Techniques for Inverted Index Compression
arXiv:1908.10598 · doi:10.1145/3415148
Abstract
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.
Accepted by ACM Computing Surveys (CSUR), 2020
References in corpus (13)
- Decoding billions of integers per second through vectorization
- Better bitmap performance with Roaring bitmaps
- Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
- Compressing Graphs and Indexes with Recursive Graph Bisection
- Asymmetric numeral systems
- Consistently faster and smaller compressed bitmaps with Roaring
- Stream VByte: Faster Byte-Oriented Integer Compression
- Roaring Bitmaps: Implementation of an Optimized Software Library
- Universal Indexes for Highly Repetitive Document Collections
- Vectorized VByte Decoding
- On Optimally Partitioning Variable-Byte Codes
- Re-Pair Compression of Inverted Lists
- On Slicing Sorted Integer Sequences