Twenty bits apart

Two ways to store a bit vector that is not half ones, and they attack opposite ends of the density dial.

Elias–Fano stores the positions of the ones, split into a packed low part and a unary high part. Its cost is m(2 + log₂(n/m)) — proportional to the number of ones, with a logarithm of the sparsity.

Block classes store each block of b bits as the count of ones in it plus which block with that count it is. Its cost is Σ ⌈log₂ C(b, cᵢ)⌉ — the entropy of the block classes, which goes to zero on a vector of all zeros or all ones.

The first is small when the ones are few. The second is small when the bits are uniform, whichever value they take.

On the marks of a self-index, sweeping the sampling rate sweeps the density, and the two lines cross.

The crossing #

At one sampled position in sixteen: Elias–Fano 6,745 bits, block classes 6,765.

Twenty bits apart on a set of a thousand and twenty-five marks in sixteen thousand three hundred and eighty-five positions.

Below that rate the blocks win and above it the split does. At one in eight: 11,406 against 10,023, blocks ahead by fourteen per cent. At one in thirty-two: 3,905 against 4,557, Elias–Fano ahead by seventeen.

So there is a genuine crossing inside the range a real index uses, and it is not at an end of the dial where nobody operates.

Twenty bits out of six thousand seven hundred is three parts in a thousand, which is well inside anything a reader should treat as a difference. It is worth reporting to that precision anyway, because the closeness is the finding: two structures built on unrelated principles, over one set, agreeing to a tenth of a per cent at one point of a dial they otherwise disagree about by factors.

A coincidence, and a useful one — it means the crossing is genuinely a crossing rather than a region where both are indifferent, and it means the decision at that rate can be made on something other than size.

Why they behave oppositely #

The two representations are exploiting different properties and a set can have one without the other.

Elias–Fano exploits sparsity: it stores m things and its cost per thing is a logarithm of the sparsity, so a sparser set costs less in total and slightly more per element.

Block classes exploit uniformity within a block: a block of sixty-three bits containing one one has C(63, 1) = 63 possibilities, so its offset is six bits and its class is six, against sixty-three plain. A block containing zero ones has one possibility and costs its class alone.

At a density of one in sixteen a block of sixty-three holds about four ones, and C(63, 4) is 595,665, so the offset is twenty bits and the class six — twenty-six against sixty-three, a factor of 2.4.

At a density of one in a hundred and twenty-eight a block holds about half a one, so most blocks are empty and cost six bits each. That is 6/63 = a tenth of a bit per position, which is a factor of ten and is being beaten by Elias–Fano’s factor of fifteen.

The reason Elias–Fano pulls ahead is that the block representation’s cost has a floor: the class of every block, ⌈log₂(b+1)⌉ bits, is paid whether the block is empty or not. That is 6/63 of a bit per position, or n/10.5 bits total, and it does not shrink with the density.

A second flat term, on the other representation. At one in a hundred and twenty-eight the blocks cost 2,566 bits of which about 1,560 is class overhead on empty blocks.

Both representations have a block-size-like parameter and only one of them has been swept in this collection. Elias–Fano’s is the low width and it is chosen by a closed form. The block representation’s is b, the block length, and rank is the only thing it does swept it and found an optimum near sixty-three for the vectors in a wavelet tree.

Whether sixty-three is the right b for a scattered sparse vector is a question nobody has asked, and it moves the crossing. A larger b reduces the per-block class overhead — the n-proportional floor — at the cost of longer offsets, so a block representation tuned for sparsity would push the crossing rightward.

The numbers here are at b = 63 throughout, which is the value this collection uses for the vectors it was tuned on. So the crossing is at one in sixteen for that block size, and a differently tuned block representation would cross elsewhere.

The operation counts, which the plate does not show #

Since the size decision at the crossing has to be made on operations, it is worth putting the operation costs where a reader can compare them, because none of this strand’s plates does.

A plain vector’s rank is a superblock read, a block read and a scan of at most one block: three memory touches and a popcount, constant.

An Elias–Fano rank is a select0 on the high vector — which in this implementation is a binary search over the high vector’s superblock directory plus a scan — and then a walk of 1.25 entries. Several times a plain rank, dominated by the select.

