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

At the scale of billions of web pages, storing uncompressed inverted index posting lists—consisting of 32-bit or 64-bit integer Document IDs, term frequencies, and positional offsets—would require hundreds of terabytes of memory and exhaust disk I/O channels. In modern search engine engineering, query throughput is strictly bound by memory bandwidth. By compressing sorted integer arrays using Delta Encoding ($d$-gaps), Variable Byte (VByte), SIMD-accelerated bit-packing, Elias-Fano quasi-succinct encoding, and Roaring Bitmaps, search engines achieve $4 imes$ to $10 imes$ storage compression while actually increasing query evaluation speeds due to CPU cache residency.

1. Delta Encoding ($d$-Gaps): Transforming Absolute IDs to Small Deltas

Because posting lists are strictly ordered by ascending Document ID (e.g., [104, 108, 115, 120, 145]), storing absolute integers wastes space on high-order bits. Delta Encoding computes the gap between successive IDs: $d_i = ext{DocID}_i - ext{DocID}_{i-1}$ (with $d_0 = ext{DocID}_0$).

• The original list [1002, 1005, 1007, 1015] becomes [1002, 3, 2, 8].
• For terms appearing frequently throughout the corpus (dense posting lists), the vast majority of $d$-gaps are tiny integers ($1, 2, 3$), which require only $2$ to $4$ bits rather than standard $32$ bits.

2. Compression Algorithms: VByte vs. Elias-Fano vs. Roaring Bitmaps

Comparing performance trade-offs across production index encoding formats:

3. Variable Byte (VByte) Encoding Mechanics

Variable Byte encoding encodes an arbitrary-length positive integer into a variable number of 8-bit bytes. The highest bit (bit 7) serves as a continuation flag, while the lower 7 bits store the integer payload:

• If the integer is $le 127$ ($2^7 - 1$), it fits in a single byte: the continuation bit is set to $1$ (e.g., 10000000 | value).
• If the integer exceeds $127$, the lowest 7 bits are written to the current byte with the continuation bit set to $0$, and the remaining bits are shifted right by 7 and written to subsequent bytes until the final byte terminates with a continuation bit of $1$.
• Because decoding operates along strict byte boundaries, VByte avoids complex bit-shifting loops, delivering high decompression speeds across non-vectorized hardware.

4. Elias-Fano Quasi-Succinct Representation

Developed independently by Peter Elias and Robert Fano, the Elias-Fano encoding represents a strictly increasing sequence of $m$ integers bounded by $U$ ($0 le x_0 < x_1 < dots < x_{m-1} < U$) within nearly theoretical information-theoretic minimum space ($m cdot lceillog_2(U/m) ceil + 2m$ bits).

• Bit Splitting: Each integer is split into lower $ell = lfloorlog_2(U/m) floor$ bits and upper $h$ bits.
• Explicit Lower Bit Storage: The lower $ell$ bits are stored contiguously in an uncompressed bit array, enabling instant random access.
• Unary Upper Bit Sequence: The upper bits are represented as a unary sequence of 0s and 1s using a bitvector where the number of 0s before the $i$-th 1 indicates the upper value.
• $O(1)$ NextGEQ Skipping: In inverted index search, traversing posting lists requires jumping to the next document ID greater than or equal to a target ($ ext{NextGEQ}$). Using CPU hardware bit instructions (like POPCNT and TZCNT / _mm_popcnt_u64), Elias-Fano skips directly to the target DocID in constant time without decompressing previous entries.

5. Production Implementation: Variable Byte Compression Engine

The following TypeScript blueprint demonstrates an enterprise Variable Byte (VByte) codec with delta-gap encoding for sorted search engine posting lists:

export class VByteCodec {
  // Compress an ascending array of DocIDs using Delta Encoding + VByte
  static compressPostingList(docIds: number[]): Uint8Array {
    const bytes: number[] = [];
    let lastDocId = 0;

    for (const docId of docIds) {
      let dGap = docId - lastDocId;
      lastDocId = docId;

      // Encode d-gap into 7-bit chunks with bit 7 as continuation bit
      while (dGap >= 128) {
        bytes.push(dGap & 0x7f); // Lower 7 bits, continuation bit = 0
        dGap >>>= 7;
      }
      bytes.push(dGap | 0x80); // Final byte has bit 7 set to 1
    }

    return new Uint8Array(bytes);
  }

  // Decompress VByte byte array back into original sorted DocIDs
  static decompressPostingList(buffer: Uint8Array): number[] {
    const docIds: number[] = [];
    let lastDocId = 0;
    let currentNumber = 0;
    let shift = 0;

    for (let i = 0; i < buffer.length; i++) {
      const byte = buffer[i];
      if ((byte & 0x80) === 0) {
        // Continuation bit is 0: more bytes follow
        currentNumber |= (byte & 0x7f) << shift;
        shift += 7;
      } else {
        // Continuation bit is 1: terminal byte for this number
        currentNumber |= (byte & 0x7f) << shift;
        const docId = lastDocId + currentNumber;
        docIds.push(docId);
        lastDocId = docId;

        // Reset for next number
        currentNumber = 0;
        shift = 0;
      }
    }

    return docIds;
  }
}