Document matching engine using asymmetric signature generation

• US 7,860,853 B2
• Filed: 02/11/2008
• Issued: 12/28/2010
• Est. Priority Date: 02/14/2007
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: Provilla, Inc. (Trend Micro Inc.)
• Inventors: Huang, Fei, Lin, Yingqiang, Huang, Shu, Ren, Liwei
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US12/069,659
• Publication Number:
  US 20080195606A1
• Time in Patent Office: 1,051 Days
• Field of Search: 707/706, 707/715, 707/748, 707/723, 705/2, 705/26, 705/36
• US Class Current: 707/706
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

An automated method of matching an input document to a set of documents from a document repository. A signature database is stored, the signature database including a document identifier and signatures generated by a first signature generator for each of the set of documents. The input document is received and signatures are generated for the input document using a second signature generator, and the signature database is searched using the signatures generated for the input document. The first and second signature generators are configured such that different numbers of signatures are generated for a same document. Other embodiments, aspects and features are also disclosed.

Claims

1. An automated method of document matching using asymmetrical signature generation, the method comprising:

receiving documents from a document repository;

generating signatures for each of the documents using a first signature generator;

providing the signatures and a document identifier for each of the documents to a signature database;

receiving an input document;

generating signatures for the input document using a second signature generator; and

searching the signature database using the signatures generated for the input document,

wherein the first and second signature generators are configured such that different numbers of signatures are generated for a same document, and

wherein the first and second signature generators each;

receive a document comprising a plurality of characters;

normalize the document to remove non-informative characters from the plurality of characters;

calculate a score for each informative character of the plurality of characters based on an occurrence frequency and distribution in the document;

rank each informative character of the plurality of characters based on the calculated score;

select, from the ranked informative characters, character occurrences; and

generate a signature for each selected character occurrence.

2. The method of claim 1, wherein the first signature generator is configured to generate less signatures from the same document than the second signature generator.

3. The method of claim 2, wherein the first and second signature generators are both configured with a same tolerance level, and wherein the tolerance level relates to an expectation that the method is able to identify document variations.

4. The method of claim 3, wherein the first and second signature generators are both configured to generate an increasing number of signatures as a document text size increases.

5. The method of claim 2, wherein a plurality of the second signature generators are each located at a protection point of a network.

6. The method of claim 5, wherein protection points of the network include interne protocol routers.

7. The method of claim 5, wherein protection points of the network include wireless access points.

8. The method of claim 5, wherein protection points of the network include input/output interfaces of host computers.

9. The method of claim 5, wherein protection points of the network include input/output interfaces of mobile devices.

10. An automated method of matching an input document to a set of documents from a document repository, the method comprising:

storing a signature database including a document identifier and signatures

generated by a first signature generator for each of the set of documents;

receiving an input document;

generating signatures for the input document using a second signature generator; and

searching the signature database using the signatures generated for the input document,

wherein the first and second signature generators are configured such that different numbers of signatures are generated for a same document, and

wherein the first and second signature generators each;

receive a document comprising text;

parse the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;

calculate a score for each token in the token set based on a frequency and distribution of the text in the document;

rank each token in the token set based on the calculated score;

select, from the ranked tokens, a subset of ranked tokens; and

generate a signature for each occurrence of the selected tokens.

11. The method of claim 10, wherein the first signature generator is configured to generate less signatures from the same document than the second signature generator.

12. The method of claim 11, wherein the first and second signature generators are both configured with a same tolerance level, and wherein the tolerance level relates to an expectation that the method is able to identify document variations.

13. The method of claim 12, wherein the first and second signature generators are both configured to generate an increasing number of signatures as a document text size increases.

14. The method of claim 11, wherein the second signature generator is located at a protection point of a network.

15. The method of claim 14, wherein protection points of the network include internet protocol routers.

16. The method of claim 14, wherein protection points of the network include wireless access points.

17. The method of claim 14, wherein protection points of the network include input/output interfaces of host computers.

18. The method of claim 14, wherein protection points of the network include input/output interfaces of mobile devices.

19. A computer readable storage medium structured to store instructions executable by a processor, the instructions when executed causing a processor to:

store a signature database including a document identifier and signatures generated by a first signature generator for each of the set of documents;

receive an input document;

generate signatures for the input document using a second signature generator; and

search the signature database using the signatures generated for the input document,

wherein the first and second signature generators are configured such that different numbers of signatures are generated for a same document, and

wherein the first and second signature generators are each configured to;

receive a document comprising a plurality of characters;

normalize the document to remove non-informative characters from the plurality of characters;

calculate a score for each informative character of the plurality of characters based on an occurrence frequency and distribution in the document;

rank each informative character of the plurality of characters based on the calculated score;

select, from the ranked informative characters, character occurrences; and

generate a signature for each selected character occurrence.

20. A computer apparatus comprising:

a processor configured to execute computer-readable instructions;

memory configured to store data, including said computer-readable instructions; and

a communications system interconnecting said processor and memory,

wherein said computer-readable instructions are configured to store a signature database including a document identifier and signatures generated by a first signature generator for each of the set of documents, receive an input document, generate signatures for the input document using a second signature generator, search the signature database using the signatures generated for the input document, and

wherein the first and second signature generators are configured such that different numbers of signatures are generated for a same document, and

wherein the first and second signature generators are each configured to;

receive a document comprising text;

parse the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;

calculate a score for each token in the token set based on a frequency and distribution of the text in the document;

rank each token in the token set based on the calculated score;

select, from the ranked tokens, a subset of ranked tokens; and

generate a signature for each occurrence of the selected tokens.