A block-classed rank is a directory read and then a decode: reconstructing the block from its class and offset, which is an unranking of a combination and is the expensive part. Comparable to Elias–Fano’s, possibly worse, and not measured here.

So all three are constant-time and their constants span perhaps an order of magnitude, with plain fastest. That is the axis on which the decision at the crossing is made and it is the axis this collection has measured least.

The reason is that this strand’s instrument charges operations rather than time, and all three of these are one operation by that accounting. The comparison that is not one comparison is the essay about exactly that gap, and it applies here: three ranks costing three different amounts, all charged as one.

What decides at the crossing #

Twenty bits is not a difference, so the choice at one in sixteen has to be made on something else, and there are three candidates.

The operations. A rank on Elias–Fano is a select0 on the high vector plus a bucket walk averaging 1.25 accesses. A rank on a block-classed vector is a directory read plus a decode of the block from its class and offset before counting — several times a plain vector’s work, and the decode is the expensive part. Elias–Fano wins.

The other operation. select1(k) on Elias–Fano is one select and one array read. On a block-classed vector it is a search over the directory and then a scan — much worse, because the representation is built around rank rather than select. Elias–Fano wins again, more decisively.

The construction. Both are linear. Elias–Fano is simpler by a wide margin: two arrays and a bit vector against a table of binomial coefficients and per-block encoding.

So at the crossing Elias–Fano is the choice on every axis except size, where the two are equal. That is a comfortable resolution and it makes the crossing less interesting than the plate suggests.

Why a crossing this close is unusual #

Most crossings in this collection are between structures doing the same job with different constants, and they cross because one constant is larger. A crossing between structures exploiting different properties is a different kind of thing and is worth marking.

The collection decides which index is small has one: an entropy-bounded index against a run-length one, crossing because a collection has some predictability and some repetition and the mix decides. That crossing moves with the corpus and is a property of the data rather than of the structures.

This one is the same shape one level down. The marks have some sparsity and no runs, so the crossing sits where the sparsity’s value overtakes the runs’ absence — and on a set with runs it would move, and on a denser set it would move the other way.

The general property: a crossing between two structures exploiting one property is a fact about the structures; a crossing between structures exploiting different properties is a fact about the data. The first can be quoted; the second has to be re-measured on each object.

Twenty bits at one in sixteen is the second kind, and quoting it as a rule would be quoting a property of these marks.

Where the block representation genuinely wins #

There is a regime where the ordering above reverses completely, and it is not on this plate’s right-hand side.

At density one — every row marked — the block representation costs 1,789 bits against the plain vector’s 19,475 and Elias–Fano’s 38,967. A factor of eleven better than plain and twenty-two better than the split.

That is because every block is all ones, so every offset costs nothing and the whole structure is its classes and directory.

The same holds at density zero and, less dramatically, at any density where the ones are clustered rather than scattered — a block that is all ones or all zeros costs nothing either way.

So the block representation’s real domain is vectors with runs, and a vector with m scattered ones is the case it handles least well. The marks are scattered by construction, because the transform sorts by context.

Rank is the only thing it does is where this collection priced the block representation, and it was on the levels of a wavelet tree over a transform — which have runs, which is the whole reason a compressed index is compressed. Applied to a scattered set it is being used outside what it is for.

What the marks would have to be #

It is worth asking what set the block representation would win on here, because the answer says something about the sampling policy.

A vector with n/s ones arranged in runs — consecutive sampled rows — would be nearly free to the blocks and unchanged to Elias–Fano.

Sampling by row index rather than by suffix-array value gives exactly that: mark every s-th row and the vector is a regular pattern, which a block representation handles better than a scattered one at the same density. But sampling by row index does not support a locate, because a locate arrives at an arbitrary row and needs to know whether its position was sampled.

So the scattering is not incidental — it is what makes the sampling useful, and it is what makes the block representation the wrong tool. The sampling that goes the other way separated the two sampling directions in this collection and this is a consequence of that separation nobody had drawn.

Two floors, on two representations #

