Similarity search system with compact data structures

• US 7,966,327 B2
• Filed: 09/07/2005
• Issued: 06/21/2011
• Est. Priority Date: 11/08/2004
• Status: Expired due to Fees

• 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
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US11/219,822
• Publication Number:
  US 20060101060A1
• Time in Patent Office: 2,113 Days
• Field of Search: 707/1, 707/2, 707/100, 707/101, 707/102, 707/104.1, 709/216, 709/217, 709/218, 345/419, 348/625, 358/487
• US Class Current: 707/737
• 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. A segmentation and feature extraction unit segments data corresponding to an object into a plurality of data segments and -generates a feature vector for each data segment. A sketch construction component converts the feature vector into a compact bit-vector corresponding to the object. The system also has a similarity index having 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 have 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 have 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 with a segmentation and feature extraction unit a collection of real-valued multi-dimensional vectors representing each said object, each of said multi-dimensional vectors having an associated weight;

converting when executed by a disk each of said multi-dimensional vectors into a sketch using a thresholding and transformation algorithm and storing said sketch in a database to produce a collection of sketches corresponding to each object, wherein each said sketch comprises a bit vector that is more compact than a real-valued multi-dimensional vector from which said sketch is converted; and

finding objects closest to a query object with a similarity search engine, wherein said similarity search engine finds said objects closest to said query object based upon said sketches stored in said database.

2. A method of searching a plurality of stored objects according to claim 1, wherein said step of finding objects comprises the steps of:

defining a similarity distance between said objects using a weighted distance function based upon said collection of sketches; and

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

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

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

5. A method of searching a plurality of stored objects according to claim 2, wherein said step of finding objects closest to a query object comprises the step of using Earth Mover'"'"'s Distance computation on said collection of sketches to filter objects to form a candidate set.

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

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

8. A method of searching a plurality of stored objects in accordance with claim 2, wherein the step of generating a collection of multi-dimensional vectors comprises the steps of:

segmenting each object into a plurality of segments; and

performing feature extraction on said plurality of segments corresponding to each object to produce said collection of multi-dimensional vectors.

9. A method of searching a plurality of stored objects according to claim 2, wherein said step of defining a similarity distance comprises the step of:

generating multi-dimensional feature vectors corresponding to a query object and converting said multi-dimensional feature vectors into a plurality of sketches and corresponding weights using an embedding and conversion technique.

10. A method of searching a plurality of stored objects according to claim 1, wherein said step of finding objects comprises the steps of:

combining said collection of sketches corresponding to an object into a combined sketch corresponding to that object;

defining a similarity distance between said objects using a weighted distance function based upon said combined sketch; and

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