US 8,015,162 B2Granted

Detecting duplicate and near-duplicate files

AssigneeGoogle Inc.

InventorMonika H. Henzinger

Life of this patent

Estimating the term…

Loading patent…

Abstract

Near-duplicate documents may be identified by processing an accepted set of documents to determine a first set of near-duplicate documents using a first technique, and processing the first set to determine a second set of near-duplicate documents using a second technique. The first technique might be token order dependent, and the second technique might be order independent. The first technique might be token frequency independent, and the second technique might be frequency dependent. The first technique might determine whether two documents are near-duplicates using representations based on a subset of the words or tokens of the documents, and the second technique might determine whether two documents are near-duplicates using representations based on all of the words or tokens of the documents. The first technique might use set intersection to determine whether or not documents are near-duplicates, and the second technique might use random projections to determine whether or not documents are near-duplicates.

Claims63

Dependent claims

A computer-implemented method comprising:

crawling documents accessible on a network to identify a set of documents, each document in the set of documents comprising a set of token sequence bit strings;
processing the set of documents to determine a first set of near-duplicate documents using a first document similarity technique, wherein the first document similarity technique is token order dependent and token frequency independent;
processing the first set of near-duplicate documents to determine a second set of near-duplicate documents using a second document similarity technique, wherein the second document similarity technique is token order independent and token frequency dependent, and the second set of near-duplicate documents are determined based on a first threshold value;
processing the set of documents to identify a third set of near-duplicate documents using the second document similarity technique, and wherein the third set of near-duplicate documents are identified based on a second threshold value greater than the first threshold value;
and
removing a final set of near-duplicate documents from the set of documents, and then indexing any remaining documents in the set of documents, wherein the final set of near-duplicate documents is a union of the second set of near-duplicate documents and the third set of near-duplicate documents.

3 more elements

A non-transitory machine readable medium having stored thereon machine-executable instructions which, when executed by a machine, cause the machine to perform operations comprising:

crawling documents accessible on a network to identify a set of documents, each document comprising a set of token sequence bit strings;
processing the set of documents to determine a first set of near-duplicate documents using a first document similarity technique, wherein the first document similarity technique is token order dependent and token frequency independent;
processing the first set of near-duplicate documents to determine a second set of near-duplicate documents using a second document similarity technique, wherein the second document similarity technique is token order independent and token frequency dependent, and the second set of near-duplicate documents are determined based on a first threshold value;
processing the set of documents to identify a third set of near-duplicate documents using the second document similarity technique, and wherein the third set of near-duplicate documents are identified based on a second threshold value greater than the first threshold value;
and
removing a final set of near-duplicate documents from the set of documents, and then indexing any remaining documents in the set of documents, wherein the final set of near-duplicate documents is a union of the second set of near-duplicate documents and the third set of near-duplicate documents.

3 more elements

A system comprising:

one or more computers programmed to perform operations comprising:
crawling documents accessible on a network to identify a set of documents, each document comprising a set of token sequence bit strings;
processing the set of documents to determine a first set of near-duplicate documents using a first document similarity technique, wherein the first document similarity technique is token order dependent and token frequency independent;
processing the first set of near-duplicate documents to determine a second set of near-duplicate documents using a second document similarity technique, wherein the second document similarity technique is token order independent and token frequency dependent, and the second set of near-duplicate documents are determined based on a first threshold value;
processing the set of documents to identify a third set of near-duplicate documents using the second document similarity technique, and wherein the third set of near-duplicate documents are identified based on a second threshold value greater than the first threshold value;
and
removing the final set of near-duplicate documents from the set of documents, and then indexing any remaining documents in the set of documents, wherein the final set of near-duplicate documents is a union of the second set of near-duplicate documents and the third set of near-duplicate documents.

4 more elements

Dependencies are inferred from the claim text.