Methods and apparatus for estimating similarity

• US 7,158,961 B1
• Filed: 12/31/2001
• Issued: 01/02/2007
• Est. Priority Date: 12/31/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Charikar, Moses Samson
• Primary Examiner(s): Robinson; Greta
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US10/029,883
• Time in Patent Office: 1,828 Days
• Field of Search: 707 1- 3, 707/5, 707/10, 707/100, 707/102, 707/104.1, 708/200, 708422-424, 345/418, 345/419, 345/427, 382/10, 382/154, 382/181, 382/190, 382/191, 382/209, 382217-220, 382276-278
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

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.

2. The computer-implemented method of claim 1, wherein the set of features is a vector.

3. The computer-implemented method of claim 1, wherein generating for each feature a hashing vector comprises:

determining a weight associated with each feature; and

multiplying each hashing vector by the weight determined for the corresponding feature.

4. The computer-implemented method of claim 1, wherein the object is a document.

5. The computer-implemented method of claim 4, wherein each feature is a word within the document.

6. The computer-implemented method of claim 1, wherein the object is a summary of another object.

7. The computer-implemented method of claim 1, wherein x is equal to 1.

8. The computer-implemented method of claim 1, wherein n is equal to 64.

9. The computer-implemented method of claim 1, further comprising:

repeating acts (a)–

(d) for a second object to create a second n·

x-bit representation; and

comparing the first and second n·

x-bit representations to determine whether the first and second objects are similar.

10. The computer-implemented method of claim 9, further comprising discarding either one of the first or second objects.

11. The computer-implemented method of claim 1, further comprising:

repeating acts (a)–

(d) for m objects to create m n·

x-bit representations; and

grouping the m objects based on their corresponding n·

x-bit representations.

12. The computer-implemented method of claim 11, further comprising compressing the objects by group.

13. The computer-implemented method of claim 1, wherein act (b) comprises generating for each feature a hashing vector having n coordinates, such that the hashing vectors are similar for similar features.

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.

15. The computer-implemented method of claim 14, wherein the weights are real numbers.

16. The computer-implemented method of claim 15, wherein the weights include values between zero and one.

17. The computer-implemented method of claim 14, wherein the object is a web document.

18. The computer-implemented method of claim 17, wherein the coordinates in the vector correspond to words in the web document.

19. The computer-implemented method of claim 18, further comprising:

assigning the weights for each coordinate of the vector as the number of occurrences of the word within the web document divided by the number of web documents contained in a collection of web documents that contain the word.

20. The computer-implemented method of claim 14, wherein values in the hashing vectors are generated using a pseudo random number generator seeded based on the coordinate corresponding to the hashing vector.

21. The computer-implemented method of claim 14, wherein each bit is generated based on the sign of the value of the coordinate.

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.