COMPARING SIMILARITY BETWEEN DOCUMENTS FOR FILTERING UNWANTED DOCUMENTS

• US 20110055332A1
• Filed: 08/28/2009
• Published: 03/03/2011
• Est. Priority Date: 08/28/2009
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Stein, Christopher A.
• Granted Patent: US 8,874,663 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A mechanism for efficiently determining similarity between documents. A set of reference data items is generated by processing a reference document. A similarity index representing similarity between a candidate document and the reference documents is obtained by counting segments of the candidate document matching the reference data items. The candidate document is a message transmitted in a communication system where the message is compared against one or more reference documents representing unwanted messages to filter and block unwanted messages from being transmittal or propagated.

Claims

1. A computer-implemented method of determining similarity between a reference document and a candidate document, comprising:

segmenting the reference document into a plurality of reference data items;

segmenting the candidate document into a plurality of document data items;

computing a count representing a number of document data items matching the reference data items; and

computing a similarity index representing similarity between the reference document and the candidate document based on the count.

2. The method of claim 1, wherein segmenting the reference document comprises segmenting the reference document at different locations in the reference document to generate shingles of a predetermined length.

3. The method of claim 1, wherein segmenting the candidate document comprises segmenting the candidate document at different locations in the candidate document to generate shingles of a predetermined length.

4. The method of claim 1, wherein computing the count comprises counting a number of unique document data items that match unique reference data items.

5. The method of claim 1, wherein computing the count comprises:

counting a number of document data item matching a reference data item; and

counting a number of the reference data item appearing in the reference document.

6. The method of claim 1, wherein the reference document is a communication identified as unwanted, and the candidate document is a communication to be transmitted via a communication channel.

7. A computer-implemented method of filtering unwanted communications, comprising:

receiving a reference document identified as unwanted;

receiving a communication transmitted through a communication channel;

comparing the communication with a first set of reference data items associated with the reference document to generate a first similarity index, the first similarity index representing similarity between the communication and the first reference document;

determining whether the communication matches the first reference document based on the first similarity index; and

designating the communication to be blocked from further transmission through the communication channel responsive to determining that the communication matches the first reference document.

8. The method of claim 7, wherein comparing the communication comprises:

segmenting the communication into a plurality of document data items;

comparing each document data item with the first set of reference data items for a match;

incrementing a match count responsive to one of the plurality of document data items matching a data item in the first set of reference data item; and

computing the first similarity index based at least on the match count, a number of the document data items, and a number of data in the first set of reference data items.

9. The method of claim 7, further comprising generating the first set of reference data items by segmenting the first reference document at different locations.

10. The method of claim 7, further comprising storing the first set of reference data items in a trie data structure.

11. The method of claim 7, wherein comparing the communication comprises:

generating shingles of a predetermined length by segmenting the communication at different locations in the communication; and

for each shingle generated by segmentation, determining if the shingle matches any data items in the first set of reference data items.

12. The method of claim 7, wherein the communication comprises an email, a web document, an instant message or a text message.

13. The method of claim 7, further comprising

receiving a second reference document identified as unwanted;

comparing the communication with a second set of the reference data items associated with the second reference document to generate a second similarity index, the second similarity index representing similarity between the communication and the second reference document;

determining whether the communication matches the second reference document based on the second similarity index; and

designating the communication to be blocked from further transmission through the communication channel responsive to determining that the message matches the second reference document.

14. The method of claim 7, further comprising:

computing frequency of a plurality of communications determined as matching the first document;

responsive to the frequency remaining above a frequency threshold, comparing all subsequent communications with the first set of reference data items; and

responsive to the frequency not remaining above the frequency threshold, comparing a subset of subsequent communications with the first set of reference data items.

15. The method of claim 14, further comprising resuming comparing the first set of reference data items with all subsequent communications responsive to at least one communication in the subset of subsequent communications being determined as matching the first document.

16. The method of claim 7, further comprising determining whether to present the communication for manual review based on the first similarity index.

