Similarity search system with compact data structures

• US 20060101060A1
• Filed: 09/07/2005
• Published: 05/11/2006
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: The Trustees of Princeton University (Princeton University)
• Original Assignee: The Trustees of Princeton University (Princeton University)
• Inventors: Li, Kai, Charikar, Moses, Lv, Qin
• Granted Patent: US 7,966,327 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

A content-addressable and searchable storage system for managing and exploring massive amounts of feature-rich data such as images, audio or scientific data, is shown. The system comprises a segmentation and feature extraction unit for segmenting data corresponding to an object into a plurality of data segments and generating a feature vector for each data segment; a sketch construction component for converting a feature vector into a compact bit-vector corresponding to the object; a similarity index comprising a plurality of compact bit-vectors corresponding to a plurality of objects; and an index insertion component for inserting a compact bit-vector corresponding to an object into the similarity index. The system may further comprise an indexing unit for identifying a candidate set of objects from said similarity index based upon a compact bit-vector corresponding to a query object. Still further, the system may additionally comprise a similarity ranking component for ranking objects in said candidate set by estimating their distances to the query object.

Claims

1. A method of searching a plurality of stored objects comprising the steps of:

generating a collection of multi-dimensional vectors representing each said object, each of said multi-dimensional vectors having an associated weight;

defining a similarity distance between said objects using a distance function; and

finding objects closest to a query object based upon said distance function.

2. A method of searching a plurality of stored objects according to claim 1, wherein said distance function comprises a monotone function of matched distances.

3. A method of searching a plurality of stored objects according to claim 1 wherein said distance function comprises an Earth Mover'"'"'s Distance.

4. A method of searching a plurality of stored objects according to claim 1, wherein said step of finding objects closest to a query object comprises the step of using sketches to filter objects to form a candidate set.

5. A method of searching a plurality of stored objects according to claim 4, further comprising the step of using a distance calculation to rank objects in said candidate set.

6. A method of searching a plurality of stored objects according to claim 1 further comprising the step of applying a transformation to each multi-dimensional vector to threshold the distances between pairs of vectors.

7. A search system comprising:

means for inputting data;

a segmentation and feature extraction unit for segmenting data and generating feature vectors representing segmented data; and

a similarity search engine comprising;

a sketch construction unit for converting feature vectors into sketches;

a similarity index;

an indexing unit for identifying a candidate set of objects in said similarity index; and

a similarity ranking component for ranking objects in the candidate set.

8. A search system according to claim 7 wherein said feature vectors have a client-defined distance function.

9. A search system according to claim 7 further comprising an index insertion unit for inserting data into said similarity index.

10. A search system according to claim 7 wherein said sketch construction unit converts a feature vector into a compact representation.

11. A search system according to claim 10 wherein said compact representation comprises a compact bit-vector.

12. A search system according to claim 7 wherein said sketch construction unit maps said feature vectors to a lower-dimensional vector such that said mapping approximates an ordering of objects in an original high dimensional space.

13. A method of processing data comprising the steps of:

segmenting said data into a plurality of segments;

extracting a feature vector from each of said plurality of segments;

converting each of said feature vectors into a segment sketch;

calculating a segment weight for each of said segments; and

embedding a plurality of said segment sketches and weights into a composite data feature vector.

14. A method of processing data according to claim 13 wherein said data comprises at least one of image data, audio data, and genomic data.

15. A method of comparing a search image to a first plurality of stored images comprising the steps of:

segmenting the search image into a plurality of search image regions;

extracting a region feature vector from each of said search image regions;

converting each of said region feature vectors into a region sketch;

storing said region sketches;

calculating a region weight for each of said search image regions;

embedding all of said region sketches and region weights into a composite search image feature vector;

storing said composite search image feature vector; and

selecting a second plurality of images from said database using said composite search image feature vector, wherein said second plurality of images comprises a subset of said first plurality of images.

16. A method of comparing a search image to a database of images according to claim 15, wherein a region'"'"'s weight is a function of the regions size.

17. A method of comparing a search image to a database of images according to claim 16, wherein said function of a region'"'"'s size comprises a normalized square root of said region'"'"'s size.

