An Exploration of Postings List Contiguity in Main-Memory Incremental Indexing

For text retrieval systems, the assumption that all data structures reside in main memory is increasingly common. In this context, we present a novel incremental inverted in-dexing algorithm for web-scale collections that directly con-structs compressed postings lists in memory. Designing effi-cient in-memory algorithms requires understanding modern processor architectures: in this paper, we explore the issue of postings list contiguity. Postings lists that occupy con-tiguous memory regions are preferred for retrieval, but main-taining contiguity is costly in terms of speed and complexity. On the other hand, allowing discontiguous index segments simplifies index construction but decreases retrieval perfor-mance. Understanding this tradeoff is our main contribu-tion: We show that co-locating small groups of inverted list segments yields query evaluation performance that is statis-tically indistinguishable from fully-contiguous postings lists. In other words, we can achieve ideal performance with a relatively small amount of effort. 1