Both alternatives to the plain vector have a term that does not shrink, and putting them side by side is the tidiest way to see why the crossing exists.

Elias–Fano’s floor is 2m bits — one for the high vector’s one and one for its bucket boundary, roughly — plus its directory. That is proportional to m, so it does shrink with the density; it is a floor per element rather than per position.

The block representation’s floor is n·⌈log₂(b+1)⌉/b — the class of every block, paid whether the block is empty or not. At b = 63 that is n/10.5, proportional to n, and it does not shrink.

So at sparse densities the block representation has a term in n and Elias–Fano does not, which is the same shape as the plain vector’s n-bit payload one step milder. The crossing is where Elias–Fano’s per-element cost falls below the blocks’ per-position floor.

Solving: m(2 + log₂(n/m)) = n/10.5 gives n/m around fifteen, which is where the measurement puts it.

What this says about a third representation #

The two floors suggest an obvious hybrid and it is worth naming rather than building.

A block representation with a sparse index over non-empty blocks would not pay the class of an empty block — the empty blocks would simply not be listed, and their absence would be encoded by the index. That removes the n-proportional floor and leaves a structure that is small at both ends.

That is, roughly, what a production succinct library ships: a partitioned vector choosing a representation per block, with the choice encoded in a header. Its size is within a constant of the best of the three at every density.

This collection has not built it, for the reason where the sparse representation loses gives: an adaptive structure hides the boundary it adapts across, and measuring the boundary requires the non-adaptive versions. The crossing at one in sixteen is a number a hybrid’s implementation needs and its own measurements would never show.

The three representations as three assumptions #

The cleanest way to hold this is that each representation is an assumption about the vector, and the assumption is what makes it small.

Plain. No assumption. n bits, always, and optimal for a vector of density a half. Every operation constant and cheap.

Elias–Fano. The ones are few. Cost m(2 + log₂(n/m)), which is the entropy of a sparse set plus half a bit an element. Select cheap, rank cheap-ish, and the assumption fails at density above about 0.3.

Block classes. The bits are locally uniform. Cost the entropy of the block classes, which is zero on constant blocks and maximal on random ones at density a half. Rank moderate, select poor, and the assumption fails on a scattered set.

A vector satisfying neither assumption should be plain. One satisfying both should be a hybrid. The marks satisfy the first and not the second, which is decided by the transform scattering them.

That framing also says what to measure when meeting a new bit vector: its density, and the entropy of its block classes. Two numbers, both a single pass, and between them they choose among the three.

What the plain vector is still for #

Ending without a word for the representation both alternatives are being compared against would leave the wrong impression, because it wins over part of the range and it wins on every operation everywhere.

At one row in four and denser, the plain vector is the smallest of the three — 19,475 bits against Elias–Fano’s 18,691 at exactly one in four, which is the crossing, and against 29,189 at one in two.

And at every density its operations are the cheapest: a rank is three memory touches and a popcount, with no decode, no select, and no walk.

So a system sampling densely should use it without hesitation, and a system sampling sparsely is trading operation cost for size — which is the same trade the sampling rate itself is, one level down.

That layering is worth noticing. The sampling rate trades index size against locate time. The mark representation trades index size against mark-lookup time. Both dials point the same way, and a system turning one should know it is compounding rather than choosing independently.

The array that says where is twice the samples is where the first dial’s effect on the second was measured, and what the locating apparatus becomes is where the two are put on one plate.

What to take from twenty bits #

Two things, one narrow and one general.

For the marks: use Elias–Fano. The crossing is at one in sixteen, the sizes are equal there, and Elias–Fano wins on both operations and on construction simplicity. Below one in four use the plain vector, because both alternatives lose.

And: a crossing this close is a signal that the two structures are exploiting different properties of the same object, not competing at the same thing. Two representations that differ by twenty bits at one point and by a factor of twenty at the ends are not two implementations of one idea. They are two ideas, and the object happens to have a little of each.

That is worth knowing before optimising either. A structure with both sparsity and runs would want the hybrid; one with only sparsity wants the split; one with only runs wants the blocks. The marks have sparsity and no runs, which is why the answer is clean once the question is asked in those terms.