Scalable document signature search engine
AssigneeTrend Micro Incorporated
InventorsYingqiang Lin, Liwei Ren, Dehua Tan
Life of this patent
Estimating the term…
Abstract
A document signature index and search system is disclosed. The logical structure of the signature index that includes search tables is defined. Also specified is a system of creating, managing and using the signature index. The system includes an index engine and search engine. The search tables are compact in disk usage and suitable for differential computation, making large scale deployment feasible. With the introduction of meta-data and an algorithm of multiple value dual binary searching, the search engine based on the search tables is very efficient in searching for signatures from large search tables which may store millions of signatures. Other embodiments, aspects and features are also disclosed.
Claims11
A computer apparatus for managing an index of documents in a document repository, the apparatus comprising:
- data storage configured to store computer-readable instructions and data;
- a processor configured to execute computer-readable instructions and to access said data storage;
- a file identifier-signature index stored on the data storage, wherein the file identifier-signature index comprises index headers and a signature array, wherein each index header comprises a file identifier for a document file in the document repository, a number of signatures associated with the file identifier, and start and end positions of a block storing the associated signatures in the signature array, wherein the signature array comprises an array of signatures generated from document files in the document repository, and wherein the index headers of the file identifier-signature index are sorted in order by the file identifiers;
- and
- a signature-file identifier index stored on the data storage, wherein the signature-file identifier index comprises signature and file identifier data pairs, wherein the signature and file identifier data pairs of the signature-file identifier index are sorted in order by the signatures;
- a weak searching index comprising weak search table meta data and a sorted signature array, wherein the signature array is sorted in order by values of the signatures and organized into signature blocks depending on values of a first plurality of bytes of the signatures, and wherein the weak search table meta data includes start and end positions of the signature blocks;
- and
- a strong searching index comprising strong search table meta data and a sorted element array, wherein each element of the sorted element array includes a signature and associated file identifier fields, wherein the element array is sorted in order by the values of the signatures and organized into signature blocks depending on the values of the first plurality of bytes of the signatures, and wherein the strong search table meta data includes the start and end positions of the signature blocks.
A computer apparatus for determining whether an input document matches any document in a set of documents, the apparatus comprising:
- data storage configured to store computer-readable instructions and data;
- a processor configured to execute computer-readable instructions and to access said data storage;
- computer-readable code configured to implement a search engine which is configured to apply a weak search if configured with a weak searching index from an index engine and to apply a strong search if configured with a strong searching index from the index engine, wherein both the weak and strong searching indices are derived from the set of documents, wherein the weak searching index comprises weak search table meta data and a sorted signature array, wherein the signature array is sorted in order by values of the signatures and organized into signature blocks depending on values of a first plurality of bytes of the signatures, and wherein the weak search table meta data includes start and end positions of the signature blocks, further wherein the strong searching index comprises strong search table meta data and a sorted element array, wherein each element of the sorted element array includes a signature and associated file identifier fields, wherein the element array is sorted in order by values of the signatures and organized into signature blocks depending on the values of the first plurality of bytes of the signatures, and wherein the strong search table meta data includes the start and end positions of the signature blocks.
Dependencies are inferred from the claim text.