Fast filtering for similarity searches on indexed data
AssigneeInternational Business Machines Corporation
InventorDaisuke Takuma
Life of this patent
Estimating the term…
Abstract
Methods and systems for searching for similar documents include comparing an input index of a requested document to one or more stored indices for respective stored documents to produce a similarity score for each of the stored documents. Each index indicates which of a plurality of queries matched a respective document. The stored documents are filtered to remove dissimilar documents based on a comparison of each respective similarity score to a threshold. A list of any stored documents that remain after said filtering is output.
Claims13
A method for searching for similar documents, comprising:
- generating an input index for a requested document, based on a plurality of queries, each query including one or more text strings, wherein the input index records which queries have at least one text string from the one or more text strings that is present in the input document, wherein the one or more text strings of each of the plurality of queries have a summed probability of matching 50% or fewer of the stored documents;
- comparing the input index of the requested document to one or more stored indices for respective stored documents, to produce a similarity score for each of the stored documents;
- filtering the stored documents to remove dissimilar documents from a list of the stored documents based on a comparison of each respective similarity score to a threshold;
- and
- outputting the list of any stored documents that remain after said filtering.
A non-transitory computer readable storage medium comprising a computer readable program for searching for similar documents, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
- generating an input index for a requested document, based on a plurality of queries, each query including one or more text strings, wherein the input index records which queries have at least one text string from the one or more text strings that is present in the input document, wherein the one or more text strings of each of the plurality of queries have a summed probability of matching 50% or fewer of the stored documents;
- comparing the input index of the requested document to one or more stored indices for respective stored documents, to produce a similarity score for each of the stored documents;
- filtering the stored documents to remove dissimilar documents from a list of the stored documents based on a comparison of each respective similarity score to a threshold;
- and
- outputting the list of any stored documents that remain after said filtering.
A system for searching for similar documents, comprising:
- a user interface configured to receive a requested document and to display similar documents;
- an index module configured to generate an input index for the requested document based on a plurality of queries, each query including one or more text strings, wherein the input index records which queries have at least one text string from the one or more text strings that is present in the input document, wherein the one or more text strings of each of the plurality of queries have a summed probability of matching 50% or fewer of the stored documents;
- a database configured to store a plurality of documents and a respective index for each stored document, each index indicating which of a plurality of queries matched a respective document;
- a similarity module comprising a processor configured to compare an input index of the requested document to one or more stored indices for respective stored documents;
- and
- a search module configured to filter the stored documents to remove dissimilar documents from a list of the stored documents based on a comparison of each respective similarity score to a threshold and to output the list of any stored documents that remain after said filtering for display as the similar documents.
Dependencies are inferred from the claim text.