Methods and apparatus for estimating similarity

DETAILED DESCRIPTION Systems and methods consistent with the present invention address this and other needs by providing a similarity engine that generates compact representations of objects that can be compared to determine similarity between the objects.
In one aspect, the present invention is a method for generating a compact representation of an object.
The method includes generating a vector corresponding to the object, each coordinate of the vector being associated with a corresponding weight and multiplying the weight associated with each coordinate in the vector by a corresponding hashing vector to generate a product vector.
The method further includes summing the product vectors and generating the compact representation of the object using the summed product vectors.
A second method consistent with the present invention includes creating a similarity sketch for each of first and second objects based on the application of a hashing function to a vector representation of the first and second objects.
Additionally, the method compares, on a bit-by-bit basis, the similarity sketches for the first and second objects, and generates a value defining the similarity between the first and second objects based on a correspondence in the bit-by-bit comparison.
Another aspect of the present invention is directed to a server that includes at least one processor, a database containing a group of objects, and a memory operatively coupled to the processor.
The memory stores program instructions that when executed by the processor, cause the processor to remove similar objects from the database by comparing similarity sketches of pairs of objects in the database and removing one of the objects of the pair when the comparison indicates that the pair of objects are more similar than a threshold level of similarity.
The processor generates the similarity sketches for each of the pair of objects based on an application of a hashing function to vector representations of the objects.
Yet another aspect of the invention is directed to a method for generating a compact representation of a first object