Method for high-dimensionality indexing in a multi-media database

• US 5,647,058 A
• Filed: 02/28/1996
• Issued: 07/08/1997
• Est. Priority Date: 05/24/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Faloutsos, Christos, Flickner, Myron Dale, Swami, Arun Narasimha, Equitz, William Robinson
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/607,922
• Time in Patent Office: 496 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/600, 395/154, 382/27, 382/30, 382/41, 382/43, 382/46, 382/48
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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 v 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.

Claims

1. 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).

2. 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.

3. 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.

4. A method for indexing as defined in claim 1 wherein the step of transforming includes using an orthogonal transform.

5. 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.

6. 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.

7. A method for indexing as defined in claim 6 wherein the step of transforming includes using an orthonormal transform.

8. 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.

9. 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).

10. 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.

11. 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.

12. 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.