Similarity search system with compact data structures
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.
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.