Elias-Fano Encoding for Monotone Integer Sequences

A sorted array of n increasing integers drawn from a universe of size u is the natural representation for an inverted index’s document list, a sparse matrix’s row offsets, or a set of timestamps. It supports binary search in O(log n) with no preprocessing, which is why it is so often the answer. Elias-Fano encoding keeps the same query cost class while storing the sequence in n(2 + ⌈log₂(u/n)⌉) bits instead of n ⌈log₂ u⌉ bits, and it answers the prefix-count query “how many values are below x” in O(1) rank operations rather than O(log n) comparisons.

The gain is large exactly when the sequence is sparse in its universe. For u = 2³² and n = 10⁶, a plain 32-bit array costs 32 bits per value. u/n is about 4295, whose base-two logarithm is just over 12, so ℓ = 13 and the encoding costs 2 + 13 = 15 bits per value — a factor of about 2.1, achieved with no loss of query capability. The saving grows with sparsity: at n = 10⁷ the ratio falls to about 429, so ℓ = 9 and the cost is 11 bits, a factor of 2.9.

The split, and what each part costs

Fix a width ℓ = ⌈log₂(u/n)⌉. Write each value x as x = (x >> ℓ) << ℓ | (x & (2^ℓ - 1)), that is, a high part h = x >> ℓ and a low part l = x mod 2^ℓ.

The low parts go into a packed array of n fields of ℓ bits each, in order. They cost n ℓ bits and support direct access to the i-th low part in O(1).

The high parts go into a bitvector of length n + h_max + 1 bits, built by unary encoding: the i-th high value h_i is represented by h_i zeros followed by a one, and the encodings are concatenated in order. The position of the i-th one in this bitvector is therefore i + h_i, because the i-th one is preceded by i ones (its own included in the count from 0) and h_i zeros. The bitvector has at most n + u/2^ℓ bits, and with 2^ℓ ≈ u/n that is at most 2n bits.

#include <stdint.h>

/* Build the high-bit bitvector for values v[0..n) with shift l.
   The i-th one sits at position i + (v[i] >> l), so the buffer needs
   n + (v[n-1] >> l) bits. Caller zeroes it. */
static void ef_highs(const uint64_t *v, size_t n, unsigned l, uint64_t *bits) {
    for (size_t i = 0; i < n; i++) {
        size_t pos = i + (size_t)(v[i] >> l);   /* strictly increasing */
        bits[pos >> 6] |= 1ULL << (pos & 63);
    }
}

Accessing the i-th value is select₁(i) on the high bitvector to recover i + h_i, then reading the low part from the packed array, then recombining: ((pos - i) << ℓ) | low[i]. Both operations are O(1) given a rank/select index of the kind described in Bitset Representation and Word-Level Rank and Select.

Prefix counting without search

The query rank(x) — how many values are strictly less than x — is where the encoding earns its place. Write x = (h << ℓ) | l. The number of ones before the zero numbered h is select₀(h) - h, because that zero has exactly h zeros before it and everything else in the prefix is a one. Every value whose high part is below h contributes exactly one one to that prefix, so the identity gives the boundary between the values with high part below h and the values with high part at least h:

1. start = (h == 0) ? 0 : select₀(h - 1) - (h - 1), the index of the first value with high part h.
2. end = (h < zeros) ? select₀(h) - h : n, one past the last value with high part h, where zeros is the total number of zeros in the bitvector — that is, the largest high part present.
3. Binary search within [start, end) for the first low part ≥ l. The block has at most 2^ℓ values in the worst case but typically far fewer, and in the common case it is small enough that a linear scan over a few packed fields beats a binary search.

The two select operations are the only non-constant work before the block search, and with a rank/select index they are themselves constant-time. Step 3 is a search inside one block, which is O(log(block size)), and the block is short when the values are spread evenly. The claim that Elias-Fano answers prefix queries in O(1) therefore rests on an assumption about the data, not only on the structure: uniform spread makes the block a single comparison, and clustered input makes it a scan of the whole cluster.

/* Count of values < x. `zeros` is the number of zeros in `bits`, which
   equals the largest high part present. */
