Back to results
US 6,658,423 B1Granted
Detecting duplicate and near-duplicate files
AssigneeGoogle Inc.
InventorsWilliam Pugh, Monika H. Henzinger
Life of this patent
Estimating the term…
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.
Claims38
A method for determining whether documents, in a large collection of documents, are near-duplicates, the method comprising:
- a) for each of at least some of the documents in the large collection of documents, generating at least two fingerprints;
- b) preprocessing the fingerprints to identify any fingerprints that are associated with only one document;
- and
- c) determining whether or not documents are near-duplicate documents based on fingerprints other than those identified as being associated with only one document.
1 more element
An apparatus for determining whether documents, in a large collection of documents, are near-duplicates, the apparatus comprising:
- a) a fingerprint generator for generating, for each of the documents in the large collection of documents, at least two fingerprints;
- b) a preprocessor for identifying any fingerprints that are associated with only one document;
- and
- c) a fingerprint comparison facility for determining whether or not documents are near-duplicate documents based on fingerprints other than those identified as being associated with only one document.
1 more element
A method for clustering documents, the method comprising:
- a) for each of the documents, generating at least two fingerprints;
- and
- b) for each of the documents,
- i) determining whether or not the document is a near-duplicate of any of previously processed documents, based on fingerprints of the documents,
- ii) if it is determined that the document is not a near-duplicate of any previously processed document, then associating the document with a unique cluster identifier, and
- iii) if it is determined that the document is a near-duplicate of a previously processed document, then associating the document with a cluster identifier associated with the previously processed document.
3 more elements
A method for filtering search results to remove near-duplicates, the method comprising:
- a) for each of a predetermined number of candidate search results, determining whether the candidate search result is a near-duplicate of another candidate search result;
- and
- b) if it is determined that the candidate search result is a near-duplicate of another candidate search result, then rejecting the candidate search result
- wherein the act of determining whether a candidate search result is a near-duplicate of another candidate search result includes
- i) comparing a cluster identifier of the candidate search result with that of the other candidate search result, and
- ii) if the cluster identifiers of the two candidate search results match, then concluding that the two candidate search results are near-duplicates, and
- wherein cluster identifiers of the candidate search results are assigned by:
- i) determining whether or not a document corresponding to the candidate search result is a near-duplicate of any of previously processed documents,
- ii) if it is determined that the document corresponding to the candidate search result is not a near-duplicate of any previously processed document, then associating the document with a unique cluster identifier, and
- iii) if it is determined that the document corresponding to the candidate search result is a near-duplicate of a previously processed document, then associating the document corresponding to the candidate search result with a cluster identifier associated with the previously processed document.
7 more elements
A method for determining whether two documents are near-duplicates, the method comprising:
- a) for each of the two documents, generating at least two fingerprints by
- i) extracting parts from the document,
- ii) hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- iii) populating at least two lists with the extracted parts based on their respective hash values, and
- iv) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list;
- and
- b) determining whether or not the two documents are near-duplicate documents based on their fingerprints.
4 more elements
A method, for use in a crawling facility, for reducing processing and bandwidth used, the method comprising:
- a) for each of the documents, generating at least two fingerprints by
- i) extracting parts from the document,
- ii) hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- iii) populating at least two lists with the extracted parts based on their respective hash values, and
- iv) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list;
- b) determining whether or not the two documents are near-duplicate documents based on their fingerprints;
- and
- c) if it is determined that the two documents are near-duplicates, then indicating that one of the two documents is not to be processed during a subsequent crawl.
5 more elements
A method for treating broken links to document, the method comprising:
- a) determining whether a link to a first document is broken;
- b) if it is determined that a link to a first document is broken, determining whether there exists a second document that is a near-duplicate of the first document;
- and
- c) if it is determined that there exists a second document that is a near-duplicate of the first document, then replacing the broken link to the first document with a link to the second document,
- wherein the act of determining whether or not there exists a second document is a near-duplicate of the first document is performed by:
- i) for each of the documents, generating at least two fingerprints by
- A) extracting parts from the document,
- B) hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- C) populating at least two lists with the extracted parts based on their respective hash values, and
- D) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list;
- and
- ii) determining whether or not the two documents are near-duplicate documents based on their fingerprints.
9 more elements
An apparatus for determining whether two documents are near-duplicates, the apparatus comprising:
- a) a fingerprint generator for generating at least two fingerprints for each of the two documents, the fingerprint generator including
- i) an extractor for extracting parts from the document,
- ii) a hashing facility for hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- iii) a list population facility for populating at least two lists with the extracted parts based on their respective hash values, and
- iv) means for determining, for each of the predetermined number of lists, a fingerprint based on the contents of the list;
- and
- b) a comparison facility for determining whether or not the two documents are near-duplicate documents based on their fingerprints.
4 more elements
An improved crawling facility, for reducing processing and bandwidth used, the crawling facility comprising:
- a) a fingerprint generator for generating, for each of the documents, at least two fingerprints, the fingerprint generator including
- i) an extractor for extracting parts from the document,
- ii) a hashing facility for hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- iii) a list population facility for populating at least two lists with the extracted parts based on their respective hash values, and
- iv) means for determining, for each of the predetermined number of lists, a fingerprint based on the contents of the list;
- b) a comparison facility for determining whether or not the two documents are near-duplicate documents based on their fingerprints;
- and
- c) a document processor, wherein if it is determined that the two documents are near-duplicates, then the document processor indicates that one of the two documents is not to be processed during a subsequent crawl.
5 more elements
A machine-readable medium having stored thereon machine-executable instructions which, when executed by a machine:
- a) extract parts from a document,
- ii) hash each of the extracted parts to generate a hash value for each of the extracted parts,
- iii) populate a predetermined number of lists with the extracted parts based on their respective hash values, and
- iv) for each of the predetermined number of lists, determine a fingerprint based on the contents of the list.
1 more element
A method for generating at least two fingerprints for a document comprising:
- a) extracting parts from the document;
- b) hashing each of the extracted parts to generate a hash value for each of the extracted parts;
- c) populating a predetermined number of lists with the extracted parts based on their respective hash values;
- and
- d) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list.
2 more elements
A method comprising:
- a) determining whether there exists a second document that is a near-duplicate of a first document;
- and
- b) indexing the first document but not the second document,
- wherein the act of determining whether or not there exists a second document is a near-duplicate of the first document is performed by:
- i) for each of the documents, generating at least two fingerprints by
- A) extracting parts from the document,
- B) hashing each of the extracted parts to generate a hash value for each of the extracted parts,
- C) populating at least two lists with the extracted parts based on their respective hash values, and
- D) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list;
- and
- ii) determining whether or not the two documents are near-duplicate documents based on their fingerprints.
8 more elements
A method for determining whether two objects are near-duplicates, the method comprising:
- a) for each of the two objects, generating at least two fingerprints by
- i) extracting features from the object,
- ii) hashing each of the extracted features to generate a hash value for each of the extracted features,
- iii) populating at least two lists with the extracted features based on their respective hash values, and
- iv) for each of the predetermined number of lists, determining a fingerprint based on the contents of the list;
- and
- b) determining whether or not the two objects are near-duplicates based on their fingerprints.
4 more elements
A method for determining whether a first document and a second document in a collection of documents are near-duplicates, the method comprising:
- a) for each of the documents in the collection of documents, generating at least two fingerprints;
- and
- b) concluding that the first and second documents are near-duplicates if any one of the at least two fingerprints of the first document matches any one of the at least two fingerprints of the second document,
- wherein documents in the collection of documents without any common fingerprints are not checked to determine whether or not they are near duplicates.
1 more element
Dependencies are inferred from the claim text.