18. A method of comparing a search image to a database of images according to claim 15, further comprising the steps of:

calculating an image dissimilarity match between said search image and each of said second plurality of images using said region bit vectors of said search image; and

selecting a third plurality of images based upon said image dissimilarity matches, wherein said third plurality of images comprises a subset of said second plurality of images.

19. A method of comparing a search image to a database of images according to claim 18, wherein said image dissimilarity match comprises a distance function.

20. A method of comparing a search image to a database of images according to claim 19, wherein said distance function comprises an Earth Mover'"'"'s Distance.

21. A method of comparing a search image to a database of images according to claim 19, wherein said distance function uses a function of a region size as a region weight.

22. A method of comparing a search image to a database of images according to claim 21 wherein said function of a region size comprises a square root of a region size.

23. A method of comparing a search image to a database of images according to claim 19, wherein said distance function uses a thresholded region distance.

24. A method of comparing a search image to a database of images according to claim 15 further comprising the steps of:

calculating a distance between two of said plurality of regions by XOR-ing their region bit vectors;

comparing said distance to a threshold;

selecting said distance as a region ground distance function if said distance is less than said threshold;

selecting said threshold as said region ground distance function if said distance is greater than said threshold;

calculating an image dissimilarity match between said search image and each of said second plurality of images using said region bit vectors and said ground distance function; and

selecting a third plurality of images based upon said image dissimilarity matches, wherein said third plurality of images comprises a subset of said second plurality of images.

25. A method of processing an image comprising the steps of:

segmenting said image into a plurality of regions;

extracting a feature vector from each of said regions;

converting each of said feature vectors into a region bit vector;

storing each of said region bit vectors;

embedding all of said region bit vectors into a composite image feature vector;

converting said composite image feature vector into an image bit vector;

storing said image bit vector.

26. A method for performing a similarity search:

segmenting input data;

extracting input data feature vectors from said segmented input data;

constructing an input data sketch from said feature vectors;

indexing said input data based upon said sketch;

segmenting query data;

extracting query data feature vectors from said segmented query data;

constructing a query data sketch from said query data feature vectors; and

comparing said query data sketch to a plurality of input data sketches.

27. A system for performing similarity searches on data comprising:

a segmentation and feature extraction unit for segmenting data corresponding to an object into a plurality of data segments and generating a feature vector for each data segment;

a sketch construction component for converting a feature vector into a compact bit-vector corresponding to said object;

a similarity index comprising a plurality of compact bit-vectors corresponding to a plurality of objects; and

an index insertion component for inserting a compact bit-vector corresponding to an object into said similarity index.

28. A system for performing similarity searches on data according to claim 27, further comprising:

an indexing unit for identifying a candidate set of objects from said similarity index based upon a compact bit-vector corresponding to a query object.

29. A system for performing similarity searches on data according to claim 28, further comprising:

a similarity ranking component for ranking objects in said candidate set by estimating their distances to the query object.

30. A system for performing similarity searches on data comprising:

a first segmentation and feature extraction unit for segmenting data corresponding to a first type of object into a plurality of data segments and generating a feature vector for each data segment;

a second segmentation and feature extraction unit for segmenting data corresponding to a second type of object into a plurality of data segments and generating a feature vector for each data segment;

a sketch construction component for converting a feature vector into a compact bit-vector corresponding to an object;

a similarity index comprising a plurality of compact bit-vectors corresponding to a plurality of objects; and

an index insertion component for inserting a compact bit-vector corresponding to an object into said similarity index.

31. A system for performing similarity searches on data according to claim 30, wherein said first data type comprises image data.

32. A system for performing similarity searches on data according to claim 31, wherein said second data type comprises audio data.

33. A system for performing similarity searches on data according to claim 30, wherein said first and second data types each comprise a different data type selected from the group of image data, audio data, and genomic data.

34. A system for performing similarity searches on data according to claim 30, further comprising:

an indexing unit for identifying a candidate set of objects from said similarity index based upon a compact bit-vector corresponding to a query object.

35. A system for performing similarity searches on data according to claim 31, further comprising:

a similarity ranking component for ranking objects in said candidate set by estimating their distances to the query object.