US 10,474,650 B1 · In-place updates for inverted indices

Abstract

Implementations provide an indexing system with near-instant updates to an inverted index while maintaining techniques for query optimization. The system may provision empty positions in posting lists to enable in-place updating, without having to rebuild the posting list or append updates to the end of the posting list. For example, a system comprises at least one processor and memory storing an index that includes at least one posting list that maps a term to a set of the documents. The posting list includes an ordered list of documents and has a plurality of open positions within the ordered list. The memory also stores instructions that, when executed by the at least one processor, cause the system to locate an open position of the plurality of open positions for a new document and to insert the new document into the at least one posting list using the open position.

Claims19

Dependent claims

A system comprising:

memory storing an index of documents, the index including at least one posting list that maps a term to a set of the documents, the posting list including an ordered list of documents in a sorted order and having a plurality of open positions within the ordered list, wherein the open positions are provisioned uniformly;
at least one processor;
and
memory storing instructions that, when executed by the at least one processor cause the system to:
locate an open position of the plurality of open positions for a new document, the open position being, of the plurality of open positions, closest to a position that preserves the sorted order of the list, and
insert the new document into the at least one posting list using the open position.

3 more elements

Dependencies are inferred from the claim text.

In-place updates for inverted indices

Life of this patent

In-place updates for inverted indices

Life of this patent

Abstract

Claims19