A position split in two

The marks are a sorted set of m positions in a universe of n, stored as n bits. The information they carry is about m log₂(n/m) + 1.44m, which at one row in thirty-two is a fifth of that.

Elias–Fano is the representation that reaches it, and the construction is short enough to state completely.

Split each position into a high part and a low part at w = ⌊log₂(n/m)⌋ bits. The low parts are the bottom w bits, stored one after another: m·w bits, packed, no structure.

The high parts are the remaining bits, and they are stored as a bit vector rather than as numbers. The vector has length m + n/2^w, and the k-th one sits at position (pₖ ≫ w) + k.

That placement is the whole trick and it is worth reading twice. The high parts are non-decreasing, so writing them as a sequence of ones separated by zeros — a one for each element, a zero for each empty bucket — gives a vector with m ones and n/2^w zeros in which every element’s high part is recoverable from where its one sits.

Recovering a position #

The k-th position is (high.select1(k) - k) << w | low[k].

select1(k) gives where the k-th one is. Subtracting k removes the ones that precede it, leaving the number of zeros — which is the number of bucket boundaries crossed, which is the high part. Shift it up by w and add the low part.

One select, one array read, one shift, one or. Select is not rank backwards is where this collection established that the two directions of a bit vector’s operations are genuinely different structures, and this representation is the clearest case: it is built so that select is one operation and rank is one operation plus a scan.

That is a constant-time operation given a select structure on the high vector, and it is the reason this representation is used rather than a sorted array: a sorted array’s k-th element is also one read, and the array is m⌈log₂ n⌉ bits rather than m(w + 2).

It is worth working one element through, because the offset by k is the part that reads as a trick and is not one.

Take positions 3, 9, 9 is not allowed — take 3, 9, 20 in a universe of 32, with m = 3 so w = ⌊log₂ 10⌋ = 3. The low parts are 3, 1, 4 and the high parts are 0, 1, 2.

The high vector has length 3 + 4 = 7. Element 0 has high part 0 and k = 0, so its one goes at position 0. Element 1 has high part 1 and k = 1, so position 2. Element 2 has high part 2 and k = 2, so position 4.

Vector: 1 0 1 0 1 0 0.

Reading element 1 back: select1(1) is 2, minus k = 1 gives 1, shifted by 3 gives 8, or the low part 1 gives 9. Correct.

The subtraction by k is undoing the offset the encoding introduced, and the encoding introduced it so that equal high parts get distinct positions. Without the offset, two elements in the same bucket would want the same bit.

Counting the ones before a position #

The other operation the marks need is rank1(i): how many samples precede row i.

Split i the same way. Every element with a smaller high part precedes it; every element with the same high part precedes it if its low part is smaller.

The first group is found by a select0: the zeros in the high vector are bucket boundaries, so the position of the (hi − 1)-th zero is where the bucket for hi begins. Subtracting the zeros before it gives the index of the first element in that bucket.

The second group is a walk along that bucket comparing low parts.

So a rank is one select0 and a short scan, and the scan’s length is the bucket’s occupancy — which is one on average, because w was chosen to make 2^w ≈ n/m.

That is what the choice of w is for. It is not chosen to minimise the size, or not only; it is chosen so that a rank’s scan is a constant.

The measured cost of a rank #

The average bucket walk over four hundred probes is 1.25 accesses, which is the expected occupancy plus a little for the buckets that hold two or three.

A sorted array of the same positions answers the same rank by binary search: ⌈log₂ 513⌉ = 10 steps.

That is a factor of eight on the operation, between two structures that price identically. A price with no structure under it is where that gap is the subject.

There is an asymmetry between the two operations worth flagging. Select is one operation and rank is one operation plus a bounded scan, so a workload doing mostly selects gets a cleaner cost than one doing mostly ranks.

A locate does both: at at every LF step of its walk, which is a rank, and rank1 once at the end to find which sample it landed on. So the walk’s s/2 steps are all rank-shaped, which means the bucket scan is the operation a locate spends its mark budget on.

At 1.25 accesses a rank and s/2 = 16 steps, that is twenty accesses a locate on the marks against the wavelet tree’s several hundred. Small, and it is the number that would grow if the low width were chosen badly.

