 |
|
|
|
|
|
 Title: |
US6134541:
Searching multidimensional indexes using associated clustering and dimension reduction information
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Castelli, Vittorio; White Plains, NY
Li, Chung-Sheng; Ossining, NY
Thomasian, Alexander; Pleasantville, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2000-10-17
/ 1997-10-31
|
| Application Number: |
US1997000961729
|
| IPC Code: |
Advanced:
G06F 17/30;
G06K 9/62;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S2P7; G06K9/62B1P1A; G06K9/62C1D1C;
|
| U.S. Class: |
Current:
707/002;
707/001;
707/003;
Original:
707/002;
707/001;
707/003;
|
| Field of Search: |
707/002,3,1
395/601,600
|
| Priority Number: |
| 1997-10-31 |
US1997000961729 |
|
| Abstract: |
An improved multidimensional data indexing technique that generates compact indexes such that most or all of the index can reside in main memory at any time. During the clustering and dimensionality reduction, clustering information and dimensionality reduction information are generated for use in a subsequent search phase. The indexing technique can be effective even in the presence of variables which are not highly correlated. Other features provide for efficiently performing exact and nearest neighbor searches using the clustering information and dimensionality reduction information. One example of the dimensionality reduction uses a singular value decomposition technique. The method can also be recursively applied to each of the reduced-dimensionality clusters. The dimensionality reduction also can be applied to the entire database as a first step of the index generation.
|
| Attorney, Agent or Firm: |
Jordan, Kevin M. ;
Ellenbogen, Wayne L. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Le, Uyen
|
| Maintenance Status: |
E1 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
|
| Parent Case: |
CROSS-REFERENCE TO RELATED APPLICATIONS
The present invention is related to co-pending patent application Ser. No. 08/960,540, entitled "Multidimensional Data Clustering and Dimension Reduction for Indexing and Searching," by Castelli et al., ed of even date herewith, IBM Docket No. YO997170. This co-pending application and the present invention are commonly assigned to the International Business Machines Corporation, Armonk, N.Y. This co-pending application is hereby incorporated by reference in its entirety into the present application
|
| Family: |
None
|
First Claim:
Show all 51 claims |
What is claimed is:
1. In a system including one or more reduced dimensionality indexes to multidimensional data, a method for performing an exact search for specified data using the one or more indexes, the method comprising the following steps in the sequence set forth:
- associating specified data to a data cluster based on clustering information, said data cluster being a partition of an original data input set;
- reducing a dimensionality of the specified data, based on dimensionality reduction information for a reduced dimensionality version of the cluster;
- recursively applying said associating and reducing steps unitl a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; and
- searching, using low dimensional indexes to said lowest level and a reduced dimensionality specified data, for cluster elements of the reduced dimensionality version of the cluster matching the specified data.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 90 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
Gersho, "Optimal Nonlinear Interpolative Vector Quantization", IEEE Transactions on Communications, vol. 38, No. 9, Sep. 1990, pp. 1285-1287.
(3 pages)
Cited by 2 patents
Milanese et al, "Correspondance Analysis and Hierarchical Indexing for Content-Based Image Retrieval", IEEE 1996. pp. 859-862.
Joseph Linde, et al., "An Algorithm for Vector Quantizer Design", IEEE Transactions on Communications, vol. COM-28, No. 1, Jan. 1980, pp. 84-95.
(12 pages)
Cited by 130 patents
Jerome H. Friedman, et al., "An Algorithm for Finding Nearest Neighbors", IEEE Transactions on Computers, Oct. 1975, 7 pages.
IBM Search Software, "IBM MediaMiner", http://www.software.com/data/mediaminer/immn0b21.html, Oct. 10, 1997, 7 pages.
IBM Search Software, MediaMiner: IBM Query by Image Content, "IBM Query by Image Content", http://www.software.ibm.com/data/mediaminer/immn0b14.html, Oct. 10, 1997, 2 pages.
QBIC Home Page, The QBIC Project, "QBIC.TM.--IBM's Query By Image Content", http://wwwqbic.almaden.ibm.com/, Oct. 19, 1997, 2 pages.
Trademark Demo Introduction Page, Trademark Server, http://wwwqbic.almaden.ibm.com/tmdemo/, Oct. 10, 1997, 3 pages.
IBM Search Software, DB2 Image Extender, DB2 Extenders, Universal Database, Image, http://www.software.ibm.com/data/db2/extenders image.htm, Oct. 10, 1997, 4 pages.
Hanan Samet, Region Representation: Quadtrees from Boundary Codes, Graphics and Image Processing, J.D. Foley, Editor, Communications of the ACM Mar. 1980, vol. 23, No. 3, pp. 163-170.
(8 pages)
Cited by 2 patents
Chi-Tsong Chen, Linear System Theory and Design, Department of Electrical Engineering State University of NY at Stony Brook, pp. 565-571, no date.
Jim Gray, et al., "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals," 1996 IEEE, pp. 152-159.
Antonin Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," Proceedings of Annual Meeting, SIGMOD '84 SIGMOD Record vol. 14, No. 2, Boston, MA, Jun. 18-21, 1984, pp. 47-57.
Belur V. Dasarathy, "Nearest Neighbor(NN) Norms: NN Patern Classification Techniques", IEEE Computer Society Press, The Institute of Electronics Engineers, Inc., Table of Contents, no date.
Roger A. Horn, et al., "Matrix Analysis," Cambridge University Press, pp. 205, 411, 414-423, no date.
Brian Everitt, "Cluster Analysis," Second Edition, Social Science Research Council, Heinemann Educational Books, London, Halsted Press, Division of John Wiley & Sons, NY, pp. 64-67, no date.
Leonard Kaufman, et al., "Finding Groups in Data, An Introduction to Cluster Analysis," A Wiley Interscience Publication, John Wiley & Sons, Inc., pp. vi-xiv, no date.
Ritei Shibata, "An optimal selection of regression variables," Biometrika (1981), 68, 1, pp. 45-54.
Raymond Ng, et al., "Evaluating Multi-Dimensional Indexing Structures for Images Transformed by Principal Component Analysis," Dept. of Computer Science, Univ. of British Columbia, 1996, SPIE, vol. 2670, pp. 50-61.
IBM Technical Disclosure Bulletin, "Multidimensional Index Structure with Multi-Level Entry and Skip-Level Search for Partially-Specified Queries," vol. 39, No. 11, Nov. 1996, pp. 37-39.
T. Y. Young and P. S. Liu, "Overhead Storage Considerations and a Multilinear Method for Data File Compression," IEEE Transactions on Software Engineering, vol. SE-6, No. 4, Jul. 1980, pp. 340-347.
(8 pages)
|
|
 Nominate this for the Gallery...
|
|
