Inverted Index Compression: Elias-Fano, Variable Byte & Roaring Bitmaps

In web-scale search engines, posting lists can occupy hundreds of gigabytes of RAM. Efficient compression algorithms allow storing millions of DocIDs per megabyte while enabling high-speed SIMD decompression.

1. Variable Byte (VByte) Encoding

VByte encodes integer DocID deltas using 7 bits of data per byte with the 8th bit serving as a continuation flag. Small gaps between consecutive documents compress from 32-bit integers down to a single byte.

2. Elias-Fano Quasi-Succinct Compression

Elias-Fano provides quasi-succinct encoding for monotonically increasing sequences. By splitting integer binary representations into high bits (encoded via unary bitmaps) and low bits (stored uncompressed), Elias-Fano supports O(1) random access skipping and intersection operations directly over compressed data.

3. Roaring Bitmaps for Dense Sets

Roaring Bitmaps partition 32-bit integer sets into 16-bit chunks, dynamically choosing between raw sorted arrays (for sparse regions) and 65,536-bit bitsets (for dense regions). This delivers ultra-fast bitwise AND / OR operations utilized extensively in faceted search filters.