 |
|
|
|
|
|
 Title: |
US5647058:
Method for high-dimensionality indexing in a multi-media database
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Equitz, William Robinson; Palo Alto, CA
Faloutsos, Christos; Silver Spring, MD
Flickner, Myron Dale; San Jose, CA
Swami, Arun Narasimha; San Jose, CA
|
| 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: |
1997-07-08
/ 1996-02-28
|
| Application Number: |
US1996000607922
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30E;
|
| U.S. Class: |
Current:
707/001;
707/104.1;
707/E17.009;
Original:
395/601;
364/282.1;
364/DIG.1;
395/615;
|
| Field of Search: |
364/DIG. 1,DIG. 2
395/600,154
382/027,30,41,43,46,48
|
| Priority Number: |
| 1996-02-28 |
US1996000607922 |
| 1993-05-24 |
US1993000066759 |
|
| Abstract: |
A high dimensional indexing method is disclosed which takes a set of objects that can be viewed as N-dimensional data vectors and builds an index which treats the objects like k-dimensional points. The method first defines and applies a set of feature extraction functions that admit some similarity measure for each of the stored objects in the database. The feature vector is then transformed in a manner such that the similarity measure is preserved and that the information of the feature vector +E,rar v+EE is concentrated in only a few coefficients. The entries of the feature vectors are truncated such that the entries which contribute little on the average to the information of the transformed vectors are removed. An index based on the truncated feature vectors is subsequently built using a point access method (PAM). A preliminary similarity search can then be conducted on the set of truncated transformed vectors using the previously created index to retrieve the qualifying records. A second search on the previously retrieved set of vectors is used to eliminate the false positives and to get the results of the desired similarity search.
|
| Attorney, Agent or Firm: |
Pintner, James C. ;
Blair, Philip E. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Von Buhr, Maria N.
|
| Maintenance Status: |
E1 Expired Check current status
|
| INPADOC Legal Status: |
Show legal status actions
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G97-363300
DERG97-363300
|
| Other References: |
J. H. Friedman et al., An Algorithm for Finding Nearest Neighbors, IEEE Transactions on Computers, Oct. 1975, pp. 1000-1006.
(7 pages)
Cited by 2 patents
T.-Y. Hou et al., A Content-based indexing technique using relative Geometry features, SPIE vol. 1662 Image Storage and Retrieval Sys. 1992, pp. 59-68.
J. E. Gary et al., Shape Similarity-Based Retrieval in Image Database Systems, SPIE vol. 1662 Image Storage and Retrieval Systems, 1992.
A. Califano et al., Multimensional Indexing for Recognizing Visual Shapes, IEEE CH2983-May 1991.
H. V. Jagadish, A Retrieval Technique for Similar Shapes, Proceedings of ACM SIGMOD Jun. 1991, vol. 20, No. 2, pp. 208-217.
C. Faloutsos et al., Diamond-Tree: An Index Structure for High-Dimensionality Approximate Searching, Tech. Research Report, Univ. of Maryland, TR92-97.
R. W. Picard et al., Finding Similar Patterns in Large Image Databases, Media Lab., E15-392, MIT, Proceedings of IEEE Conf. on Acoustics, Speech, and Signal Processing, Minneapolis, MN, Apr. 1993.
P. W. Foltz et al., Personalized Information Delivery: An Analysis of Information Filtering Methods, Comm. of the ACM, Dec. 1992, vol. 35, No. 12, pp. 51-60.
(10 pages)
Cited by 30 patents
[ISI abstract]
D. E. Willard, Multidimensional Search Trees that Provide New Types of Memory Reductions, Journal of the Association for Computing Machinery, vol. 34, No. 4, Oct. 1987, pp. 846-858.
(13 pages)
D. Casasent et al., Fourier-Transform Feature-Space Studies, Proceeding of SPIE--The International Society for Optical Engineering, vol. 449, Nov. 1983.
|
|
 Nominate this for the Gallery...
|
|
