Near-duplicate document detection for web crawling

• US 8,548,972 B1
• Filed: 03/16/2012
• Issued: 10/01/2013
• Est. Priority Date: 03/31/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jain, Arvind, Manku, Gurmeet Singh
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US13/422,130
• Time in Patent Office: 564 Days
• Field of Search: 707/706
• US Class Current: 707/706
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system generates a hash value for a fetched document and compares the hash value with a set of stored hash values to identify ones of the stored hash values with a sequence of bit positions, less than all of the bit positions, that match a corresponding sequence of bit positions of the hash value. The system also determines whether any of the identified hash values are substantially similar to the hash value and identify the fetched document as a near-duplicate of another document when one of the identified hash values is substantially similar to the hash value.

Claims

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

determining, by at least one of the one or more devices, a first fingerprint of a first document;

identifying, by at least one of the one or more devices, a second fingerprint of a second document,

the second fingerprint being different than the first fingerprint;

determining, by at least one of the one or more devices, whether the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of the first fingerprint,

the sequence of bit positions being fewer than all of the bit positions in the second fingerprint;

identifying, by at least one of the one or more devices, the first document as a near-duplicate of the second document based on;

determining that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of the first fingerprint, and

determining that the second fingerprint differs from the first fingerprint in at most k bits,

k being an integer greater than zero; and

processing, by at least one of the one or more devices, the first document or the second document based on identifying the first document as a near-duplicate of the second document.

2. The method of claim 1, further comprising:

applying a number of permutations to the first fingerprint to generate a plurality of permutated fingerprints; and

identifying the first document as a near-duplicate of the second document based on determining that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of one of the number of permutated fingerprints.

3. The method of claim 1, where the processing includes:

discarding the first document;

or

ignoring one or more outgoing links in the first document.

4. The method of claim 1, where, when determining the first fingerprint, the method further comprises:

identifying a plurality of features of the first document;

extracting a first set of features, of the plurality of features, of the first document without extracting a second set of features of the plurality of features, the second set of features including stop words;

assigning a weight to each feature of the first set of features; and

determining the first fingerprint based on the first set of features and the assigned weight for each feature of the first set of features.

5. The method of claim 1, further comprising:

identifying the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second document do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

parsing, based on identifying that the first document is not a near-duplicate of the second document, the first document to identify one or more outgoing links.

6. The method of claim 1, further comprising:

identifying the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second fingerprint do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

storing, based on identifying the first document as not being a near-duplicate of the second document, the first fingerprint with the second fingerprint.

7. The method of claim 1, further comprising:

determining the first fingerprint using a hashing technique.

8. A device comprising:

a processor; and

a memory including a plurality of instructions that, when executed by the processor, cause the processor to;

determine a first fingerprint of a first document;

identify a second fingerprint of a second document,

the second fingerprint being different than the first fingerprint;

determine whether the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of the first fingerprint,

the sequence of bit positions being fewer than all of the bit positions in the second fingerprint;

identify the first document as a near-duplicate of the second document, the processor, when identifying the first document as a near-duplicate of the second document, being to;

determine that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of the first fingerprint, and

determine that the second fingerprint differs from the first fingerprint in at most k bits,

k being an integer greater than zero; and

process the first document or the second document based on identifying the first document as a near-duplicate of the second document.

9. The device of claim 8, where the processor is further to:

apply a number of permutations to the first fingerprint to generate a plurality of permutated fingerprints; and

identify the first document as a near-duplicate of the second document based on determining that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of one of the number of permutated fingerprints.

10. The device of claim 8, where, when processing the first document or the second document, the processor is further to:

discard the first document;

or

ignore one or more outgoing links in the first document.

11. The device of claim 8, where, when determining the first fingerprint, the processor is further to:

identify a plurality of features of the first document;

extract a first set of features, of the plurality of features, of the first document without extracting a second set of features of the plurality of features, the second set of features including stop words;

assign a weight to each feature of the first set of features; and

determine the first fingerprint based on the first set of features and the assigned weight for each feature of the first set of features.

12. The device of claim 8, where the processor is further to:

identify the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second document do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

parse, based on identifying that the first document is not a near-duplicate of the second document, the first document to identify one or more outgoing links.

13. The device of claim 8, where the processor is further to:

identify the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second fingerprint do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

store, based on identifying the first document as not being a near-duplicate of the second document, the first fingerprint with the second fingerprint.

14. The device of claim 8, where the processor is further to:

determine the first fingerprint using a hashing technique.

15. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to determine a first fingerprint of a first document;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to identify a second fingerprint of a second document,

the second fingerprint being different than the first fingerprint;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to identify the first document as a near-duplicate of the second document, the one or more instructions to identify the first document as a near-duplicate of the second document including;

one or more instructions to determine that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of the first fingerprint, and

one or more instructions to determine that the second fingerprint differs from the first fingerprint in at most k bits,

k being an integer greater than zero; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to process the first document or the second document based on identifying the first document as a near-duplicate of the second document.

16. The medium of claim 15, further comprising:

one or more instructions to apply a number of permutations to the first fingerprint to generate a plurality of permutated fingerprints; and

one or more instructions to identify the first document as a near-duplicate of the second document based on determining that the second fingerprint includes bits in a sequence of bit positions that match bits in a corresponding sequence of bit positions of one of the number of permutated fingerprints.

17. The medium of claim 15, where the one or more instructions to process the first document or the second document include:

one or more instructions to discard the first document;

or

one or more instructions to ignore one or more outgoing links in the first document.

18. The medium of claim 15, where the one or more instructions to determine the first fingerprint include:

one or more instructions to identify a plurality of features of the first document;

one or more instructions to extract a first set of features, of the plurality of features, of the first document without extracting a second set of features of the plurality of features, the second set of features including stop words;

one or more instructions to assign a weight to each feature of the first set of features; and

one or more instructions to determine the first fingerprint based on the first set of features and the assigned weight for each feature of the first set of features.

19. The medium of claim 15, further comprising:

one or more instructions to identify the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second document do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

one or more instructions to parse, based on identifying that the first document is not a near-duplicate of the second document, the first document to identify one or more outgoing links.

20. The medium of claim 15, further comprising:

one or more instructions to identify the first document as not being a near-duplicate of the second document when the bits in the sequence of bit positions of the second fingerprint do not match the bits in the corresponding sequence of bit positions of the first fingerprint; and

one or more instructions to store, based on identifying the first document as not being a near-duplicate of the second document, the first fingerprint with the second fingerprint.