Optimizations for Dynamic Inverted Index Maintenance

For free-text search over rapidly evolving corpora, dynamic update of inverted indices is a basic requirement. B-trees are an effective tool in implementing such indices. The Zipfian distribution of postings suggests space and time optimizations unique to this task. In particular, we present two novel optimizations, merge update, which performs better than straight forward block update, and pulsing which significantly reduces space requirements without sacrificing performance. Inverted Indices Most standard free-text search methods in Information Retrieval (IR) can be implemented efficiently through the use of an inverted index. These include standard boolean, extended boolean, proximity, and relevance search algorithms. [7] An inverted index is a data structure that maps a word, or atomic search item, to the set of documents, or set of indexed units, that contain that word --- its postings. An individual posting may be a binary indication of the presence of that word in a document, ..