Efficient online index maintenance for contiguous inverted lists
作者:
Highlights:
•
摘要
Search engines and other text retrieval systems use high-performance inverted indexes to provide efficient text query evaluation. Algorithms for fast query evaluation and index construction are well-known, but relatively little has been published concerning update. In this paper, we experimentally evaluate the two main alternative strategies for index maintenance in the presence of insertions, with the constraint that inverted lists remain contiguous on disk for fast query evaluation. The in-place and re-merge strategies are benchmarked against the baseline of a complete re-build. Our experiments with large volumes of web data show that re-merge is the fastest approach if large buffers are available, but that even a simple implementation of in-place update is suitable when the rate of insertion is low or memory buffer size is limited. We also show that with careful design of aspects of implementation such as free-space management, in-place update can be improved by around an order of magnitude over a naïve implementation.
论文关键词:Text indexing,Search engines,Index construction,Index update
论文评审过程:Received 14 April 2005, Accepted 26 September 2005, Available online 8 November 2005.
论文官网地址:https://doi.org/10.1016/j.ipm.2005.09.005