Document near-duplicate detection

• US 8,364,686 B1
• Filed: 05/27/2011
• Issued: 01/29/2013
• Est. Priority Date: 03/25/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Shen, Shioupyn
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US13/117,543
• Time in Patent Office: 613 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 method performed by one or more computer devices, the method comprising:

generating, by at least one of the one or more computer devices, a fingerprint for an input document, where generating the fingerprint includes;

sampling the 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 the fingerprint, 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; and

storing, by at least one of the one or more computing devices, the fingerprint in a memory.

2. The method of claim 1, 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.

3. The method of claim 2, where comparing the pair of fingerprints includes calculating a hamming distance between the pair of fingerprints, where the pair of fingerprints corresponds to the near-duplicate documents when the hamming distance between the pair of fingerprints is below a threshold.

4. The method of claim 2, further comprising:

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

5. The method of claim 1, where the set of checksum values is a subset of checksum values generated for the input 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 input document.

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

where the method further comprises:

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

7. The method of claim 1, further comprising:

reducing 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.

8. The method of claim 7, where reducing the length of the checksum value includes subjecting the checksum value to a hashing algorithm to reduce the length of the checksum value to the particular length.

9. The method of claim 7, where reducing the length of the checksum value includes selecting a particular quantity of bits of the checksum value to reduce the length of the checksum value to the particular length.

10. A non-transitory computer-readable memory device that stores instructions executable by one or more computer devices, the computer-readable memory device comprising:

one or more instructions to generate a fingerprint for an input document, where the one or more instructions to generate the fingerprint include;

one or more instructions to sample the input document to obtain a plurality of sampled blocks,

one or more instructions to 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

one or more instructions to 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

one or more instructions to store the fingerprint.

11. The computer-readable memory device of claim 10, further comprising:

one or more instructions 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.

12. The computer-readable memory device of claim 11, where the one or more instructions to compare the pair of fingerprints include one or more instructions fingerprints corresponds to the near-duplicate documents when the hamming distance between the pair of fingerprints is below a threshold.

13. The computer-readable memory device of claim 11, further comprising:

one or more instructions to index and store information regarding only one of the documents when the documents are determined to be the near-duplicate documents based on the comparison of the pair of fingerprints associated with the documents.

14. The computer-readable memory device of claim 10, where the set of checksum values is a subset of checksum values generated for the input document, and

where the computer-readable memory device further comprises:

one or more instructions 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.

15. The computer-readable memory device of claim 10, where the set of checksum values is a subset of checksum values generated for the input document, and

where the computer-readable memory device further comprises:

one or more instructions 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.

16. The computer-readable memory device of claim 10, further comprising:

one or more instructions 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.

17. The computer-readable memory device of claim 16, where the one or more instructions to reduce the length of the checksum value include one or more instructions to subject the checksum value to a hashing algorithm to reduce the length of the checksum value to the particular length.

18. The computer-readable memory device of claim 16, where the or more instructions to reduce the length of the checksum value include one or more instructions to select a particular quantity of bits of the checksum value to reduce the length of the checksum value to the particular length.

19. A method performed by one or more computer devices, the method comprising:

sampling, by at least one of the one or more computer devices, a document to obtain a plurality of sampled blocks;

generating, by at least one of the one or more computer devices, 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, by at least one of the one or more computer devices, 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.

20. The method of claim 19, further comprising:

comparing 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.

21. The method of claim 19, where the set 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 19, where the set 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 largest, unique checksum values of the checksum values generated for the document.

23. The method of claim 19, 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.

24. The method of claim 19, 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.

25. A non-transitory computer-readable memory device that stores instructions executable by one or more computer devices, the computer-readable memory device comprising:

one or more instructions to sample a document to obtain a plurality of sampled blocks;

one or more instructions to 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

one or more instructions to 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.

26. The computer-readable memory device of claim 25, where the computer-readable memory device further comprises:

one or more instructions 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.

27. The computer-readable memory device of claim 25, where the set of checksum values is a subset of checksum values generated for the document, and

where the computer-readable memory device further comprises:

one or more instructions to select the subset of checksum values as a particular number of smallest, unique checksum values of the checksum values generated for the document.

28. The computer-readable memory device of claim 25, where the set of checksum values is a subset of checksum values generated for the document, and

where the computer-readable memory device further comprises:

one or more instructions to select the subset of checksum values as a particular number of largest, unique checksum values of the checksum values generated for the document.

29. The computer-readable memory device of claim 25, further comprising:

one or more instructions 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.

30. The computer-readable memory device of claim 25, further comprising:

one or more instructions 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.

31. A system, comprising:

one or more computer devices configured 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.

32. The system of claim 31, where, when reducing lengths of the plurality of checksum values, the one or more computer devices are configured to:

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

33. The system of claim 32, where the one or more computer devices hash each of the plurality of checksum values by selecting a quantity of bits of each of the plurality of checksum values.

34. The system of claim 31, where the one or more computer devices are further configured 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.

35. The system of claim 31, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the one or more computer devices are further configured to:

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

36. The system of claim 31, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the one or more computer devices are further configured to:

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

37. The system of claim 31, where the one or more computer devices are further configured 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.

38. The system of claim 37, where the one or more computer devices are further configured to:

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

39. A non-transitory computer-readable memory device that stores instructions executable by one or more computer devices, the computer-readable memory device comprising:

one or more instructions to generate a plurality of checksum values based on a document;

one or more instructions to reduce lengths of the plurality of checksum values to form a plurality of reduced-length checksum values, where each reduced-length of a respective one of a plurality of bits of a fingerprint corresponding to the document; and

one or more instructions to 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.

