Back to results
US 10,120,931 B2Granted
Incremental maintenance of inverted indexes for approximate string matching
AssigneeAT&T Intellectual Property I, L.P.
InventorsMarios Hadjieleftheriou, Nick Koudas, Divesh Srivastava
Life of this patent
Estimating the term…
Abstract
In embodiments of the disclosed technology, indexes, such as inverted indexes, are updated only as necessary to guarantee answer precision within predefined thresholds which are determined with little cost in comparison to the updates of the indexes themselves. With the present technology, a batch of daily updates can be processed in a matter of minutes, rather than a few hours for rebuilding an index, and a query may be answered with assurances that the results are accurate or within a threshold of accuracy.
Claims18
A method, comprising:
- calculating a first inverse document frequency for each of a plurality of n-grams in a plurality of strings;
- for each particular n-gram of the plurality of n-grams, creating a sorted list comprising strings, of the plurality of strings, that include the particular n-gram based on the first inverse document frequency for the particular n-gram;
- in response to an update to the plurality of strings, determining n-grams, from the plurality of n-grams, affected by the update;
- for each respective n-gram determined to be affected by the update:
- calculating a second inverse document frequency for the respective n-gram in the updated plurality of strings;
- calculating an error for the respective n-gram based on a difference between the first inverse document frequency for the respective n-gram in the plurality of strings and the second inverse document frequency for the respective n-gram in the updated plurality of strings;
- determining a threshold for the respective n-gram such that the threshold for the respective n-gram is inversely correlated with the inverse document frequency for the respective n-gram;
- determining whether the error for the respective n-gram satisfies the threshold for the respective n-gram;
- and
- in response to determining that the error satisfies the threshold:
- calculating a length for each string affected by the update, and
- re-sorting the sorted list for the respective n-gram based on the update and the length.
9 more elements
A computer readable storage device storing computer program instructions, which, when executed on a processor, cause the processor to perform operations comprising:
- calculating a first inverse document frequency for each of a plurality of n-grams in a plurality of strings;
- for each particular n-gram of the plurality of n-grams, creating a sorted list comprising strings, of the plurality of strings, that include the particular n-gram based on the first inverse document frequency for the particular n-gram;
- in response to an update to the plurality of strings, determining n-grams, from the plurality of n-grams, affected by the update;
- for each respective n-gram determined to be affected by the update:
- calculating a second inverse document frequency for the respective n-gram in the updated plurality of strings;
- calculating an error for the respective n-gram based on a difference between the first inverse document frequency for the respective n-gram in the plurality of strings and the second inverse document frequency for the respective n-gram in the updated plurality of strings;
- determining a threshold for the respective n-gram such that the threshold for the respective n-gram is inversely correlated with the inverse document frequency for the respective n-gram;
- determining whether the error for the respective n-gram satisfies the threshold for the respective n-gram;
- and
- in response to determining that the error satisfies the threshold:
- calculating a length for each string affected by the update, and
- re-sorting the sorted list for the respective n-gram based on the update and the length.
9 more elements
An apparatus comprising:
- a processor;
- and
- a memory to store computer program instructions, the computer program instructions when executed on the processor, cause the processor to perform operations comprising:
- calculating a first inverse document frequency for each of a plurality of n-grams in a plurality of strings;
- for each particular n-gram of the plurality of n-grams, creating a sorted list comprising strings, of the plurality of strings, that include the particular n-gram based on the first inverse document frequency for the particular n-gram;
- in response to an update to the plurality of strings, determining n-grams, from the plurality of n-grams, affected by the update;
- for each respective n-gram determined to be affected by the update:
- calculating a second inverse document frequency for the respective n-gram in the updated plurality of strings;
- calculating an error for the respective n-gram based on a difference between the first inverse document frequency for the respective n-gram in the plurality of strings and the second inverse document frequency for the respective n-gram in the updated plurality of strings;
- determining a threshold for the respective n-gram such that the threshold for the respective n-gram is inversely correlated with the inverse document frequency for the respective n-gram;
- determining whether the error for the respective n-gram satisfies the threshold for the respective n-gram;
- and
- in response to determining that the error satisfies the threshold:
- calculating a length for each string affected by the update, and
- re-sorting the sorted list for the respective n-gram based on the update and the length.
12 more elements
Dependencies are inferred from the claim text.