System and method for detecting duplicate and similar documents

• US 7,139,756 B2
• Filed: 01/22/2002
• Issued: 11/21/2006
• Est. Priority Date: 01/22/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Coden, Anni, Brown, Eric W., Cooper, James W.
• Primary Examiner(s): Rimell, Sam
• Assistant Examiner(s): BETIT, JACOB F
• Application Number:
  US10/054,366
• Publication Number:
  US 20030172066A1
• Time in Patent Office: 1,764 Days
• Field of Search: 707/4, 707/531, 707/101, 707/7, 707/203, 707/2, 707/5, 707/6, 707/102, 707/3, 707/100, 707/103, 380/23, 380/30
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and a method are described for rapidly determining document similarity among a set of documents, such as a set of documents obtained from an information retrieval (IR) system. A ranked list of the most important terms in each document is obtained using a phrase recognizer system. The list is stored in a database and is used to compute document similarity with a simple database query. If the number of terms found to not be contained in both documents is less than some predetermined threshold compared to the total number of terms in the document, these documents are determined to be very similar. It is shown that these techniques may be employed to accurately recognize that documents, that have been revised to contain parts of other documents, are still closely related to the original document. These teachings further provide for the computation of a document signature that can then be used to make a rapid comparison between documents that are likely to be identical.

Claims

1. A method for processing data representing documents, comprising:

for individual documents of a set of documents, executing a software program to obtain a list of terms found in each document;

comparing the list of terms for a first document to the list of terms for a second document;

declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of terms are found in each of the lists of the first document and the second document; and

wherein the step of comparing includes a preliminary step of sorting the documents into a document list in order of increasing size, and where the step of comparing compares the list of terms for a given document with the list of terms for the for the next larger-documents in the document list.

2. A method for processing data representing documents, comprising:

for individual documents of a set of documents, executing a software program to obtain a list of salient terms found in each document;

comparing the list of salient terms for a first document to the list of salient terms for a second document; and

declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of salient terms are found in each of the lists of the first document and the second document,

wherein the comparing includes sorting the documents into a document list in order of increasing size, and where the step of comparing compares the list of salient terms for a given document with the list of salient terms for the next larger-documents in the document list.

3. A method as in claim 2, wherein if the predetermined number is 90% of the salient terms or greater the first document is declared to be substantially identical to the second document.

4. A method as in claim 2, wherein the set of documents is obtained in response to a search query made to a data communications network.

5. A method as in claim 2, and further comprising storing the lists of salient terms in a database.

6. A method as in claim 2, and further comprising computing a signature for each document, and storing the computed document signature.

7. A method as in claim 2, and further comprising computing a signature for each document, and storing the computed document signature in association with the list of salient terms for each document.

8. A method as in claim 2, wherein the step of executing a software program assigns to each salient term a collection-level importance ranking or Information Quotient (IQ), and wherein the IQ is considered during the step of comparing.

9. A method for processing data representing documents, comprising:

for individual documents of a set of documents, executing a software program to obtain a list of terms found in each document;

comparing the list of terms for a first document to the list of terms for a second document;

declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of terms are found in each of the lists of the first document and the second document; and

wherein the step of comparing includes a preliminary step of sorting the documents into a document list in order of increasing size, and where the step of comparing compares the list of terms of a given document only with the list of terms of another document in the list that is no more than a predetermined amount larger than the given document.

10. A method for processing data representing documents, comprising:

for individual ones of documents, executing a software program to obtain a list of salient terms found in each document;

computing a document signature for each document from the list of salient terms obtained for the document;

comparing the document signature for a first document to the document signature for a second document; and

declaring the first document to be substantially identical to the second document if the document signatures are substantially equal,

wherein the step of comparing includes a preliminary step of sorting the documents into a document list in order of increasing size, and where the step of comparing compares the list of salient terms of a given document with the list of salient terms of the next larger-documents in the document list.

11. A method as in claim 10, wherein the step of computing a document signature computes a hash code for each term of the list of salient terms, and then sums all of the hash codes to form the document signature.

12. A method as in claim 10, wherein the documents are obtained in response to a search query made to a data communications network, and where the steps of comparing and declaring are executed in substantially real time as the documents are returned by the query.

13. A method as in claim 10, wherein the documents are obtained in response to a search query made to a data communications network, where the steps of comparing and declaring are executed in substantially real time as the documents are received from the data communications network, and for a case where a received document is found to be substantially identical to an already received document, returning only one of the documents in response to the search query.

14. A method as in claim 10, and further comprising storing the computed document signatures in a database.

15. A method as in claim 10, and further comprising storing the computed document signature in association with the list of salient terms for each document.

16. A system for processing data representing documents comprising,

