elias-fano · shipping · also Elias-Fano representation

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

related
Partitioned Elias-Fano, Roaring bitmap, Lossless compression, Rank/select

Citations

  1. Sebastiano Vigna, Quasi-Succinct Indices, WSDM 2013, sections 4-7; DOI 10.1145/2433396.2433409 (accessed 2026-11-17)
  2. Giuseppe Ottaviano and Rossano Venturini, Partitioned Elias-Fano Indexes, SIGIR 2014, sections 4-5; DOI 10.1145/2600428.2609615 (accessed 2026-11-17)
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.

JSON: /data/terms/elias-fano.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Elias-Fano encoding. Hesela. 2026-11-17. https://hesela.dev/terms/elias-fano/