Decreasing the fragility of duplicate document detecting algorithms

• US 7,624,274 B1
• Filed: 12/21/2004
• Issued: 11/24/2009
• Est. Priority Date: 02/11/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: AOL LLC (Apollo Global Management, Inc.)
• Inventors: Alspector, Joshua, Kolcz, Aleksander, Chowdhury, Abdur R.
• Primary Examiner(s): Cervetti; David García
• Assistant Examiner(s): Louie; Oscar A
• Application Number:
  US11/016,928
• Time in Patent Office: 1,799 Days
• Field of Search: 762/22, 762/26, 713/176, 713/180, 380/59, 715/752, 709204-207
• US Class Current: 713/176
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

In a signature-based duplicate detection system, multiple different lexicons are used to generate a signature for a document that comprises multiple sub-signatures. The signature of an e-mail or other document may be defined as the set of signatures generated based on the multiple different lexicons. When a collection of sub-signatures is used as a document'"'"'s signature, two documents may be considered as being duplicates when a sub-signature generated based on a particular lexicon in the collection for the first document matches a signature generated based on the same lexicon in the collection for the second document.

Claims

1. A method used in detecting a duplicate document, the method comprising:

generating at least a first and second lexicon of attributes, the second lexicon being generated by eliminating a random fraction of attributes from the first lexicon independently of a characteristic of the attributes in the first lexicon;

determining unique attributes in a document;

determining a first set of intersection attributes based on an intersection between the unique attributes in the document and the first lexicon;

determining a second set of intersection attributes based on an intersection between the unique attributes in the document and the second lexicon;

calculating a first sub-signature based on the first set of intersection attributes;

calculating a second sub-signature based on the second set of intersection attributions;

setting a signature of the document to include the first and second sub-signatures; and

accessing a second signature associated with a second document, the second signature including a third sub-signature calculated based on an intersection between unique attributes in the second document and the first lexicon, and a fourth sub-signature calculated based on an intersection between unique attributes in the second document and the second lexicon; and

if the first sub-signature matches the third sub-signature or if the second sub-signature matches the fourth sub-signature, determining that the document and the second document are duplicates.

2. The method of claim 1 wherein generating the first lexicon of attributes and the second lexicon of attributes comprises:

parsing a set of documents to obtain unique attributes in the set of documents;

calculating the normalized inverse document frequency for the unique attributes in the set of documents;

selecting the unique attributes in the set of documents that have a normalized inverse document frequency within a selected range; and

generating the first lexicon from the selected unique attributes.

3. The method of claim 2 wherein the set of documents is a set of known spam e-mails.

4. The method of claim 2 wherein the set of documents is a set of training documents.

5. The method of claim 1 wherein the document is an e-mail.

6. The method of claim 5 wherein the unique attributes comprise tokens.

7. The method of claim 6 wherein the tokens comprise words in a body of the e-mail.

8. The method of claim 5 wherein the e-mail is a known spam e-mail and the signature of the known spam e-mail is a spam signature for use in detecting a duplicate spam e-mail.

9. The method of claim 1 wherein the attributes in the first and second lexicons and the unique attributes comprise words.

10. The method of claim 1 wherein the document is an unknown document and the signature is a query signature, the method further comprising comparing the query signature to known signatures generated from a set of known documents to determine whether the unknown document is a duplicate of one of the set of known documents.

11. The method of claim 10 wherein comparing the query signature to known signatures generated from a set of known documents comprises determining whether a sub-signature in the query signature is the same as a sub-signature in one of the known signatures.

12. The method of claim 11 wherein determining if a sub-signature in the query signature is the same as a sub-signature in one of the known signatures comprises determining whether a sub-signature in the query signature that was generated based on an intersection between the unique tokens and one of the multiple lexicons is the same as a sub-signature in the known signature that was generated based on an intersection between unique tokens in a known document and the same one of the multiple lexicons.

13. A computer-usable medium storing a computer program used in detecting a duplicate document, the computer program comprising instructions for causing a computer to perform the following operations:

generate at least a first and second lexicon of attributes, the second lexicon being generated by eliminating a random fraction of attributes from the first lexicon independently of a characteristic of the attributes in the first lexicon;

determine unique attributes in a document;

determine a first set of intersection attributes based on an intersection between the unique attributes in the document and the first lexicon;

determine a second set of intersection attributes based on an intersection between the unique attributes in the document and the second lexicon;

calculate a first sub-signature based on the first set of intersection attributes;

calculate a second sub-signature based on the second set of intersection attributions;

set a signature of the document to include the first and second sub-signatures; and

access a second signature associated with a second document, the second signature including a third sub-signature calculated based on an intersection between unique attributes in the second document and the first lexicon, and a fourth sub-signature calculated based on an intersection between unique attributes in the second document and the second lexicon; and

if the first sub-signature matches the third sub-signature or if the second sub-signature matches the fourth sub-signature, determine that the document and the second document are duplicates.

14. The medium of claim 13 wherein, to generate the first lexicon of attributes and the second lexicon of attributes, the computer program further comprises instructions for causing a computer to:

parse a set of documents to obtain unique attributes in the set of documents;

calculate the normalized inverse document frequency for the unique attributes in the set of documents;

select the unique attributes in the set of documents that have a normalized inverse document frequency within a selected range; and

generate the first lexicon from the selected unique attributes.

15. The medium of claim 13 wherein the document is an unknown document and the signature is a query signature, the computer program further comprising instructions for causing a computer to compare the query signature to known signatures generated from a set of known documents to determine whether the unknown document is a duplicate of one of the set of known documents.

16. The medium of claim 15 wherein, to compare the query signature to known signatures generated from a set of known documents, the computer program further comprises instructions for causing a computer to determine whether a sub-signature in the query signature is the same as a sub-signature in one of the known signatures.

17. The medium of claim 16 wherein, to determine if a sub-signature in the query signature is the same as a sub-signature in one of the known signatures, the computer program further comprises instructions configured to cause a computer to determine whether a sub-signature in the query signature that was generated based on an intersection between the unique tokens and one of the multiple lexicons is the same as a sub-signature in the known signature that was generated based on an intersection between unique tokens in a known document and the same one of the multiple lexicons.

18. An apparatus used in detecting a duplicate document, the apparatus comprising:

means for generating at least a first and second lexicon of attributes, the second lexicon being generated by eliminating a random fraction of attributes from the first lexicon independently of a characteristic of the attributes in the first lexicon,

one or more processing devices and a computer-readable medium coupled to the one or more processing devices, the medium storing instructions which, when executed by the one or more processing devices, cause the one or more processing devices to perform operations comprising;

determining unique attributes in a document;

determining a first set of intersection attributes based on an intersection between the unique attributes in the document and the first lexicon;

determining a second set of intersection attributes based on an intersection between the unique attributes in the document and the second lexicon;

calculating a first sub-signature based on the first set of intersection attributes;

calculating a second sub-signature based on the second set of intersection attributions;

setting a signature of the document to include the first and second sub-signatures; and

accessing a second signature associated with a second document, the second signature including a third sub-signature calculated based on an intersection between unique attributes in the second document and the first lexicon, and a fourth sub-signature calculated based on an intersection between unique attributes in the second document and the second lexicon; and

if the first sub-signature matches the third sub-signature or if the second sub-signature matches the fourth sub-signature, determining that the document and the second document are duplicates.