The sizes #

At n = 16,385 and m = 513 — one row in thirty-two on a sixteen-thousand-character text — the low width is 4, so:

Low parts: 513 × 4 = 2,052 bits. High vector: 513 ones and 1,024 zeros, so 1,537 bits of payload plus a directory. Total with directory: 3,905 bits.

The plain vector with its directory is 19,475. The Elias–Fano array is 20.1% of it.

Compressed blocks over the same set reach 4,557 — close, and on the wrong side. Twenty bits apart is where the two representations cross.

Why the high vector is not itself sparse #

A reader who has followed the construction will notice that the high vector has m ones in m + n/2^w positions, which is about half — and ask why it is not itself Elias–Fano encoded.

Because it is not sparse. At w = ⌊log₂(n/m)⌋ the vector has m ones and about m zeros, so its density is a half, and Elias–Fano on a density-one-half set costs more than storing the bits. Where the sparse representation loses measures that directly: at every row marked, the array is 2.0 times the plain vector.

So the recursion terminates immediately, by construction. The split is chosen so that the high vector is dense enough to store plainly and the low parts are incompressible — they are the low bits of positions, which on any set worth this representation are essentially uniform.

That is a satisfying property and it is the reason the construction has one level rather than being a hierarchy.

The two directories #

The high vector needs both a select structure and a rank structure, and it is worth being explicit because the size accounting depends on it.

select1 is used by the position lookup. select0 is used by the rank. Both are searches over the vector’s directory in this implementation, which is a plain bit vector with superblock and block counters.

That directory is 596 bits at this size — 10.4% of the structure. It is the part the size model this collection has carried for several strands omits entirely, and it is the difference between an accounting and an object.

A production implementation would use a constant-time select structure rather than a search over a rank directory, which costs more bits and less time. The trade is real and this collection has not measured it; what it has measured is that the directory is not zero, which is the claim the model was making.

What the construction does not need #

Three things a reader might expect and none of them is present.

No compression of the low parts. They are packed and that is all. On a set whose elements are spread across the universe the low bits are uniform, so there is nothing to compress — which is the same argument as the high vector’s density and is the other half of why the split is where it is.

No assumption about the set’s structure. The construction works on any sorted set and costs the same on a regular one as on a random one. That is a weakness rather than a strength: a set with structure — an arithmetic progression, say — is far more compressible than this, and Elias–Fano gets none of it.

No dependence on the universe’s size beyond a logarithm. The size is m(w + 2) with w = log₂(n/m), so doubling n at fixed m costs one bit per element. The plain vector doubles.

That third point is the one that matters for a growing index. A collection that doubles keeps its sampling rate, so m doubles too and both representations double — but a collection that doubles while keeping the number of samples fixed costs the plain vector twice as much and Elias–Fano one bit an element.

Two operations the marks do not need #

The representation supports more than the index asks of it, and it is worth saying what is being paid for and not used.

Predecessor. Given a row, the largest sampled row at or before it — which is select1(rank1(i) - 1), two operations. An index that walked forward rather than backward would want this, and none here does.

Successor. The mirror. Also unused.

Both are free in the sense that they need no structure beyond what select and rank already need. So nothing is being paid for them, and they are mentioned because they are the reason this representation is the standard one for posting lists: an inverted index intersecting two lists wants successor queries constantly, and Elias–Fano supports them without a separate index.

The marks want a membership test and a rank, which is the smallest useful subset of what the structure does. That is worth knowing if a future use wants more: the structure will not need replacing.

Where it came from #

The representation is Elias’s from 1974 and Fano’s from the same year, and it has been rediscovered several times since under other names — the sd-array being the one this field uses.

That it is fifty years old and the structure it is being applied to is thirty is worth a sentence, because the gap is not a story about anybody being slow. Elias–Fano’s usual application is an inverted index’s posting lists, which are sparse sets of document identifiers; the marks of a self-index are a sparse set of row numbers. The two fields describe the same object in different vocabularies — “posting list” and “sample marks” — and neither paper’s index contains the other’s word.

