Document near-duplicate detection

• US 7,962,491 B1
• Filed: 12/03/2009
• Issued: 06/14/2011
• Est. Priority Date: 03/25/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Shen, Shioupyn
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US12/630,645
• Time in Patent Office: 558 Days
• Field of Search: None
• US Class Current: 707/749
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

A near-duplicate component includes a fingerprint creation component and a similarity detection component. The fingerprint creation component receives a document of arbitrary size and generates a compact “fingerprint” that describes the contents of the document. The similarity detection component compares multiple fingerprints based on the hamming distance between the fingerprints. When the hamming distance is below a threshold, the documents can be said to be near-duplicates of one another.

Claims

1. A computer device comprising:

a memory to store instructions for implementing;

a fingerprint creation component to generate a fingerprint of a particular length for an input document, where, to generate the fingerprint, the fingerprint creation component is to;

sample the input document to obtain a plurality of sampled blocks,

generate a set of checksum values from the plurality of sampled blocks, where each checksum value, in the set of checksum values, corresponds to an address of a respective one of a plurality of bits of the fingerprint, and

generate the fingerprint by flipping a particular bit, of the plurality of bits of the fingerprint, a quantity of times based on a quantity of checksum values, in the set of checksum values, that corresponds to the address of the particular bit; and

a processor to execute the instructions in the memory.

2. The computer device of claim 1, further including:

a similarity detection component to compare a pair of fingerprints to determine whether the pair of fingerprints indicates that documents, associated with the pair of fingerprints, correspond to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints.

3. The computer device of claim 2, where, when comparing the pair of fingerprints, the similarity detection component is to calculate a hamming distance between the pair of fingerprints.

4. The computer device of claim 3, where the similarity detection component determines that the pair of fingerprints corresponds to near-duplicate documents when the hamming distance between the pair of fingerprints is below a threshold.

5. The computer device of claim 2, further including:

a search engine to index and store information regarding only one of the documents when the documents are determined to be near-duplicate documents, based on a comparison of the pair of fingerprints associated with the documents.

6. The computer device of claim 1, where the set of checksum values is a subset of checksum values generated for the input document, and

where the fingerprint creation component is further to:

select the subset of checksum values as a particular number of smallest, unique checksum values of the checksum values generated for the input document.

7. The computer device of claim 1, where the set of checksum values is a subset of checksum values generated for the input document, and

where the fingerprint creation component is further to:

select the subset of checksum values as a particular number of largest, unique checksum values of the checksum values generated for the input document.

8. The computer device of claim 1, where the fingerprint creation component is further to reduce a length of a checksum value, in the set of checksum values, to a particular length, where the checksum value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the checksum value matching the address of the one of the plurality of bits of the fingerprint.

9. The computer device of claim 8, where, when reducing the length of the checksum value, the fingerprint creation component is to subject the checksum value to a hashing algorithm to reduce the length of the checksum value to the particular length.

10. The computer device of claim 8, where, when reducing the length of the checksum value, the fingerprint creation component is to select a particular quantity of bits of the checksum value to reduce the length of the checksum value to the particular length.

11. A system comprising:

one or more computer devices configured to;

sample a document to obtain a plurality of sampled blocks, generate a set of checksum values from the plurality of sampled blocks, where each checksum value, in the set of checksum values, identifies a respective one of a plurality of bits of a fingerprint for the document, and

generate the fingerprint, for the document, by flipping each bit, of the plurality of bits of the fingerprint, a quantity of times based on a quantity of checksum values, in the set of checksum values, that identify the bit.

12. The system of claim 11, where the one or more computer devices are further to:

compare a pair of fingerprints to determine whether the pair of fingerprints corresponds to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints.

13. The system of claim 11, where the set of checksum values is a subset of checksum values generated for the document, and

where the one or more computer devices are to:

select the subset of checksum values as a particular number of smallest, unique checksum values of the checksum values generated for the document.

14. The system of claim 11, where the set of checksum values is a subset of checksum values generated for the document, and

where the one or more computer devices are to:

select the subset of checksum values as a particular number of largest, unique checksum values of the checksum values generated for the document.

15. The system of claim 11, where the one or more computer devices are to:

hash the checksum values, in the set of checksum values, to form hashed checksum values, where one of the hashed checksum values identifies one of the plurality of bits of the fingerprint.

16. The computer-implemented device of claim 11, where the one or more computer devices are to:

initialize each of the plurality of bits of the fingerprint to a particular value before flipping any of the plurality of bits of the fingerprint.

17. A method, performed by one or more server devices, the method comprising:

generating, by one or more processors associated with the one or more server devices, a plurality of checksum values based on a document;

reducing, by one or more processors associated with the one or more server devices, lengths of the plurality of checksum values to form a plurality of reduced-length checksum values, where each reduced-length checksum value, of the plurality of reduced-length checksum values, matches an address of a respective one of a plurality of bits of a fingerprint corresponding to the document; and

generating, by one or more processors associated with the one or more server devices, the fingerprint, corresponding to the document, by flipping each bit, of the plurality of bits of the fingerprint, based on a quantity of reduced-length checksum values, of the plurality of reduced-length checksum values, that matches the address of the bit.

