Reliability of duplicate document detection algorithms

• US 8,429,178 B2
• Filed: 07/18/2011
• Issued: 04/23/2013
• Est. Priority Date: 02/11/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Alspector, Joshua, Kolcz, Aleksander, Chowdhury, Abdur R.
• Primary Examiner(s): Nguyen, Cindy
• Application Number:
  US13/185,238
• Publication Number:
  US 20110276646A1
• Time in Patent Office: 645 Days
• Field of Search: 707/754, 709/206, 709/207
• US Class Current: 707/754
• 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:

receiving an electronic message that is addressed to a user;

determining, by at least one processor, one or more attributes of the electronic message;

determining, by the at least one processor, an intersection between the determined one or more attributes of the electronic message and a first lexicon of attributes that are associated with spam electronic messages;

determining, by the at least one processor, whether the intersection exceeds a precision threshold, the precision threshold indicating the reliability of the intersection between the determined one or more attributes of the electronic message and the first lexicon of attributes; and

if the intersection exceeds the precision threshold;

determining an electronic message signature based on the intersection, and

comparing the electronic message signature to each of a plurality of signatures associated with spam electronic messages.

2. The method of claim 1, further comprising if the intersection does not exceed the precision threshold:

adding attributes from a second lexicon associated with spam electronic messages that intersect with the one or more attributes of the electronic message to create an augmented intersection that is sufficient to meet the target precision;

determining an electronic message signature based on the augmented intersection;

comparing the electronic message signature based on the augmented intersection to each of a plurality of signatures associated with spam electronic message; and

removing the electronic message without sending the electronic message to the user based on the comparisons.

3. The method of claim 1, further comprising:

determining that the electronic message is a spam electronic message based on the comparisons; and

removing the electronic message without sending the electronic message to the user.

4. The method of claim 1, further comprising:

determining that the electronic message is a spam electronic message based on the comparisons; and

sending the electronic message to the user with a spam electronic message indicator.

5. The method of claim 1, further comprising:

determining that the electronic message is not a spam electronic message based on the comparisons; and

sending the electronic message to the user with a legitimate electronic message indicator.

6. The method of claim 1, wherein the determined one or more attributes comprise one or more of words, phrases, or clusters of words associated with the electronic message.

7. The method of claim 1, wherein the one or more attributes are determined based on non-text media associated with the electronic message.

8. The method of claim 1, wherein receiving the electronic message comprises receiving an e-mail at an e-mail server associated with at least one of an e-mail domain, a portion of an e-mail domain, or multiple e-mail domains.

9. A computer system, comprising:

one or more processors; and

a memory having instructions, that when executed by the one or more processors, cause the one or more processors to perform the operations of;

receiving an electronic message that is addressed to a user;

determining one or more attributes of the electronic message;

determining an intersection between the determined one or more attributes and of the electronic message a first lexicon of attributes that are associated with spam electronic messages;

determining whether the intersection exceeds a precision threshold, the precision threshold indicating the reliability of the intersection between the determined one or more attributes of the electronic message and the first lexicon of attributes; and

if the intersection exceeds the precision threshold, determining an electronic message signature based on the intersection, and comparing the electronic message signature to each of a plurality of signatures associated with spam electronic messages.

10. The system of claim 9, wherein the operations performed by the one or more processors further comprise if the intersection does not exceed the precision threshold:

adding attributes from a second lexicon associated with spam electronic messages that intersect with the one or more attributes of the electronic message to create an augmented intersection that is sufficient to meet the target precision;

determining, by the at least one processor, an electronic message signature based on the augmented intersection;

comparing the electronic message signature based on the augmented intersection to each of a plurality of signatures associated with spam electronic messages; and

removing the electronic message without sending the electronic message to the user based on the comparisons.

11. The system of claim 9, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is a spam electronic message based on the comparisons; and

removing the electronic message without sending the electronic message to the user.

12. The system of claim 9, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is a spam electronic message based on the comparisons; and

sending the electronic message to the user with a spam electronic message indicator.

13. The system of claim 9, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is not a spam electronic message based on the comparisons; and

sending the electronic message to the user with a legitimate electronic message indicator.

14. The system of claim 9, wherein the determined one or more attributes comprise one or more of words, phrases, or clusters of words associated with the electronic message.

15. The system of claim 9, wherein the one or more attributes are determined based on non-text media associated with the electronic message.

16. The system of claim 9, wherein receiving the electronic message comprises receiving an e-mail at an e-mail server associated with at least one of an e-mail domain, a portion of an e-mail domain, or multiple e-mail domains.

17. A non-transitory computer-readable medium storing instructions, the instructions operable to cause one or more computer processors to perform operations, comprising:

receiving an electronic message that is addressed to a user;

determining one or more attributes of the electronic message;

determining an intersection between the determined one or more attributes of the electronic message and a first lexicon of attributes that are associated with spam electronic messages;

determining whether the intersection exceeds a precision threshold, the precision threshold indicating the reliability of the intersection between the determined one or more attributes of the electronic message and the first lexicon of attributes; and

if the intersection exceeds the precision threshold determining an electronic message signature based on the intersection, and comparing the electronic message signature to each of a plurality of signatures associated with spam electronic messages.

18. The non-transitory computer-readable medium of claim 17, wherein the instructions are further operable to cause one or more computer processors to perform further operations if the intersection does not exceed the precision threshold, comprising:

adding attributes from a second lexicon associated with spam electronic messages that intersect with the one or more attributes of the electronic message to create an augmented intersection that is sufficient to meet the target precision;

determining, by the at least one processor, an electronic message signature based on the augmented intersection;

comparing the electronic message signature based on the augmented intersection to each of a plurality of signatures associated with spam electronic messages; and

removing the electronic message without sending the electronic message to the user based on the comparisons.

19. The non-transitory computer-readable medium of claim 17, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is a spam electronic message based on the comparisons; and

removing the electronic message without sending the electronic message to the user.

20. The non-transitory computer-readable medium of claim 17, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is a spam electronic message based on the comparisons; and

sending the electronic message to the user with a spam electronic message indicator.

21. The non-transitory computer-readable medium of claim 17, wherein the operations performed by the one or more processors further comprise:

determining that the electronic message is not a spam electronic message based on the comparisons; and

sending the electronic message to the user with a legitimate electronic message indicator.

22. The non-transitory computer-readable medium of claim 17, wherein the determined attributes comprise one or more of words, phrases, or clusters of words associated with the electronic message.

23. The non-transitory computer-readable medium of claim 17, wherein the attributes are determined based on non-text media associated with the electronic message.

24. The non-transitory computer-readable medium of claim 17, wherein receiving the electronic message comprises receiving an e-mail at an e-mail server associated with at least one of an e-mail domain, a portion of an e-mail domain, or multiple e-mail domains.