Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View

  Buy Now:   Buy PDF- 34pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
Title: US6122628: Multidimensional data clustering and dimension reduction for indexing and searching
[ Derwent Title ]


Country: US United States of America

View Images High
Resolution

 Low
 Resolution

 
34 pages

 
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-09-19 / 1997-10-31

Application Number: US1997000960540

IPC Code: Advanced: G06F 17/30; G06K 9/62;
Core: more...

Subclass: G06F; IPC-7:
G06F 17/30
;

ECLA Code: G06F17/30S2P7; G06F17/30T1P; G06K9/62B1P1A; G06K9/62C1D1C;

U.S. Class: Current: 707/005; 707/002; 707/003; 707/E17.085;
Original: 707/005; 707/002; 707/003;

Field of Search: 707/003,2,5,1,4,101 395/601,600

Priority Number:
1997-10-31  US1997000960540

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.

Attorney, Agent or Firm: Jordan, Kevin M.F. Chau & Associates, LLP ;

Primary / Asst. Examiners: Lintz, Paul R.; Le, Uyen

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

Parent Case:

CROSS-REFERENCE TO RELATED APPLICATIONS
    The present invention is related to patent application Ser. No. 08/961,729 entitled "Searching Multidimensional Indexes Using Associated Clustering and Dimension Reduction Information," by Castelli et al., filed of even date herewith, now pending. 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

Designated Country: CZ EP HU IL KR PL RU  DE FR GB IE 

Family: Show 20 known family members

First Claim:
Show all 73 claims
What is claimed is:     1. A computerized method of representing multidimensional data, comprising the steps of:
  • a) partitioning the multidimensional data into one or more clusters;
  • b) generating and storing clustering information for said one or more clusters;
  • c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters;
  • d) storing the dimensionality reduction information;
  • e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and
  • f) generating and storing one or more low-dimensional idexes for clusters at a lowest level of said hierarchy.


Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 138 U.S. patent(s) that reference this one

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (138)   |   Backward references (10)   |   Citation Link

Buy
PDF
Patent  Pub.Date  Inventor Assignee   Title
Buy PDF- 9pp US4839853  1989-06 Deerwester et al.  Bell Communications Research, Inc. Computer information retrieval using latent semantic structure
Buy PDF- 20pp US5179643  1993-01 Homma et al.  Hitachi, Ltd. Method of multi-dimensional analysis and display for a large volume of record information items and a system therefor
Buy PDF- 25pp US5359724  1994-10 Earle  Arbor Software Corporation Method and apparatus for storing and retrieving multi-dimensional data in computer memory
Buy PDF- 20pp US5463702  1995-10 Trueblood  Sony Electronics Inc. Perceptual based color-compression for raster image quantization
Buy PDF- 22pp US5497486  1996-03 Stolfo et al.  Stolfo; Salvatore J. Method of merging large databases in parallel
Buy PDF- 13pp US5647058  1997-07 Agrawal et al.  International Business Machines Corporation Method for high-dimensionality indexing in a multi-media database
Buy PDF- 29pp US5675819  1997-10 Schuetze  Xerox Corporation Document information retrieval using global word co-occurrence patterns
Buy PDF- 17pp US5787422  1998-07 Tukey et al.  Xerox Corporation Method and apparatus for information accesss employing overlapping clusters
Buy PDF- 15pp US5819258  1998-10 Vaithyanathan  Digital Equipment Corporation Method and apparatus for automatically generating hierarchical categories from large document collections
Buy PDF- 18pp US5857179  1999-01 Vaithyanathan et al.  Digital Equipment Corporation Computer method and apparatus for clustering documents and automatic generation of cluster keywords
       
Foreign References: None

Other Abstract Info: DERABS G1999-313467

Other References:
  • 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. (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.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.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.


  • Inquire Regarding Licensing

    Powered by Verity


    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help