for individual documents of a set of documents, a processor that executes a software program to obtain a list of terms found in each document and compares the list of terms for a first document to the list of terms for a second document, said processor operating to declare the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of terms are found in each of the lists of the first document and the second document;

and wherein said processor is further operable, before comparing the lists of terms, to sort the documents into a document list in order of increasing size, and to then compare the list of terms of a given document with the list of terms of a next larger documents in the document list.

17. A system for processing data representing documents comprising, for individual documents of a set of documents, a processor that executes a software program to obtain a list of salient terms found in each document and that compares the list of salient terms for a first document to the list of salient terms for a second document, said processor, in response to executing the software program, declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of salient terms are found in each of the lists of the first document and the second document, wherein said comparing includes sorting the documents into a document list in order of increasing size, and where said comparing compares the list of salient terms for a given document with the the list of salient terms for the next larger-documents in the document list.

18. A system as in claim 17, wherein if the predetermined number is 90% of the salient terms or greater the first document is declared to be substantially identical to the second document.

19. A system as in claim 17, wherein the set of documents is obtained in response to a search query made to a data communications network.

20. A system as in claim 17, and further comprising a memory containing a database for storing the lists of salient terms.

21. A system as in claim 17, said processor being further operable for computing a signature for each document, and further comprising a memory for storing the computed document signature.

22. A system as in claim 17, said processor being further operable for computing a signature for each document, and further comprising a memory for storing the computed document signature in association with the list of salient terms for each document.

23. A system as in claim 17, wherein said processor, when executing the software program, assigns to each term a collection-level importance ranking or Information Quotient (IQ), and wherein the IQ is considered by said processor when comparing the list of salient terms for the first document to the list of salient terms for the second document.

24. A system for processing data representing documents comprising,

for individual documents of a set of documents, a processor that executes a software program to obtain a list of terms found in each document and compares the list of terms for a first document to the list of terms for a second document, said processor, in response to executing the software program, declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of terms are found in each of the lists of the first document and the second document;

and wherein said processor, before comparing the lists of terms, sorts the documents into a document list in order of increasing size, and compares the list of terms for a given document only with the list of terms for another document in the list that is no more than a predetermined amount larger than the given document.

25. A system for processing data representing documents, comprising, for individual documents of a set of documents, a processor that executes a software program to obtain a list of salient terms found in each document, computes a document signature for each document from the list of salient terms obtained for the document;

compares the document signature for a first document to the document signature for a second document; and

declares the first document to be substantially identical to the second document if the document signatures are equal, wherein said comparing includes sorting the documents into a document list in order of increasing size, and where said comparing compares the list of salient terms for a given document with the list of salient terms for the next larger-documents in the document list.

26. A system as in claim 25, wherein said processor computes the document signature by computing a hash code for each salient term of the list of salient terms, and summing all of the hash codes to form the document signature.

27. A system as in claim 25, wherein the documents are obtained in response to a search query made to a data communications network, and where the processor executes the comparing and declaring functions in substantially real time as the documents are returned by the query.

28. A system as in claim 25, wherein the documents are obtained in response to a search query made to a data communications network, where the processor executes comparing and declaring functions in substantially real time as the documents are received from the data communications network, and for a case where a received document is found to be substantially identical to an already received document, said processor returns only one of the documents in response to the search query.

29. A system as in claim 25, and further comprising a memory containing a database for storing the computed document signatures.

30. A system as in claim 29, and further comprising storing the computed document signature in association with the list of terms for each document.

31. A computer program recorded on a computer-readable media, said computer program comprising instructions for directing a data processor to process data representing documents by, for individual documents of a set of documents, obtaining a list of salient terms found in each document;

comparing the list of salient terms for a first document to the list of salient terms for a second document; and

declaring the first document to be substantially identical to, or substantially similar to, the second document if some predetermined number of salient terms are found in each of the lists of the first document and the second document, wherein said comparing includes sorting the documents into a document list in order of increasing size, and where said comparing compares the list of salient terms for a given document with the list of salient terms for the next larger-documents in the document list.

32. A computer program recorded on a computer-readable media, said computer program comprising instructions for directing a data processor to process data representing documents by, for individual ones of documents, obtaining a list of salient terms found in each document;

computing a document signature for each document from the list of salient terms obtained for the document;

comparing the document signature for a first document to the document signature for a second document; and

declaring the first document to be substantially identical to the second document if the document signatures are equal, wherein said comparing includes sorting the documents into a document list in order of increasing size, and where said comparing compares the list of salient terms for a given document with the list of salient terms for the next larger-documents in the document list.

33. A computer program as in claim 32, wherein the document signature is computed by computing a hash code for each salient term of the list of salient terms, and summing together all of the hash codes to form the document signature.