That is the same translation failure asking about symbols that are not there records for a different operation, and it is the second instance in this collection within one slate. The tree answers the question is the third, on a third pair of vocabularies.

Two ways to build the same object #

The strand builds this structure twice and the two routes have to agree, which is a check rather than a formality.

One route is a subclass: an index that builds a plain-marked structure in its constructor and replaces the vector before anything reads it. That is how a standalone index gets sparse marks.

The other is a swap: a function that takes a built index, reads its marks out, and replaces the field. That is how a bidirectional index’s halves get them, because those halves are built by a factory the subclass cannot reach.

Two ways to build one structure is how they come to differ, so the two are compared: same total size, same number of marks, and every element’s select equal. Two hundred and fifty-seven positions checked.

That check exists because this collection has been bitten by the shape before. What a quadratic construction was setting is a different instance of the general form: a second construction path is a second implementation, and a second implementation drifts until something compares them.

What is checked #

Three claims, and the first is the one that would catch a construction error.

Rank and select agree with a linear count, everywhere. Not a spot check: every position of a four-thousand-row universe, and every element’s select compared against the position it was built from. Four thousand and ninety-eight rank comparisons, two hundred and fifty-seven select comparisons.

The positions strictly increase. Enforced in the constructor, because Elias–Fano’s high vector encoding assumes it and a violation produces a plausible wrong answer rather than a failure.

Every occurrence an index reports with plain marks, it reports with these. The substitution is genuine — the plain vector is dropped — so a wrong rank produces wrong occurrences rather than a slower query, and the check is on the occurrences.

That third is the one that makes the swap safe to make. A structure whose marks were subtly wrong would produce positions computed from the wrong sample, and the positions would be plausible numbers in the right range.

The one parameter, and what happens if it is wrong #

The construction has exactly one parameter and the rest is determined, which is unusual enough to be worth stating as a property.

Given the set and the universe, w decides everything: the low parts’ width, the high vector’s length, both sizes, and the expected bucket occupancy that bounds a rank’s scan.

Choosing it too small puts everything in the high vector. At w = 0 the vector is n + m bits, which is worse than the plain vector it replaces — and the size check catches it: the degenerate split is 10,043 bits against the chosen split’s 1,968, a factor of 5.1.

Choosing it too large puts everything in the low parts, and the structure becomes a packed array of positions with a nearly-empty high vector. That costs m⌈log₂ n⌉ and is a sorted array with extra steps.

Between the two the curve is shallow, which is the flat bottom of a shallow curve and is the reason a size model rounding the split the other way prices the structure correctly.

So the parameter is easy to get right, hard to get badly wrong, and the failure mode at each end is a size rather than a wrong answer. That is a comfortable place for a parameter to be and it is not where most of this collection’s parameters are.

What the swap does to a locate #

The substitution is meant to be invisible to the query and it is worth checking that it is, because a representation change that quietly slows the hot path is the usual way a size saving is paid for.

A locate walks s/2 rows on average, asking at at each and rank1 once. With a plain vector each of those is a directory read and a short scan — constant. With Elias–Fano each is a select0 on the high vector plus a bucket walk of 1.25 accesses.

So the marks’ contribution to a locate goes from about seventeen constant-time operations to about seventeen operations of a few steps each. Against the wavelet tree’s several hundred bit-vector ranks over the same walk, that is a few per cent.

The measurement that matters is the one on the answers rather than on the timing: every occurrence the plain-marked index reports, the sparse-marked one reports, on seventy-two queries across three pattern lengths and fifteen hundred occurrences. A wrong rank would produce a position computed from the wrong sample, which is a plausible number in the right range and nothing else would catch.

What it buys #

At one row in thirty-two the index goes from 104,720 bits to 89,150 — a saving of 14.9% of the whole structure, for a change to one array.

At one in a hundred and twenty-eight it is 18.4%.

At one in four it is 0.5%, because at that rate the sampled positions dominate and the marks are a tenth of the apparatus.

So the saving is a function of the sampling rate, which is the dial everything in this neighbourhood depends on and the one that has to be quoted beside any number here.