DETECTING DUPLICATE AND NEAR-DUPLICATE FILES

• US 20080162478A1
• Filed: 03/15/2008
• Published: 07/03/2008
• Est. Priority Date: 01/24/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: PUGH, William, Henzinger, Monika H.
• Granted Patent: US 9,275,143 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Improved duplicate and near-duplicate detection techniques may assign a number of fingerprints to a given document by (i) extracting parts from the document, (ii) assigning the extracted parts to one or more of a predetermined number of lists, and (iii) generating a fingerprint from each of the populated lists. Two documents may be considered to be near-duplicates if any one of their fingerprints match.

Claims

1. A computer-implemented method for determining whether two documents are near-duplicates, the computer-implemented method comprising:

a) for each of the two documents, generating at least two different fingerprints; and

b) determining whether or not the two documents are near-duplicate documents by

1) determining whether or not any one of the at least two fingerprints of a first of the two documents matches any one of the at least two fingerprints of a second of the two documents, and

2) if it is determined that any one fingerprint of the at least two fingerprints of the first of the two documents does match any one fingerprint of the at least two fingerprints of the second of the two documents, then concluding that the two documents are near-duplicates; and

c) using the determination of whether or not the two documents are near-duplicates in at least one of (A) an act of serving search results corresponding to documents, (B) an act of crawling documents, (C) an act of indexing documents, and (D) an act of fixing a broken link to at least one of the two documents.

2. A machine-readable medium having stored thereon a plurality of records, each of the records comprising:

a) a first field for storing a document identifier; and

b) a plurality of lists, each of the plurality of lists containing elements of a document identified by the document identifier stored in the first field, wherein each of the elements are contained in one of the plurality of lists in accordance with a result of hashing the element using a hash function.

3. The machine-readable medium of claim 2 wherein each of the elements of a document is an element that has been extracted from the document.

4. The machine-readable medium of claim 2 wherein each of the elements of a document is a predetermined number of words.

5. The machine-readable medium of claim 2 wherein each of the elements of a document is a predetermined number of sentences.

6. The machine-readable medium of claim 2 wherein each of the elements of a document is a predetermined number of characters.

7. The machine-readable medium of claim 2 wherein each of the elements of a document is a predetermined number of paragraphs.

8. The machine-readable medium of claim 2 wherein each of the elements of a document is a predetermined number of sections.

9. The machine-readable medium of claim 2 wherein each of the elements of a document partially overlaps another of the elements of the document.

10. The machine-readable medium of claim 2 wherein at least some of the plurality of lists include different numbers of elements.

11. The machine-readable medium of claim 2 wherein the at least one of the plurality of records includes at least one list including no elements.

12. The machine-readable medium of claim 2 wherein at least some contiguous elements in a document are not contiguous elements of a list.

13. The machine-readable medium of claim 2 wherein for each of the records, the number of lists is the same.

14. Apparatus for determining whether two documents are near-duplicates, the apparatus comprising:

a) at least one processor; and

b) at least one storage device storing a processor executable program which, when executed by the at least one processor, performs a method including

1) for each of the two documents, generating at least two different fingerprints; and

2) determining whether or not the two documents are near-duplicate documents by

A) determining whether or not any one of the at least two fingerprints of a first of the two documents matches any one of the at least two fingerprints of a second of the two documents, and

B) if it is determined that any one fingerprint of the at least two fingerprints of the first of the two documents does match any one fingerprint of the at least two fingerprints of the second of the two documents, then concluding that the two documents are near-duplicates; and

C) using the determination of whether or not the two documents are near-duplicates in at least one of (i) an act of serving search results corresponding to documents, (ii) an act of crawling documents, (iii) an act of indexing documents, and (iv) an act of fixing a broken link to at least one of the two documents.