Document near-duplicate detection

• US 7,707,157 B1
• Filed: 03/25/2004
• Issued: 04/27/2010
• 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): Ly; Cheyne D
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US10/808,326
• Time in Patent Office: 2,224 Days
• Field of Search: 707/6, 707/200, 707/3, 707/101, 707/102, 707/104.1
• US Class Current: 1/1
• 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 method for generating a fingerprint of a document, performed by one or more server devices, the method comprising:

obtaining, by a processor associated with the one or more server devices, a plurality of overlapping blocks by sampling the document;

generating, by a processor associated with the one or more server devices, a set of checksum values from the plurality of overlapping blocks;

choosing, by a processor associated with the one or more server devices, a subset of the set of checksum values, where the subset is less than an entirety of the set of checksum values;

initializing, by a processor associated with the one or more server devices, the fingerprint of the document by setting all bits of the fingerprint to zero;

addressing, by a processor associated with the one or more server devices, a particular bit of the fingerprint with a particular checksum value; and

flipping, by a processor associated with the one or more server devices, the particular bit of the fingerprint a number of times corresponding to a number of times the particular checksum value occurs in the subset.

2. The method of claim 1, where the fingerprint comprises a predetermined length.

3. The method of claim 2, where the predetermined length is eight or sixteen bytes.

4. The method of claim 1, where choosing a subset of the set of checksum values includes selecting a predetermined number of the smallest checksum values.

5. The method of claim 1, where choosing a subset of the set of checksum values includes selecting a predetermined number of the largest checksum values.

6. The method of claim 1, further comprising:

hashing the subset of the set of checksum values to a length for addressing the bits of the fingerprint.

7. The method of claim 6, where hashing the subset of the set of checksum values includes taking a number of least significant bits of the subset of the set of checksum values.

8. The method of claim 1, where each of the plurality of overlapping blocks is of a predetermined length.

9. The method of claim 8, where obtaining a plurality of overlapping blocks further includes:

padding null characters to the document when a length of the document is below the predetermined length.

10. A method for generating a fingerprint of a document, performed by one or more server devices, the method comprising:

sampling, by a processor associated with the one or more server devices, the document to obtain a plurality of overlapping samples;

generating, by a processor associated with the one or more server devices, a set of checksum values from the plurality of overlapping samples;

selecting, by a processor associated with the one or more server devices, a subset of the set of checksum values as those of the checksum values corresponding to a predetermined number of smallest checksum values or a predetermined number of largest checksum values;

addressing, by a processor associated with the one or more server devices, a particular bit of the fingerprint with a particular checksum value; and

flipping, by a processor associated with the one or more server devices, the particular bit of the fingerprint a number of times corresponding to a number of times the particular checksum value occurs in the subset.

11. The method of claim 10, where the fingerprint comprises a predetermined length.

12. The method of claim 11, where the predetermined length is eight or sixteen bytes.

13. The method of claim 10, further comprising:

hashing the subset of the checksum values to a length for indexing the fingerprint of the document.

14. The method of claim 13, where hashing the subset of the checksum values includes taking a number of least significant bits of the predetermined number of checksum values.

15. The method of claim 13, where flipping a particular bit in the fingerprint of the document includes flipping the particular bit in the fingerprint of the document when the particular value addressed to the particular bit corresponds to a particular one of the hashed checksum values.

16. A memory device containing program instructions that, when executed by a processor, cause the processor to:

sample a document to obtain a plurality of overlapping samples;

generate a set of checksum values from the plurality of overlapping samples;

select a subset of the set of checksum values as those of the checksum values corresponding to a predetermined number of smallest checksum values or a predetermined number of largest checksum values;

addressing bits in the fingerprint with particular values; and

flipping a particular bit in the fingerprint a number of times based on a number of checksum values in the subset that correspond to the particular value addressed to the particular bit.

17. The memory device of claim 16, further including program instructions that, when executed by the processor, cause the processor to:

hash the subset of the checksum values to a length for setting the bits in the fingerprint of the document.

18. The memory device of claim 17, where hashing the predetermined number of the checksum values includes taking a number of least significant bits of the predetermined number of checksum values.