Multidimensional data clustering and dimension reduction for ind

Details Multidimensional data clustering and dimension reduction for ind Multidimensional data clustering and dimension reduction for ind

1997-10-31

2000-09-19

Lintz, Paul R.

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 707 3, G06F 1730

Patent

active

061226289

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 can also be applied to the entire database as a first step of the index generation.

REFERENCES:
patent: 4839853 (1989-06-01), Deerwester et al.
patent: 5179643 (1993-01-01), Homma et al.
patent: 5359724 (1994-10-01), Earle
patent: 5463702 (1995-10-01), Trueblood
patent: 5497486 (1996-03-01), Stolfo et al.
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5675819 (1997-10-01), Schuetze
patent: 5787422 (1998-07-01), Tukey et al.
patent: 5819258 (1998-10-01), Vaithyanathan
patent: 5857179 (1999-01-01), Vaithyanathan et al.
Allen Gersho, "Optimal Nonlinear Interpolative Vector Quantization", IEEE Transactions on Communications, vol. 38 No. 9 Sep. 1990.
Milanese et al, "Correspondence Analysis and Hierarchical Indexing for Content-Based Image Retrieval", IEEE 1996.
Joseph Linde, et al., "An Algorithm for Vector Quantizer Design", IEEE Transactions on Communications, vol. COM-28, No. 1, Jan. 1980, pp. 84-95.
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.ibm.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.sup..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, 8 pages.
Chi-Tsong Chen, Linear System Theory and Design, Department of Electrical Engineering State University of NY at Stony Brook, 8 pages.
Jim Gray, et al., "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals", 1063-6382/96, 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 Pattern Classification Techniques", IEEE Computer Society Press, The Institute of Electrical and Electronics Engineers, Inc., Table of Contents.
Roger A. Horn, et al., "Matrix Analysis", Cambridge University Press, p. 205, 411, 414-423.
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.
Leonard Kaufman, et al., "Finding Groups in Data, An Introduction to Cluster Analysis," A Wiley Interscience Publication, John Wiley & Sons, Inc., pp. vi-xiv.
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.

Affiliated with

Also associated with

Rating

Multidimensional data clustering and dimension reduction for ind does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multidimensional data clustering and dimension reduction for ind, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multidimensional data clustering and dimension reduction for ind will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1083312