40. The computer-readable memory device of claim 39, where the one or more instructions to reduce lengths of the plurality of checksum values include one or more instructions to hash each of the plurality of checksum values to a particular size.

41. The computer-readable memory device of claim 40, where the one or more instructions to hash each of the plurality of checksum values include one or more instructions to select a quantity of bits of each of the plurality of checksum values.

42. The computer-readable memory device of claim 39, further comprising:

one or more instructions 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.

43. The computer-readable memory device of claim 39, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the computer-readable memory device further comprises:

one or more instructions to select the subset of checksum values as a particular number of smallest, unique checksum values of the checksum values generated for the document.

44. The computer-readable memory device of claim 39, where the plurality of checksum values is a subset of checksum values generated for the document, and

where the computer-readable memory device further comprises:

one or more instructions to select the subset of the checksum values as a particular number of largest, unique checksum values of the checksum values generated for the document.

45. The computer-readable memory device of claim 39, further comprising:

one or more instructions 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.

46. The computer-readable memory device of claim 45, further comprising:

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

47. A method performed by one or more computer devices, the method comprising:

sampling, by at least one of the one or more computer devices, an input document to obtain a plurality of sampled blocks;

computing, by at least one of the one or more computer devices, 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 corresponding to the input document;

setting, by at least one of the one or more computer devices, a particular bit, of the plurality of bits of the fingerprint, to a particular value to generate the fingerprint,

the particular bit being set to the particular value based on a quantity of checksum values, in the set of checksum values, that corresponds to the address of the particular bit; and

storing, in a memory, the fingerprint as a representation of the input document.

48. The method of claim 47, further comprising:

comparing the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents,

where comparing the fingerprint and the other fingerprint includes calculating a hamming distance between the fingerprint and the other fingerprint, where the input document and the other document are the near-duplicate documents when the hamming distance between the fingerprint and the other fingerprint is below a threshold.

49. The method of claim 47, further comprising:

comparing the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents; and

indexing and storing information regarding only the input document or the other document when the input document and the other document are determined to be the near-duplicate documents based on the comparison of the fingerprint and the other fingerprint.

50. The method of claim 47, further comprising:

reducing a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where reducing the length of the value includes subjecting the value to a hashing algorithm to reduce the length of the value to the particular length.

51. The method of claim 47, further comprising:

reducing a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where reducing the length of the value includes selecting a particular quantity of bits of the value to reduce the length of the value to the particular length.

52. A system, comprising:

one or more computer devices configured to;

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

compute 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 corresponding to the input document;

set a particular bit, of the plurality of bits of the fingerprint, to a particular value to generate the fingerprint,

the particular bit being set to the particular value based on a quantity of checksum values, in the set of checksum values, that corresponds to the address of the particular bit; and

store, in a memory, the fingerprint as a representation of the input document.

53. The system of claim 52, where the one or more computer devices are further configured to:

compare the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents,

where, when comparing the fingerprint and the other fingerprint, the one or more computer devices are configured to calculate a hamming distance between the fingerprint and the other fingerprint, where the input document and the other document are the near-duplicate documents when the hamming distance between the fingerprint and the other fingerprint is below a threshold.

54. The system of claim 52, where the one or more computer devices are further configured to:

compare the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents; and

index and store information regarding only the input document or the other document when the input document and the other document are determined to be the near-duplicate documents based on the comparison of the fingerprint and the other fingerprint.

55. The system of claim 52, where the one or more computer devices are further configured to:

reduce a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where, when reducing the length of the value, the one or more computer devices are configured to subject the value to a hashing algorithm to reduce the length of the value to the particular length.

56. The system of claim 52, where the one or more computer devices further configured to:

reduce a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where, when reducing the length of the value, the one or more computer devices are configured to select a particular quantity of bits of the value to reduce the length of the value to the particular length.

57. A non-transitory computer-readable memory device storing instructions executable by one or more computer devices, the instructions comprising:

one or more instructions to sample an input document to obtain a plurality of sampled blocks;

one or more instructions to compute 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 corresponding to the input document;

one or more instructions to set a particular bit, of the plurality of bits of the fingerprint, to a particular value to generate the fingerprint,

the particular bit being set to the particular value based on a quantity of checksum values, in the set of checksum values, that corresponds to the address of the particular bit; and

one or more instructions to store the fingerprint as a representation of the input document.

58. The computer-readable memory device of claim 57, where the instructions further comprise:

one or more instructions to compare the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents,

where the one or more instructions to compare the fingerprint and the other fingerprint include one or more instructions to calculate a hamming distance between the fingerprint and the other fingerprint, where the input document and the other document are the near-duplicate documents when the hamming distance between the fingerprint and the other fingerprint is below a threshold.

59. The computer-readable memory device of claim 57, where the instructions further comprise:

one or more instructions to compare the fingerprint and another fingerprint to determine whether the input document and another document, associated with the other fingerprint, are near-duplicate documents; and

one or more instructions to index and store information regarding only the input document or the other document when the input document and the other document are determined to be the near-duplicate documents based on the comparison of the fingerprint and the other fingerprint.

60. The computer-readable memory device of claim 57, where the instructions further comprise:

one or more instructions to reduce a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where the one or more instructions to reduce the length of the value include one or more instructions to subject the value to a hashing algorithm to reduce the length of the value to the particular length.

61. The computer-readable memory device of claim 57, where the instructions further comprise:

one or more instructions to reduce a length of a value, in the set of values, to a particular length, where the value, of the particular length, corresponds to an address of one of the plurality of bits of the fingerprint based on the value matching the address of the one of the plurality of bits of the fingerprint,

where the one or more instructions to reduce the length of the value include one or more instructions to select a particular quantity of bits of the value to reduce the length of the value to the particular length.