Elias–Fano Monotone Select
Split monotone integers into low bits and a select-indexed high-bit vector.
By Riano · Published · Updated · Report a correction
Elias–Fano Monotone Select
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.
Worked Example
Consider encoding the sequence 1, 3, 8, 10, 15 from a universe U = 16. There are n = 5 elements. The number of low bits is calculated as ℓ = max(0, ⌊log₂(16 / 5)⌋) = max(0, ⌊log₂(3.2)⌋) = 1. This means we take 1 low bit for each number, and the remaining bits form the high value by dividing by 2¹ (or shifting right by 1).
| Value | High (value/2¹) | Low (value mod 2) |
|---|---|---|
| 1 | 0 | 1 |
| 3 | 1 | 1 |
| 8 | 4 | 0 |
| 10 | 5 | 0 |
| 15 | 7 | 1 |
To build the high bitvector, we place a 1 at index (high + i), where i is the 0-based index of the element.
| Index i | High | Position (High + i) |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 2 |
| 2 | 4 | 6 |
| 3 | 5 | 8 |
| 4 | 7 | 11 |
Placing 1s at indices 0, 2, 6, 8, 11 gives the high vector 1010001010010. Concatenating the 1-bit low parts gives 1|1|0|0|1.
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.
Limitations
Elias-Fano encoding requires the sequence to be strictly monotone non-decreasing. It does not work on unsorted arrays. It also requires knowing the upper bound of the universe U and the number of elements n in advance to compute the optimal splitting parameter ℓ.
References
- Vigna, S. (2013). Quasi-succinct indices.arXiv:1206.4300
- Elias, P. (1974). Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM), 21(2), 246-260.
- Fano, R. M. (1971). On the number of bits required to implement an associative memory.
For further details on how this succinct index operates, refer to the above classical articles.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Elias–Fano Monotone Select module.
Try Elias–Fano Monotone Select on Riano →