Reliability of duplicate document detection algorithms

• US 7,984,029 B2
• Filed: 06/23/2008
• Issued: 07/19/2011
• Est. Priority Date: 02/11/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Alspector, Joshua, Kolcz, Aleksander, Chowdhury, Abdur R.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Nguyen; Cindy
• Application Number:
  US12/144,021
• Publication Number:
  US 20080319995A1
• Time in Patent Office: 1,121 Days
• Field of Search: 707/6, 707/692, 707/698, 707/706, 707727-730, 707/741, 707/742, 707/747, 715/501.1
• US Class Current: 707/698
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

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.

Claims

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.