Patent US1624674A successfully refreshed from Google Patents.
Patent US5647058A successfully refreshed from Google Patents.
US5647058A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for high-dimensionality indexing in a multi-media database
Assignee: International Business Machines Corp
•
Filing: 1996-02-28
•
Granted: 1997-07-08
•
Expires: 2016-02-28
Abstract
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.
Inventors
- 👤 Rakesh Agrawal
- 👤 William Robinson Equitz
- 👤 Christos Faloutsos
- 👤 Myron Dale Flickner
- 👤 Arun Narasimha Swami
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 22:53
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/40; G06F16/41; G06V; G06V10/00; G06V10/40; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
154 words
A method for indexing in a database of stored objects, the method comprising the steps of: a) applying a set of feature extraction functions to extract a set of feature vectors from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; b) transforming the set of extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the set of extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; c) truncating the transformed feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and d) indexing the truncated feature vectors using a non-sequential point-access-method (PAM).
Claim 2
Independent Claim
154 words
A method for indexing in a database of stored objects, the method comprising the steps of: a) applying a set of feature extraction functions to extract a set of feature vectors from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; b) transforming the set of extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the set of extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; c) truncating the transformed feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and d) indexing the truncated feature vectors using a non-sequential point-access-method (PAM).
Claim 3
Dependent Claim
45 words
A method for indexing as defined in claim 1 further comprising the step of conducting a similarity search on the indexed set of truncated transformed feature vectors to retrieve a set of vectors which represent a superset of objects including desired objects and false positives.
Claim 4
Dependent Claim
29 words
A method for indexing as defined in claim 2 further comprising the step of performing a secondary search on the retrieved set of vectors to eliminate the false positives.
Claim 5
Dependent Claim
19 words
A method for indexing as defined in claim 1 wherein the step of transforming includes using an orthogonal transform.
Claim 6
Dependent Claim
43 words
A method as recited in claim 1, wherein the step of transforming the extracted feature vectors includes utilizing a transform from the set consisting of (i) data-dependent orthonormal transforms, (ii) a Discrete Cosine Transform, (iii) a Harr transform, and (iv) a Wavelet transform.
Claim 7
Independent Claim
247 words
A method for identifying similar ones of stored objects in a database, the method comprising the steps of: a) identifying a subset of objects in the database, the subset including the similar objects to be identified; b) indexing said subset of similar objects, the step of indexing comprising the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors to obtain a subset of the entries of the feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and indexing the truncated feature vectors using a non-sequential point-access-method (PAM); c) conducting a preliminary similarity search on the indexed set of truncated transformed feature vectors to retrieve a set of vectors which represent a superset of objects including desired objects and false positives; and d) performing a secondary search on the retrieved set of vectors to eliminate the false positives.
Claim 8
Independent Claim
247 words
A method for identifying similar ones of stored objects in a database, the method comprising the steps of: a) identifying a subset of objects in the database, the subset including the similar objects to be identified; b) indexing said subset of similar objects, the step of indexing comprising the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors to obtain a subset of the entries of the feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and indexing the truncated feature vectors using a non-sequential point-access-method (PAM); c) conducting a preliminary similarity search on the indexed set of truncated transformed feature vectors to retrieve a set of vectors which represent a superset of objects including desired objects and false positives; and d) performing a secondary search on the retrieved set of vectors to eliminate the false positives.
Claim 9
Dependent Claim
19 words
A method for indexing as defined in claim 6 wherein the step of transforming includes using an orthonormal transform.
Claim 10
Dependent Claim
43 words
A method as recited in claim 6, wherein the step of transforming the extracted feature vectors includes utilizing a transform from the set consisting of (i) data-dependent orthonormal transforms, (ii) a Discrete Cosine Transform, (iii) a Harr transform, and (iv) a Wavelet transform.
Claim 11
Dependent Claim
201 words
A database computer system containing multi-dimensional objects, the system comprising: a) at least one storage device for storing said objects; b) a computer processor for controlling access to said stored objects; c) memory coupled to said computer processor for access thereto; and d) program means, executable by the computer processor, for performing the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors to obtain a subset of the entries of the feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and indexing the truncated feature vectors using a non-sequential point-access-method (PAM).
Claim 12
Dependent Claim
201 words
A database computer system containing multi-dimensional objects, the system comprising: a) at least one storage device for storing said objects; b) a computer processor for controlling access to said stored objects; c) memory coupled to said computer processor for access thereto; and d) program means, executable by the computer processor, for performing the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors to obtain a subset of the entries of the feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; and indexing the truncated feature vectors using a non-sequential point-access-method (PAM).
Claim 13
Dependent Claim
50 words
A system as recited in claim 9, wherein the program means for performing the step of transforming the extracted feature vectors includes means for utilizing a transform from the set consisting of (i) data-dependent orthonormal transforms, (ii) a Discrete Cosine Transform, (iii) a Harr transform, and (iv) a Wavelet transform.
Claim 14
Dependent Claim
222 words
A computer program product, for use in a database computer system containing stored objects, the computer program product comprising: a) a recording medium; and b) means, recorded on said medium, for instructing said computer system to perform the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; indexing the truncated feature vectors using a non-sequential point-access-method (PAM); conducting a preliminary similarity search on the indexed set of truncated transformed feature vectors to retrieve a set of vectors which represent a superset of objects including desired objects and false positives; and performing a secondary search on the retrieved set of vectors to eliminate the false positives.
Claim 15
Dependent Claim
222 words
A computer program product, for use in a database computer system containing stored objects, the computer program product comprising: a) a recording medium; and b) means, recorded on said medium, for instructing said computer system to perform the steps of: applying a set of feature extraction functions to extract a set of feature vectors, having respective sets of entries, from the stored objects in the database, the set of feature extraction functions having a similarity measure applicable to the stored objects; transforming the extracted feature vectors using an orthonormal transform such that the similarity measure is preserved, and such that the information of the extracted feature vectors is segregated into (i) a subset of the transformed feature vectors in which information of the set of extracted feature vectors is concentrated, and (ii) entries which contribute little to the information of the transformed vectors; truncating the transformed feature vectors such that the entries which contribute little to the information of the transformed vectors are removed; indexing the truncated feature vectors using a non-sequential point-access-method (PAM); conducting a preliminary similarity search on the indexed set of truncated transformed feature vectors to retrieve a set of vectors which represent a superset of objects including desired objects and false positives; and performing a secondary search on the retrieved set of vectors to eliminate the false positives.
Claim 16
Dependent Claim
53 words
A computer program product as recited in claim 11, wherein the means for instructing to transform the extracted feature vectors includes means for instructing the system to utilize a transform from the set consisting of (i) data-dependent orthonormal transforms, (ii) a Discrete Cosine Transform, (iii) a Harr transform, and (iv) a Wavelet transform.
References Cited (Backward Citations)
US4817176A
Cited
US4885703A
Cited
US5123088A
Cited
US5161204A
Cited
US5274714A
Cited
US5325445A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-07 | 2001-01-06 | 2001-07-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-07 | 2005-01-06 | 2005-07-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-07 | 2009-01-06 | 2009-07-08 | $7700.00 | Window Closed / Lapsed |