Compact Indexes for Flexible Top-k Retrieval
This work addresses the computational bottleneck in large-scale information retrieval systems, offering practical improvements for handling terabyte-sized collections, though it builds incrementally on existing indexing methods.
The paper tackles the problem of efficient top-k retrieval for multi-term queries by engineering a self-index system that generalizes the GREEDY approach, achieving significant reductions in ranking time for popular IR relevance measures like TFxIDF and BM25 through document weight reordering and a novel repetition array.
We engineer a self-index based retrieval system capable of rank-safe evaluation of top-k queries. The framework generalizes the GREEDY approach of Culpepper et al. (ESA 2010) to handle multi-term queries, including over phrases. We propose two techniques which significantly reduce the ranking time for a wide range of popular Information Retrieval (IR) relevance measures, such as TFxIDF and BM25. First, we reorder elements in the document array according to document weight. Second, we introduce the repetition array, which generalizes Sadakane's (JDA 2007) document frequency structure to document subsets. Combining document and repetition array, we achieve attractive functionality-space trade-offs. We provide an extensive evaluation of our system on terabyte-sized IR collections.