static size_t ef_rank(const uint64_t *v_low, size_t n, unsigned l,
                      const uint64_t *bits, size_t zeros, uint64_t x) {
    size_t h = (size_t)(x >> l);
    uint64_t lo = x & ((1ULL << l) - 1);
    if (h > zeros) return n;                    /* past the last block */
    size_t start = (h == 0) ? 0 : select0(bits, h - 1) - (h - 1);
    size_t end   = (h < zeros) ? select0(bits, h) - h : n;
    /* scan or binary search v_low[start..end) for the first >= lo */
    size_t i = start;
    while (i < end && v_low[i] < lo) i++;
    return i;
}

The failure mode in this code is the mask (1ULL << l) - 1 when l == 64, which shifts by the width of the type. ℓ is bounded by log₂(u/n) and is at most 63 for any realistic u, so the guard is a static assertion rather than a runtime check.

Why the block search is not the bottleneck

The critical property is that the block sizes are determined by the distribution, not by n. If the values are uniformly spread over the universe, each block holds about n · 2^ℓ / u ≈ 1 value, so the search is a single comparison. If the values cluster — all n values in one high block — then one block holds all of them and the query degenerates to a linear scan over n values.

Clustered input is the case where Elias-Fano’s O(1) claim needs qualification, and clustering is normal rather than pathological in the structures the encoding was designed for: document id lists for a term are not spread uniformly over the id space, and timestamps concentrate around working hours. The remedy is to choose ℓ from the actual distribution rather than from u/n, which keeps the average block short at the cost of a longer bitvector for the outliers. A common practical choice is to set ℓ so that the bitvector length is about 2n bits, which is the optimum for uniform data and a reasonable compromise for skewed data.

Comparison with the alternatives

Three structures compete for the same job, and the choice depends on the query mix.

A plain sorted array. n ⌈log₂ u⌉ bits, O(log n) per lookup, and the simplest possible implementation. Its advantage is cache behaviour: binary search on a dense array touches log₂ n lines, while Elias-Fano touches a directory, a bitvector word, and a packed block. For small n the dense array also avoids building the two indexes at all, which is why it is usually the better choice when the sequence is short.

Delta encoding plus a sampled index. Store the gaps v_i - v_{i-1} with a variable-length code and a sample every k values. Space can be better than Elias-Fano for very sparse sequences, but random access requires decoding from the previous sample, so access is O(k) in the worst case and the structure is best for sequential scans.

Elias-Fano. n(2 + ⌈log₂(u/n)⌉) bits, O(1) random access, a prefix count that costs two select operations plus a search inside one block, and high bits whose ones are strictly increasing, so the bitvector has long runs of zeros on sparse input and compresses well under run-length coding. Its weakness is that the low parts are stored at a fixed width, so a sequence with a few huge gaps pays for them in every entry.

The 2018 “learned index” line of work made a related observation: for a sorted array, a model that predicts the position of a key can replace the top levels of a search tree, and the error bound of the model determines the local search length. Elias-Fano’s block structure is the same idea with an exactly known error bound and no model: the block is the region where the high bits agree, and its length is read off the bitvector rather than predicted.

Construction and its cost

Building the structure is one pass over the values. Computing ℓ requires u and n, both known in advance. The high bitvector is written by a loop like the one above, which touches n output words in the worst case, and the low array is a pack of n fields of ℓ bits. The rank/select index is built over the high bitvector in one more pass, O(n) with a popcount per word.

The construction cost that is easy to miss is the bitvector buffer. The |= in the loop requires the output to be zeroed first, and the buffer’s length depends on the maximum high value, which is the last value’s high part. Zeroing 2n bits is O(n) work but touches n/4 bytes; for n = 10⁸ that is 25 MB of writes before the first one is set.

Every one is written at its final position pos_i = i + (v_i >> ℓ), computed independently from i and v_i. That independence is worth noting because it means the writes can be split across threads as long as they are distributed by output word rather than by input index — the buffer is the only shared state, and clearing it can be done word-wise. Two values cannot collide: i grows by one per step and v_i >> ℓ never decreases, so the positions are strictly increasing.

Where the sequence must also support insertion, Elias-Fano is the wrong structure: inserting one value shifts every subsequent high part and rewrites the bitvector. The mutable alternatives are the B-tree family, covered in another cluster, or a log-structured merge of immutable Elias-Fano blocks, which is how several search engines store posting lists — the static blocks are built once and merged in the background. The rank/select machinery those blocks rely on is the same as in Bitset Representation and Word-Level Rank and Select, and the next step up in query power, range counting over arbitrary sequences, is the subject of Wavelet Trees and Range Queries on Sequences.