Elias-Fano encoding
Elias-Fano encodes a nondecreasing integer sequence by storing fixed-width low bits and a unary representation of the high-bit differences.
Layout: For n values in [0, U), choose l = max(0, floor(log2(U/n))) low bits per value. The high-bit stream places its ith one at floor(x_i / 2^l) + i, using zero-based positions. Repeated values are allowed. [1]
Access: Recover x_i from the position of the ith one and its low bits. Efficient selection or skipping requires auxiliary indexing; the two payload streams alone do not promise constant-time queries. [1]
Distinction: This is not Elias gamma or delta coding of each gap. The representation exploits ordering but a single global parameter does not adapt to local clusters. [1] [2]
Relations
Citations
- Sebastiano Vigna, Quasi-Succinct Indices, WSDM 2013, sections 4-7; DOI 10.1145/2433396.2433409
- Giuseppe Ottaviano and Rossano Venturini, Partitioned Elias-Fano Indexes, SIGIR 2014, sections 4-5; DOI 10.1145/2600428.2609615
Sources & caveats
- Primary-source synthesis, not a reproduction of the papers' retrieval benchmarks.
- The linked illustration defines its own stream-ending convention and counts payload bits separately from metadata.