Elias–Fano Monotone Select
Split monotone integers into low bits and a select-indexed high-bit vector.
Free theory articleSplit monotone integers into low bits and a select-indexed high-bit vector.
Concept & interpretation
The Elias-Fano encoding provides an elegant and succinct way to represent monotone non-decreasing sequences of integers. It works by splitting each integer into two parts: a fixed number of low bits (ℓ bits), and the remaining high bits. The high bits are then represented using a unary-like bitvector where the position of the i-th one bit determines the high-part value of the i-th element. This separation allows the original sequence to be encoded close to the theoretical information lower bound, while supporting fast random access via select-one operations on the high-bit vector.
Experiment
Use the interactive module to explore how the Elias-Fano encoding handles different types of sequences.
- Start by changing the Sequence native select to Equal and observe how repeated values cause contiguous blocks of ones in the high bitvector.
- Increase the Universe size to see the number of low bits (ℓ) increase, making the high bitvector sparser.
- Change the Probe index to see how random access decodes a specific element using a select-one query.
- Observe the Low-bit count and Decoded probe outputs after each change.