Reliability of duplicate document detection algorithms

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

generating a primary lexicon of attributes and a secondary lexicon of attributes;

determining unique attributes in a document;

determining an intersection between the unique attributes in the document and the primary lexicon;

determining whether the intersection exceeds a threshold;

when the intersection does not exceed the threshold, adding attributes from the secondary lexicon that intersect with the unique attributes in the document to the intersection to create an augmented intersection that exceeds the threshold; and

calculating a signature for the document based on the augmented intersection.

2. The method of claim 1 further comprising calculating a signature for the document based on the intersection when the intersection exceeds the threshold.

3. The method of claim 1 wherein generating a primary lexicon of attributes and a secondary 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;

defining the primary lexicon as the unique attributes in the range of documents that have a normalized inverse document frequency within a selected range; and

defining the secondary lexicon as the unique attributes in the set of documents that have a normalized inverse document frequency outside the selected range.

4. The method of claim 3 wherein defining the secondary lexicon comprises defining a secondary lexicon as the unique attributes in the set of documents that have a normalized inverse document frequency above the selected range.

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

6. The method of claim 3 wherein the set of documents is a set of training documents.

7. The method of claim 3 wherein determining an intersection between the unique attributes in the document and the primary lexicon comprises:

determining an intersection between the unique attributes in the document and the unique attributes in the set of documents to obtain a set of common attributes;

obtaining a normalized inverse document frequency for the common attributes from the unique attributes in the set of documents;

ranking the common attributes according to the normalized inverse document frequency of the common attributes; and

selecting the common attributes that have a normalized inverse document frequency within the selected range to obtain a set of intersection attributes.

8. The method of claim 7 wherein determining whether the intersection exceeds a threshold comprises:

multiplying a threshold percentage times a number of the unique attributes in the document to obtain a preliminary threshold number;

comparing the preliminary threshold number to a specified threshold number to determine whether the preliminary threshold number exceeds the specified threshold number;

comparing a number of attributes in the set of intersection attributes to the preliminary threshold number when the preliminary threshold number exceeds the specified threshold number; and

comparing a number of attributes in the set of intersection attributes to the specified threshold number when the preliminary threshold number does not exceed the specified threshold number.

9. The method of claim 7 wherein adding attributes from the secondary lexicon that intersect with the unique attributes in the document to the intersection to create an augmented intersection that exceeds the threshold comprises:

determining an additional number of attributes needed to achieve the threshold;

selecting additional attributes equal to the additional number of attributes from the set of common attributes that have a normalized inverse document frequency outside of the specified range; and

adding the additional attributes selected to the set of intersection attributes.

10. The method of claim 9 wherein selecting additional attributes equal to the additional number of attributes from the set of common attributes that have a normalized inverse document frequency outside of the specified range comprises selecting additional attributes from the set of common attributes that have a normalized inverse document frequency above the specified range in an increasing order of the normalized document frequency of the additional attributes.

11. The method of claim 1 wherein the threshold is a minimum number of attributes.

12. The method of claim 1 wherein the threshold is a minimum percentage of the unique attributes in the document.

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

14. The method of claim 13 wherein the wherein the unique attributes comprise tokens.

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

16. The method of claim 1 wherein the attributes in the primary lexicon, the attributes in the secondary lexicon, and the unique attributes comprise words.

17. 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.

18. The method of claim 1 further comprising determining an intersection between the unique attributes in the document and the secondary lexicon.

19. A comparable-user medium having a computer program embodied thereon for use in detecting a duplicate document, the comparator program comprising instructions for causing a computer to perform the following operations:

generate a primary lexicon of attributes and a secondary lexicon of attributes;

determine unique attributes in a document;

determine an intersection between the unique attributes in the document and the primary lexicon;

determining whether the intersection exceeds a threshold;

when the intersection does not exceed the threshold, add attributes from the secondary lexicon that intersect with the unique attributes in the document to the intersection to create an augmented intersection that exceeds the threshold; and

calculate a signature for the document based on the augmented intersection.

20. The medium of claim 19 wherein, to generate a primary lexicon of attributes and a secondary 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;

define the primary lexicon as the unique attributes in the set of documents that have a normalized inverse document frequency within a selected range; and

define the secondary lexicon as the unique attributes in the set of documents that have a normalized inverse document frequency outside the selected range.

21. The medium of claim 20 wherein, to define the secondary lexicon, the computer program further comprises instructions for causing a computer to define the secondary lexicon as the unique attributes in the set of documents that have a normalized inverse document frequency above the selected range.

22. The medium of claim 20 wherein the set of documents is a set of known spam e-mails.

23. The medium of claim 20 wherein, to determine an intersection between the unique attributes in the document and the primary lexicon, the computer program further comprises instructions for causing a computer to:

determine an intersection between the unique attributes in the document and the unique attributes in the set of documents to obtain a set of common attributes;

obtain a normalized inverse document frequency for the common attributes from the unique attributes in the set of documents;

rank the common attributes according to the normalized inverse document frequency of the common attributes; and

select the common attributes that have a normalized inverse downward frequency within the selected range to obtain a set of intersection attributes.

24. The medium of claim 23 wherein, to determine whether the intersection exceeds a threshold, the computer program further comprises instructions for causing a computer to:

multiply a threshold percentage times a number of unique attributes in the document to obtain a preliminary threshold number;

compare the preliminary threshold number to a specific threshold number to determine whether the preliminary threshold number exceeds the specified threshold number;

compare a number of attributes in the set of intersection attributes to the preliminary threshold number when the preliminary threshold number exceeds the specified threshold number; and

compare a number of attributes in the set of intersection attributes to the specified threshold number when the preliminary threshold number does not exceed the specified threshold number.

25. The medium of claim 23 wherein, to add attributes from the secondary lexicon that intersect with the unique attributes in the document to the intersection to create an augmented intersection that exceeds the threshold, the computer program further comprises instructions for causing a computer to:

determine an additional number of attributes needed to achieve the threshold;

select additional attributes equal to the additional number of attributes from the set of common attributes that have a normalized inverse document frequency outside of the specified range; and

add the additional attributes selected to the set of intersection attributes.

26. The medium of claim 25 wherein, to select additional attributes equal to the additional number of attributes from the set of common attributes that have a normalized inverse document frequency outside of the specified range, the computer program further comprises instructions for causing a computer to select additional attributes from the set of common attributes that have a normalized inverse document frequency above the specified range in an increasing order to the normalized document frequency of the additional attributes.

27. The medium of claim 19 wherein the document is an e-mail.

28. The medium of claim 19 wherein the attributes in the primary lexicon, the attributes in the secondary lexicon, and the unique attributes comprise words.

29. The medium of claim 19 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.

30. The medium of claim 19 wherein the computer program further comprises instructions for causing a computer to determine an intersection between the unique attributes in the document and the secondary lexicon.

31. An apparatus for use in detecting a duplicate document, the apparatus comprising:

means for generating a primary lexicon of attributes and a secondary lexicon of attributes;

means for determining unique attributes in a document;

means for determining an intersection between the unique attributes in the document and the primary lexicon;

means for determining whether the intersection exceeds a threshold;

when the intersection does not exceed the threshold, means for adding attributes from the secondary lexicon that intersect with the unique attributes in the document to the intersection to create an augmented intersection that exceeds the threshold; and

means for calculating a signature for the document based on the augmented intersection.