17. A communication system for filtering unwanted communications, comprising:

an communication processor configured to compare a communication with a first set of reference data items associated with a first reference document, the reference document identified as unwanted, to generate a first similarity index, the first similarity index representing similarity between the communication and the first reference document, the communication processor configured to determine whether the communication matches the first reference document based on the first similarity index, the communication processor configured to designate the communication to be blocked from further transmission through the communication channel responsive to determining that the communication matches the first reference document; and

a communication module configured to receive communications to be transmitted and transmit the communication responsive to one or more recipients responsive to the communication not being blocked by the communication processor.

18. The communication system of claim 17, wherein the communication processor is configured to:

segment the communication into a plurality of document data items;

compare each document data item with the first set of reference data items for a match;

increment a match count responsive to one of the plurality of document data items matching a data item in the first set of reference data item; and

compute the first similarity index based at least on the match count, a number of the document data items, and a number of data in the first set of reference data items.

19. The communication system of claim 17, further comprising a reference document processor configured to generate the first set of reference data items by segmenting the first reference document at different locations.

20. The communication system of claim 19, further comprising a reference data store configured to store the first set of reference data items in a trie data structure.

21. The communication system of claim 17, wherein the communication processor is configured to:

generate shingles by segmenting the communication into shingles of a predetermined length at different locations in the communication; and

for each shingle generated by segmentation, determine if the shingle matches any data item in the first set of reference data items.

22. The communication system of claim 17, wherein the communication comprises an email, a web document, an instant message or a text message.

23. The communication system of claim 17, wherein the communication processor is further configured to:

compare a communication with a second set of reference data items associated with a second reference document, the reference document identified as unwanted, to generate a second similarity index, the first similarity index representing similarity between the communication and the first reference document;

determine whether the communication matches the first reference document based on the second similarity index; and

designate the communication to be blocked from further transmission through the communication channel responsive to determining that the communication matches the second reference document.

24. The communication system of claim 23, further comprising a reference data manager configured to:

compute frequency of a plurality of communications determined as matching the first document;

responsive to the frequency remaining above a frequency threshold, compare all subsequent communications with the first set of reference data items; and

responsive to the frequency not remaining above the frequency threshold, compare a subset of subsequent communications with the first set of reference data items.

25. The computer system of claim 24, wherein the reference data manager is configured to resume comparing the first set of reference data items with all subsequent communications responsive to at least one communication in the subset of subsequent communications determined as matching the first document.

26. The computer system of claim 24, wherein the reference data manager is configured to determine whether to present the communication for manual review based on the first similarity index.

27. A computer readable storage medium storing instructions for filtering unwanted communications, the instructions when executed by a processor, cause the processor to:

receive a first reference document identified as unwanted;

receive a communication to be routed or published in a communication channel controlled by the computing device;

compare the communication with a first set of the reference data items associated with the first reference document to generate a first similarity index, the first similarity index representing similarity between the communication and the first reference document;

determine whether the communication matches the first reference document based on the first similarity index; and

designate the communication to be blocked from further transmission through the communication channel responsive to determining that the communication matches the first reference document.

28. The computer readable storage medium of claim 27, wherein instructions to compare the communication comprise instructions to:

segment the communication into a plurality of document data items;

compare each document data item with the first set of reference data items for a match;

increment a match count responsive to one of the plurality of document data items matching a data item in the first set of reference data item; and

compute the first similarity index based at least on the match count, a number of the document data items, and a number of data in the first set of reference data items.

29. A computer-implemented method of filtering unwanted communications, comprising steps for:

receiving a communication transmitted through a communication channel;

determining whether the communication is similar within a predefined tolerance to a reference document identified as unwanted; and

designate the communication to be blocked from access by one or more intended recipients responsive to determining that the message is similar to the reference document.

30. The method of claim 29, wherein the communication comprises at least one of an email, a web document, a feed, a stream, an instant message or a text message.