Incremental maintenance of inverted indexes for approximate string matching

Patent metadata

Field	Value
Publication number	US-9514172-B2
Application number	US-201213595270-A
Country	US
Kind code	B2
Filing date	Aug 27, 2012
Priority date	Jun 10, 2009
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

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.

First claim

We claim:

1. A method for limiting updates of inverted indexes in a database, the method comprising:
calculating a first inverse document frequency for each n-gram in a plurality of strings;
calculating a first length for each string in the plurality of strings;
for each n-gram, creating an inverted list comprising strings containing the n-gram;
sorting each inverted list by lengths of the strings in the inverted list;
receiving an update to the plurality of strings;
calculating a second inverse document frequency of n-grams affected by the update;
for each respective n-gram affected by the update:
calculating an error for the respective n-gram based on the second inverse document frequency; and
in response to determining that the error for the respective n-gram satisfies a predefined error threshold for the respective n-gram, wherein the predefined error threshold for the respective n-gram is determined based on a frequency of the respective n-gram in the plurality of strings:
calculating a second length for each string affected by the update, and
re-sorting each inverted list affected by the update based on the second length.

2. The method of claim 1 , further comprising:
updating each inverted list affected by the update to generate a respective updated affected inverted list.

3. The method of claim 2 , further comprising:
answering a query based on the respective updated affected inverted list.

4. The method of claim 1 , wherein the update is an addition of a new string.

5. The method of claim 1 , wherein the update is a deletion of a portion of an existing string.

6. The method of claim 1 , wherein the update is a modification of a portion of a string.

7. The method of claim 1 , wherein each update is buffered and propagated in a batch at regular time intervals.

8. 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 n-gram in a plurality of strings;
calculating a first length for each string in the plurality of strings;
for each n-gram, creating an inverted list comprising strings containing the n-gram;
sorting each inverted list by lengths of the strings in the inverted list;
receiving an update to the plurality of strings;
calculating a second inverse document frequency of n-grams affected by the update;
for each respective n-gram affected by the update:
calculating an error for the respective n-gram based on the second inverse document frequency; and
in response to determining that the error for the respective n-gram satisfies a predefined error threshold for the respective n-gram, wherein the predefined error threshold for the respective n-gram is determined based on a frequency of the respective n-gram in the plurality of strings:
calculating a second length for each string affected by the update, and
re-sorting each inverted list affected by the update based on the second length.

9. The apparatus of claim 8 , wherein the update is an addition of a new string.

10. The apparatus of claim 8 , wherein the update is a deletion of a portion of a string.

11. The apparatus of claim 8 , wherein the update is a modification of a portion of a string.

12. The apparatus of claim 8 , wherein each update is buffered and propagated in a batch at regular time intervals.

13. A non-transitory 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 n-gram in a plurality of strings;
calculating a first length for each string in the plurality of strings;
for each n-gram, creating an inverted list comprising strings containing the n-gram;
sorting each inverted list by lengths of the strings in the inverted list;
receiving an update to the plurality of strings;
calculating a second inverse document frequency of n-grams affected by the update;
for each respective n-gram affected by the update:
calculating an error for the respective n-gram based on the second inverse document frequency; and
in response to determining that the error for the respective n-gram satisfies a predefined error threshold for the respective n-gram, wherein the predefined error threshold for the respective n-gram is determined based on a frequency of the respective n-gram in the plurality of strings:
calculating a second length for each string affected by the update, and
re-sorting each inverted list affected by the update based on the second length.

14. The non-transitory computer readable storage device of claim 13 , wherein the update is an addition of a new string.

15. The non-transitory computer readable storage device of claim 13 , wherein the update is a deletion of a portion of a string.

16. The non-transitory computer readable storage device of claim 13 , wherein the update is a modification of a portion of a string.

17. The non-transitory computer readable storage device of claim 13 , wherein each update is buffered and propagated in a batch at regular time intervals.

Assignees

• Hadjieleftheriou Marios
• Koudas Nick
• Srivastava Divesh
• At & T Ip I Lp

Inventors

• Hadjieleftheriou Marios
• Koudas Nick
• Srivastava Divesh

Classifications

• G06F17/30336 Primary

  Physics · mapped topic

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/319

  Inverted lists · CPC title

• G06F16/328 Primary

  Management therefor · CPC title