Methods and apparatus for estimating similarity
First Claim
1. A computer-implemented method for generating a compact representation of a first object, comprising:
- (a) identifying a set of features corresponding to the first object;
(b) generating for each feature a hashing vector having n coordinates;
(c) summing the hashing vectors to obtain a summed vector; and
(d) creating an n·
x-bit representation of the summed vector by calculating an x-bit value for each coordinate of the summed vector, the n·
x-bit representation of the summed vector defining the compact representation of the first object.
2 Assignments
0 Petitions
Accused Products
Abstract
A similarity engine generates compact representations of objects called sketches. Sketches of different objects can be compared to determine the similarity between the two objects. The sketch for an object may be generated by creating a vector corresponding to the object, where each coordinate of the vector is associated with a corresponding weight. The weight associated with each coordinate in the vector is multiplied by a predetermined hashing vector to generate a product vector, and the product vectors are summed. The similarity engine may then generate a compact representation of the object based on the summed product vector.
-
Citations
24 Claims
-
1. A computer-implemented method for generating a compact representation of a first object, comprising:
-
(a) identifying a set of features corresponding to the first object; (b) generating for each feature a hashing vector having n coordinates; (c) summing the hashing vectors to obtain a summed vector; and (d) creating an n·
x-bit representation of the summed vector by calculating an x-bit value for each coordinate of the summed vector, the n·
x-bit representation of the summed vector defining the compact representation of the first object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer-implemented method for generating a compact representation of an object, comprising:
-
generating a vector corresponding to the object, each coordinate of the vector being associated with a corresponding weight; multiplying the weight associated with each coordinate in the vector by a corresponding hashing vector to generate a product vector; summing the product vectors to obtain a summed product vector; and generating a compact representation of the object using the summed product vectors. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21)
-
-
22. A system for generating a compact representation of an object, comprising:
-
means for generating a vector corresponding to the object, each coordinate of the vector being associated with a corresponding weight; means for multiplying the weight associated with each coordinate in the vector by a corresponding hashing vector to generate a product vector; means for summing the product vectors to obtain a summed product vector; and means for generating the compact representation based on the summed product vector.
-
-
23. A computer-readable medium storing instructions for causing at least one processor to perform a method that generates a compact representation of an object, the method comprising:
-
generating a vector corresponding to the object, each coordinate of the vector being associated with a corresponding weight; multiplying the weight associated with each coordinate in the vector by a corresponding hashing vector to generate a product vector; summing the product vectors; and generating the compact representation of the object using the summed product vector.
-
-
24. A computer-implemented method for generating a compact representation of an object, comprising:
-
generating an object vector corresponding to the object; generating a hashing vector corresponding to each coordinate of the object vector; summing the hashing vectors to obtain a summed vector; calculating at least one bit corresponding to each coordinate of the summed product vector; and generating a compact representation of the object by concatenating the calculated bits.
-
Specification