Elias-Fano Encoding for Monotone Sequences

The integers in a postings list are ascending, and that order is information. A code that ignores it — variable-byte, bit packing — stores each value without using the fact that the next value is larger than the current one. Elias-Fano exploits the order directly: it stores a sorted sequence of n integers from a universe of size u in roughly n log₂(u/n) + 2n bits, which is within a couple of bits per element of the information-theoretic optimum, while retaining the ability to extract the i-th value in constant time.

That combination — near-optimal space and constant-time random access — is what separates Elias-Fano from everything earlier in this cluster. The earlier schemes are either larger but fast to decode, or smaller but sequential. Elias-Fano is both small and randomly accessible, and the cost is a primitive operation, select on a bit vector, that is cheap only when it has been engineered carefully.

The split into high and low parts

The universe is the document identifier space. Given n sorted values drawn from 0 to u−1, choose a split point: the low bits hold the value modulo 2^b, and the high bits hold the quotient by 2^b. The standard choice of b is ⌊log₂(u/n)⌋, which makes the low part use b bits and the high part use the remaining bits.

The two parts are stored in different structures. The low parts are packed contiguously into an array, each occupying exactly b bits — this is a fixed-width array, one per element, requiring n·b bits in total. The high parts are not stored per element at all, because they are non-decreasing and mostly repeated. Instead, the high parts are represented by a bit vector of length n + u/2^b, with a one bit at position (high_i + i), where i is the element’s rank.

Consider a small example with universe 16 and b = 2. The values 2, 5, 9, 12 have low parts 2, 1, 1, 0 (two bits each) and high parts 0, 1, 2, 3 (the quotients by 4). The bit vector marks positions high_i + i = 0, 2, 4, 6, giving the pattern 1010101, and the length is 4 (elements) plus 4 (the maximum quotient) = 8, minus a small constant.

The high part is the clever part. Because the values are sorted, the high parts are non-decreasing, and because they are non-decreasing, the number of elements with a given high value is stored implicitly in the spacing of the one bits. The bit vector needs only n one bits and u/2^b zero bits, and it encodes the entire high-part sequence.

The space bound

The total size is the low array plus the high bit vector. The low array costs n·b bits with b ≈ log₂(u/n). The high bit vector costs n + u/2^b bits, and with b = log₂(u/n) this is n + u/(u/n) = 2n bits. The sum is n·log₂(u/n) + 2n bits.

The information-theoretic lower bound for storing an n-element subset of a u-element universe is ⌈log₂ C(u, n)⌉ bits, which is approximately n·log₂(u/n) + 1.44n bits. Elias-Fano is about half a bit per element above that, and the constant can be shaved by adjusting the split point or by using a different high-part encoding. For a postings list of a million documents from a universe of ten million, the bound is about a million times (log₂ 10 + 2) ≈ 5.3 million bits, roughly 0.66 megabytes, against about a megabyte for the practical Elias-Fano form.

The remarkable property is that this holds for every distribution. Elias-Fano does not adapt to the gap distribution the way a Golomb-Rice code does; it achieves its bound uniformly, because the split point depends only on u and n, not on where the values fall. A list with a uniform gap distribution and a list with one giant gap and a million adjacent values cost the same in bits, and both are near-optimal for their own density. This is a different philosophy from the adaptive codes: Elias-Fano pays the same price everywhere and never has a bad case, while the adaptive codes pay less on favourable distributions and more on hostile ones.

Random access through rank and select

To extract the i-th value, read the i-th low part directly — it is at a fixed bit offset — and reconstruct the high part from the bit vector. The high part is the number of zero bits before the i-th one bit, which is exactly the operation called select on the bit vector: select_1(i) returns the position of the i-th set bit, and high_i = select_1(i) − i. The value is then high_i·2^b + low_i.

Select is a primitive that has to be fast for the whole scheme to work, and it is fast only with auxiliary structures. A naive scan of the bit vector costs O(u) per select. The standard construction stores, at fixed intervals of the bit vector, the cumulative number of ones so far, so that a select begins from the nearest sampled point and scans a bounded number of bits. With a sample every 512 bits and a 64-bit popcount of the intervening words, a select costs a handful of memory references. This is the “succinct bit vector” machinery, and it adds o(n + u/2^b) bits of overhead, which is why the space bound above has the 2n rather than n for the high vector: the sampled structure is part of the cost.

Successor queries fall out for free. The position of the first value greater than a query x is found by locating the bit vector position corresponding to x’s high part and scanning the adjacent low parts, which is the operation an inverted-index cursor needs to “advance to the next document at or after d”. This is the property that makes Elias-Fano attractive for the skip-structure-free random access that bit packing achieves only with auxiliary skip arrays.

Why it was not the obvious default

The theory is clean; the engineering made Elias-Fano a latecomer. Three practical factors delayed its adoption, and they explain why the earlier, larger schemes still dominate the field.

Decode of a single value is cheap, but decode of a contiguous run of values is not cheaper than a fixed-width scheme, and it involves the select machinery per value if the values are read one at a time. A sequential scan that needs every value can instead walk the bit vector linearly, using the rank samples to skip, and amortise the select cost, but the code path is more complex than a variable-byte loop.

The bit vector’s select is a random access into a sampled structure, so its cache behaviour depends on the sample interval and the access pattern. A query that seeks to widely separated documents pays a cache miss per select, while a sequential decode stays in cache. The same tension exists in every indexed structure, but Elias-Fano’s per-operation constant is dominated by the select, and select is only cheap when the sampled data is resident.

The universe size must be known. Elias-Fano needs u to allocate the high bit vector, and document identifiers are assigned from a growing counter, so the universe is the collection size, which changes. An index built incrementally must either rebuild to a new u or allocate headroom, and headroom inflates the high vector linearly in the unused universe. The codes earlier in this cluster do not care about u at all; they only care about the gaps, which is a real operational advantage.

What Elias-Fano does and does not replace

For monotone document identifier lists, Elias-Fano is a strong candidate for the postings themselves: near-optimal space, random access, and a successor primitive. For position lists inside a document, the same properties apply, and a positional index stored as Elias-Fano inherits them. For the term dictionary, the values are not a monotone sequence of integers but a sorted set of variable-length strings, and Elias-Fano does not apply directly — that is the domain of front coding.

The real competitor is not another integer code but the decision about whether random access matters at all. A term-at-a-time evaluator that reads lists sequentially from start to finish gains nothing from Elias-Fano’s random access and would rather have the fastest sequential decode, which a bit-packed or variable-byte format provides more cheaply. A document-at-a-time evaluator with frequent seeks gains a great deal, and for it the select cost is the price of not carrying skip arrays. Elias-Fano is the answer to a specific question — “how small can a monotone sequence be while staying randomly accessible?” — and it is near the theoretical answer to that question.