Reliability of duplicate document detection algorithms
In a single-signature duplicate document system, a secondary set of attributes is used in addition to a primary set of attributes so as to improve the precision of the system. When the projection of a document onto the primary set of attributes is below a threshold, then a secondary set of attributes is used to supplement the primary lexicon so that the projection is above the threshold.
1. A method comprising:
accessing a first data item;
accessing a primary lexicon of attributes and a secondary lexicon of attributes;
determining, by at least one processor, attributes of the first data item;
determining, by at least one processor, an intersection between the determined attributes and the primary lexicon of attributes;
determining, by at least one processor, whether the intersection is sufficient to meet a target precision for duplicate detection;
if the intersection is sufficient to meet the target precision for duplicate detection, determining a signature for the first data item based on the intersection;
if the intersection is not sufficient to meet the target precision for duplicate detection, adding attributes from the secondary lexicon that intersect with the attributes of the first data item to create an augmented intersection that is sufficient to meet the target precision and determining a signature for the first data item based on the augmented intersection;
comparing the determined signature to a signature of a second data item; and
determining whether the first data item is a duplicate of the second data item based on the comparison.
2. The method of claim 1 , wherein the first data item is part of a collection of documents, the method further comprising removing the first data item from the collection of documents if the first data item is determined to be a duplicate of the second data item.
3. The method of claim 2 , wherein the first data item and the second data item are part of the collection of documents.
4. The method of claim 2 , wherein the collection of documents is a collection of documents stored in a search engine database.
5. The method of claim 2 , wherein the collection of documents comprises one or more documents returned in response to querying a search engine.
6. The method of claim 2 further comprising forwarding the collection of documents to an end user after removing the first data item from the collection of documents.
7. The method of claim 1 , wherein the first data item comprises an uncategorized e-mail and the second data item comprises an e-mail categorized as spam, the method further comprising categorizing the uncategorized e-mail as a spam e-mail if the uncategorized e-mail is determined to be a duplicate of the e-mail categorized as spam.
8. The method of claim 1 , wherein the first data item comprises an item included in a newsfeed.
9. The method of claim 1 , wherein the first data item comprises one or more of textual content, audio content, video content, or image content.
10. The method of claim 1 , wherein the first data item comprises a document and the determined attributes comprise one or more of words, phrases, or clusters of words included in a body of the document.
11. A tangible computer-usable medium having a computer program embodied thereon, the computer program comprising instructions for causing a processor to perform the following operations:
access a first data item;
access a primary lexicon of attributes and a secondary lexicon of attributes; determine attributes of the first data item;
determine an intersection between the determined attributes and the primary lexicon of attributes;
determine whether the intersection is sufficient to meet a target precision for duplicate detection;
if the intersection is sufficient to meet the target precision for duplicate detection, determine a signature for the first data item based on the intersection;
if the intersection is not sufficient to meet the target precision for duplicate detection, add attributes from the secondary lexicon that intersect with the attributes of the first data item to create an augmented intersection that is sufficient to meet the target precision and determine a signature for the first data item based on the augmented intersection;
compare the determined signature to a signature of a second data item; and
determine whether the first data item is a duplicate of the second data item based on the comparison.
12. The medium of claim 11 , wherein the first data item is part of a collection of documents, and the instructions further comprise instructions to remove the first data item from the collection of documents if the first data item is determined to be a duplicate of the second data item.
13. The medium of claim 12 , wherein the first data item and the second data item are part of the collection of documents.
14. The medium of claim 12 , wherein the collection of documents is a collection of documents stored in a search engine database.
15. The medium of claim 12 , wherein the collection of documents comprises one or more documents returned in response to querying a search engine.
16. The medium of claim 12 , wherein the instructions further comprise instructions to forward the collection of documents to an end user after removing the first data item from the collection of documents.
17. The medium of claim 11 , wherein the first data item comprises an uncategorized e-mail and the second data item comprises an e-mail categorized as spam, and the instructions further comprise instructions to categorize the uncategorized e-mail as a spam e-mail if the uncategorized e-mail is determined to be a duplicate of the e-mail categorized as spam.
18. The medium of claim 11 , wherein the first data item comprises an item included in a newsfeed.
19. The medium of claim 11 , wherein the first data item comprises one or more of textual content, audio content, video and image content.
20. The medium of claim 11 , wherein the first data item comprises a document and the determined attributes comprise one or more of words, phrases, and clusters of words included a body of the document.