Comparing similarity between documents for filtering unwanted documents

• US 8,874,663 B2
• Filed: 08/28/2009
• Issued: 10/28/2014
• 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.
• Primary Examiner(s): Moise, Emmanuel L
• Assistant Examiner(s): DRABIK, SARAH E
• Application Number:
  US12/550,052
• Publication Number:
  US 20110055332A1
• Time in Patent Office: 1,887 Days
• Field of Search: 709203-207
• 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 comprising:

segmenting at least a portion of a reference document into a plurality of reference shingles, each reference shingle comprising a contiguous portion of the reference document that is of a predetermined length and shorter than the reference document, the plurality of reference shingles comprising a first series of reference shingles and a second series of reference shingles, the first series of reference shingles overlapping and having shifted starting locations relative to the second series of reference shingles;

storing the plurality of reference shingles in a trie structure and counts indicating a number of times each of the plurality of reference shingles comprising the first series of reference shingles and the second series of reference shingles appear in the plurality of reference shingles, a number of levels in the trie structure corresponding to a number of characters in each reference shingle;

segmenting at least a portion of a candidate document into a plurality of candidate shingles comprising a contiguous portion of the candidate document that is of the predetermined length and shorter than the candidate document;

determining a degree of matching between the stored reference shingles and the candidate shingles; and

computing a similarity index representing similarity between the reference document and the candidate document by an equation

2. The method of claim 1, wherein the plurality of candidate shingles comprise a first series of candidate shingles and a second series of candidate shingles, the first series of candidate shingles overlapping and having shifted starting locations relative to the second series of candidate shingles.

3. The method of claim 1, wherein determining the degree of match comprises computing a number of the candidate shingles matching the reference shingles.

4. The method of claim 3, wherein computing the number comprises:

counting a number of candidate shingles matching one of the reference shingles; and

counting a number of the one of the reference shingles appearing in the reference document.

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

6. A computer-implemented method comprising:

receiving a first reference document identified as unwanted;

receiving a communication transmitted through a communication channel;

segmenting at least a portion of the first reference document into a plurality of first reference shingles, each of the first reference shingles a contiguous portion of the first reference document that is of a predetermined length and shorter than the first reference document, the plurality of first reference shingles comprising a first series of reference shingles and a second series of reference shingles, the first series of reference shingles overlapping and having shifted starting locations relative to the second series of reference shingles;

storing the plurality of reference shingles in a trie structure and counts indicating a number of times each of the plurality of reference shingles comprising the first series of reference shingles and the second series of reference shingles appear in the plurality of reference shingles, a number of levels in the trie structure corresponding to a number of characters in each reference shingle;

segmenting at least a portion of the communication into a plurality of candidate shingles comprising a contiguous portion of the communication that is of the predetermined length and shorter than the communication;

determining a degree of matching between the first reference shingles and the candidate shingles;

computing a first similarity index by an equation

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

8. The method of claim 6, further comprising

receiving a second reference document identified as unwanted;

comparing the communication with second reference shingles 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 communication matches the second reference document.

9. The method of claim 6, further comprising:

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

responsive to the frequency remaining above a frequency threshold, comparing all subsequent communications with the first reference document; and

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

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

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

12. A communication system comprising:

a communication processor configured to compare a communication with a plurality of first reference shingles associated with a first reference document, the first reference document identified as unwanted and generate a 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 a communication channel responsive to determining that the communication matches the first reference document based on the first similarity index, the communication processor further configured to;

segment at least a portion of the first reference document into a plurality of reference shingles, each of the first reference shingles comprising a contiguous portion of the first reference document that is of a predetermined length and shorter than the first reference document, the plurality of first reference shingles comprising a first series of reference shingles and a second series of reference shingles, the first series of reference shingles overlapping and having shifted starting locations relative to the second series of reference shingles;

store the plurality of reference shingles in a trie structure and counts indicating a number of times each of the plurality of reference shingles comprising the first series of reference shingles and the second series of reference shingles appear in the plurality of reference shingles, a number of levels in the trie structure corresponding to a number of characters in each reference shingle;

segment at least a portion of the communication into a plurality of candidate shingles comprising a contiguous portion of the communication that is of the predetermined length and shorter than the communication;

determine a degree of matching between the first reference shingles and the candidate shingles; and

compute the first similarity index by an equation

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

14. The communication system of claim 12, wherein the communication processor is further configured to:

compare a communication with second reference shingles associated with a second reference document, the second reference document identified as unwanted, to generate a second similarity index representing similarity between the communication and the second reference document;

determine whether the communication matches the second 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.

15. The communication system of claim 14, further comprising a reference data manager coupled to the communication processor and comprising a computer-readable storage medium storing instructions to:

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

responsive to the frequency remaining above a frequency threshold, compare all subsequent communications with the first reference document; and

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

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

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

18. A non-transitory computer readable storage medium storing instructions, 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 processor;

segment at least a portion of the first reference document into a plurality of first reference shingles, each of the first reference shingles comprising a contiguous portion of the first reference document that is of a predetermined length and shorter than the first reference document, the plurality of first reference shingles comprising a first series of reference shingles and a second series of reference shingles, the first series of reference shingles overlapping and having shifted starting locations relative to the second series of reference shingles;

store the plurality of reference shingles in a trie structure and counts indicating a number of times each of the plurality of reference shingles comprising the first series of reference shingles and the second series of reference shingles appear in the plurality of reference shingles, a number of levels in the trie structure corresponding to a number of characters in each reference shingle;

segment at least a portion of the communication into a plurality of candidate shingles comprising a contiguous portion of the communication that is of the predetermined length and shorter than the communication;

compute a first similarity index by an equation

19. A computer-implemented method comprising:

segmenting at least a portion of a reference document into a plurality of reference shingles, each reference shingle comprising a contiguous portion of the reference document that is of a predetermined length and shorter than the reference document;

storing the plurality of reference shingles in a trie structure and counts indicating a number of times each of the plurality of reference shingles comprising the first series of reference shingles and the second series of reference shingles appear in the plurality of reference shingles, a number of levels in the trie structure corresponding to a number of characters in each reference shingle;

segmenting at least a portion of a candidate document into a plurality of candidate shingles, each candidate shingle comprising a contiguous portion of the candidate document that is of the predetermined length and shorter than the candidate document, the plurality of candidate shingles comprising a first series of candidate shingles and a second series of candidate shingles, the first series of candidate shingles overlapping with and having shifted starting locations relative to the second series of candidate shingles;

determining a degree of matching between the reference shingles and the candidate shingles; and

computing a similarity index representing similarity between the reference document and the candidate document by an equation