18. The method of claim 17, where reducing lengths of the plurality of checksum values includes:

hashing each of the plurality of checksum values to a particular size.

19. The method of claim 18, where the hashing includes selecting a quantity of bits of each of the plurality of checksum values.

20. The method of claim 18, further comprising:

initializing, prior to flipping any bits of the plurality of bits of the fingerprint, the fingerprint by setting all of the plurality of bits of the fingerprint to a particular value.

21. The method of claim 17, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the method further comprises:

selecting the subset of checksum values as a particular number of smallest, unique checksum values of the checksum values generated for the document.

22. The method of claim 17, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the method further comprises:

selecting the subset of the checksum values as a particular number of largest, unique checksum values of the checksum values generated for the document.

23. The method of claim 17, further comprising:

comparing a pair of fingerprints to determine whether the pair of fingerprints indicates that documents, associated with the pair of fingerprints, correspond to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints.

24. The method of claim 23, further comprising:

providing the documents to a user as a single link when the documents are determined to be near-duplicate documents based on a comparison of the pair of fingerprints associated with the documents.

25. A computer device, comprising:

a memory to store instructions for implementing;

a fingerprint creation component to generate a fingerprint of a particular length for a document, where, to generate the fingerprint, the fingerprint creation component is to;

generate a plurality of checksum values based on the document,

reduce lengths of the plurality of checksum values to form a plurality of reduced-length checksum values, where each reduced-length checksum value, of the plurality of reduced-length checksum values, matches an address of a respective one of a plurality of bits of the fingerprint corresponding to the document, and

generate the fingerprint, corresponding to the document, by flipping each bit, of the plurality of bits of the fingerprint, based on a quantity of reduced-length checksum values, of the plurality of reduced-length checksum values, that matches the address of the bit; and

a processor to execute the instructions in the memory.

26. The computer device of claim 25, where, when reducing lengths of the plurality of checksum values, the fingerprint creation component is to:

hash each of the plurality of checksum values to a particular size, or

select a quantity of bits of each of the plurality of checksum values.

27. The computer device of claim 25, where the fingerprint creation component is further to initialize, prior to flipping any bits of the plurality of bits of the fingerprint, the fingerprint by setting all of the plurality of bits of the fingerprint to a particular value.

28. A system, comprising:

one or more computer devices to;

generate a plurality of checksum values based on a document;

reduce lengths of the plurality of checksum values to form a plurality of reduced-length checksum values, where each reduced-length checksum value, of the plurality of reduced-length checksum values, matches an address of a respective one of a plurality of bits of a fingerprint corresponding to the document; and

generate the fingerprint, corresponding to the document, by flipping each bit, of the plurality of bits of the fingerprint, based on a quantity of reduced-length checksum values, of the plurality of reduced-length checksum values, that matches the address of the bit.

29. The system of claim 28, where the one or more computer devices are further to:

compare a pair of fingerprints to determine whether the pair of fingerprints indicates that documents, associated with the pair of fingerprints, correspond to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints.

30. The system of claim 29, where the one or more computer devices are further to:

provide the documents to a user as a single link when the documents are determined to be near-duplicate documents based on a comparison of the pair of fingerprints associated with the documents.

31. A method performed by one or more server devices, the method comprising:

sampling an input document to obtain a plurality of sampled blocks;

generating a set of checksum values from the plurality of sampled blocks, where each checksum value, in the set of checksum values, corresponds to an address of a respective one of a plurality of bits of a fingerprint for the input document; and

generating the fingerprint by flipping a particular bit, of the plurality of bits of the fingerprint, a quantity of times based on a quantity of checksum values, in the set of checksum values, that corresponds to the address of the particular bit.

32. The method of claim 31, further comprising:

comparing a pair of fingerprints to determine whether the pair of fingerprints indicates that documents, associated with the pair of fingerprints, correspond to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints; and

determining that the pair of fingerprints corresponds to near-duplicate documents when a hamming distance between the pair of fingerprints is below a threshold.

33. The method of claim 31, further comprising:

comparing a pair of fingerprints to determine whether the pair of fingerprints indicates that documents, associated with the pair of fingerprints, correspond to near-duplicate documents, where the fingerprint is one of the fingerprints in the pair of fingerprints; and

indexing and storing information regarding only one of the documents when the documents are determined to be near-duplicate documents, based on the comparison of the pair of fingerprints associated with the documents.

34. A method performed by one or more server devices, the method comprising:

sampling a document to obtain a plurality of sampled blocks;

generating a set of checksum values from the plurality of sampled blocks, where each checksum value, in the set of checksum values, identifies a respective one of a plurality of bits of a fingerprint for the document; and

generating the fingerprint, for the document, by flipping each bit, of the plurality of bits of the fingerprint, a quantity of times based on a quantity of checksum values, in the set of checksum values, that identify the bit.

35. The method of claim 34, further comprising:

hashing the checksum values, in the set of checksum values, to form hashed checksum values, where one of the hashed checksum values identifies one of the plurality of bits of the fingerprint.

36. The method of claim 34, further comprising:

initializing each of the plurality of bits of the fingerprint to a particular value before flipping any of the plurality of bits of the fingerprint.