Efficient computation of document similarity

A system comprising:

• a processor;
• a gram logic configured to cause the processor to produce a gram from a string;
• a candidate logic configured to cause the processor to identify one or more candidate documents based on identifying at least one match between a query gram produced by the gram logic from a query string and a document gram associated with a document, where document grams are stored in an inverted index that relates grams to documents;
• a reconstruction logic configured to cause the processor to produce a partially reconstructed candidate document from one or more entries in the inverted index, the entries being associated with the candidate document, the entries corresponding to one or more query grams that match one or more document grams;
• an edit distance logic configured to cause the processor to compute an edit distance between a first string associated with the query string and a second string associated with the partially reconstructed candidate document, where the edit distance logic is embodied as executable instructions stored on a computer-readable medium;
• a signal logic configured to cause the processor provide data corresponding to the edit distance;
• and
• where the reconstruction logic causes the processor to select a candidate document to partially reconstruct based on one or more of, the number of matches between query grams associated with the query string and document grams associated with the candidate document, a percentage of matches between query grams and document grams, a normalized similarity score that relates a number of matches between query grams and document grams to one or more of, a total number of query grams, and a total number of document grams.

A system, comprising:

• a processor
• a gram logic configured to cause the processor to produce a gram from a string;
• a candidate logic configured to cause the processor to identify one or more candidate documents based on identifying at least one match between a query gram produced by the gram logic from a query string and a document gram associated with a document, where document grams are stored in an inverted index that relates grams to documents;
• a reconstruction logic configured to cause the processor to produce a partially reconstructed candidate document from one or more entries in the inverted index, the entries being associated with the candidate document, the entries corresponding to one or more query grams that match one or more document grams;
• an edit distance logic configured to cause the processor to compute an edit distance between a first string associated with the query string and a second string associated with the partially reconstructed candidate document, where the edit distance logic is embodied as executable instructions stored on a computer-readable medium;
• and
• a signal logic configured to provide data corresponding to the edit distance;
• a query logic configured to cause the processor to receive and store the query string;
• a duplicate removal logic configured to cause the processor to select one of a plurality of redundant matching grams to include in a string to provide to the edit distance logic;
• and
• a rank logic configured to cause the processor to provide an output that describes an ordered set of documents relevant to the query string, the order being based, at least in part, the data provided by the signal logic;
• where a gram includes one or more of, a skipping character, a mismatch character, and a delimiter character, where the edit distance is one of, a Levenshtein distance, a Hamming distance, a proximity score, and a normalized edit distance score, and where an entry in the inverted index includes a document identifier and one or more of, a gram offset, a term offset, and a gram type;
• where the reconstruction logic causes the processor to produce the second string, the second string having one or more of, a known substring, and an unknown substring, the location and content of the known substring being determined by information stored in one or more entries in the inverted index, the information comprising offset information, the one or more entries corresponding to matches between document grams associated with the candidate document and query grams associated with the query string, and
• where the reconstruction logic causes the processor to select a candidate document to partially reconstruct based on one or more of, the number of matches between query grams associated with the query string and document grams associated with the candidate document, a percentage of matches between query grams and document grams, a normalized similarity score that relates a number of matches between query grams and document grams to one or more of, a total number of query grams, and a total number of document grams.

A computer-readable medium having stored thereon instructions that when executed by a processor cause the processor to perform a method, the method comprising:

• identifying a set of candidate documents from a set of indexed documents by comparing a first set of grams to a second set of grams, the first set of grams being related to a query for documents, the second set of grams being related to indexed documents;
• selecting a subset of the set of candidate documents to partially reconstruct based on a similarity score;
• selectively producing a partially reconstructed document from the subset of candidate documents;
• selectively computing an edit distance between a first string related to the first set of grams and a second string related to the partially reconstructed document;
• and
• providing data corresponding to the edit distance.