Select is not rank backwards

A bit vector of 65,536 positions holding 6,554 ones. Two questions about it.

How many ones are there before position $i$? A directory of prefix counts, one per block of the vector, one per superblock above that, and a short scan of the remainder. The blocks are evenly spaced because positions are evenly spaced, so the scan is bounded by the block length, and the whole thing costs a fixed fraction of the vector. This collection built it two essays ago and the structure is obvious from the question.

Where is the $k$-th one? There is no obvious structure at all, and the reason is one sentence: select’s answers are indexed by rank, and the ones are not evenly spaced. A million ones may sit in the first thousand positions or be strewn over the whole vector, so a fixed interval in $k$ maps to no fixed interval in position, and nothing about a block length bounds anything.

Three answers, and the cheapest one is free #

Binary search on the rank directory. The superblock counts are increasing, so the superblock holding the $k$-th one is found by binary search, and the answer is found by scanning forward from its start. Zero extra bits. On this vector it scans up to 510 positions, passes 70 ones, and touches 16 machine words.

One position kept per $L$ ones. Store the position of the $L$-th, $2L$-th, $3L$-th one outright, and scan forward from the nearest. At $L=8$ that is 13,120 bits — two bits per one — and the scan passes at most 7 ones.

Dense and sparse superblocks. The structure everything ships. Keep the anchors as above; then, for each stretch between anchors, decide which of two cases it is in:

• if the $L$ ones between two anchors are spread over more than a threshold of positions, write out all $L$ answers. Call it sparse. There cannot be many such stretches, because each consumes a threshold’s worth of a vector that only has $n$ positions, and that argument is what bounds the space;
• otherwise the $L$ ones sit within the threshold, so an offset into the stretch fits in $\lceil \log_2 \text{threshold}\rceil$ bits, and one offset per $M$ ones bounds the scan at $M$ ones.

The two cases are the wrong way round #

Which case a stretch falls into depends on how far apart its ones are, not on how many there are. So:

The sparse case is the vector with the ones spread out. That is the opposite of what the word invites, and it is worth saying plainly because it inverts the intuition about which vectors are expensive: a structure whose size depends on where the ones are, rather than on how many, costs the most on the vector with the fewest.

It also means the size is not a function of $n$ and the number of ones. Two vectors with identical shape parameters differ here by a factor of eleven, and no average-case description of the structure distinguishes them.

What “constant time” is constant in #

The guarantee is that a query passes fewer than $M$ ones. On this vector at $M = 8$ it passes 7, and it passes 7 at every anchor interval — the bound comes from the sub-block spacing and $L$ only decides how many anchors are stored.

Passing 7 ones means inspecting whatever number of positions holds 7 ones, which at a tenth density is about 70 and at worst 186.

So the operation is constant in ones and linear in the reciprocal of the density in positions, and those are the same number only on a vector that is half ones. Every published statement of the bound is in the first unit; every implementation’s cost is in the third.

The third unit is what closes the gap, and it is why every real implementation of this is written against a population count. Inspecting sixty-four positions is one machine operation, so the seven words above are seven operations rather than a hundred and eighty-six — which this collection has measured directly in another setting and which is the difference between a structure that is theoretically constant and one that is practically fast.

Tightening $M$ tightens the bound and costs bits, which is what makes it a trade rather than a parameter:

Where the structure with the guarantee loses #

The comparison that decides whether the machinery is worth building is against the plain array of sampled positions, and it is not a rout.

At $L = 8$ the two-case structure gives exactly the bound the plain array gives and costs 75% more bits. It only starts winning once its anchor interval is eight times the plain array’s — which is the whole reason the anchors are separated from the sub-block offsets in the first place, and it is a fact about the construction that the description “constant time in $o(n)$ bits” contains no trace of.

And on a sparse vector it loses outright. Hold everything and turn the density down:

The binary search inspects at most 510 positions and 16 words on any of these, for no bits at all.

At one bit in fifty, the structure with the constant-time guarantee inspects 831 positions to the binary search’s 510, touches nearly twice the machine words, and costs 2,304 bits the binary search does not spend. It is better in exactly one unit — the one the theorem is written in — and worse in every unit a processor charges for.

The mechanism is the asymmetry the essay opened with, arriving from the other side. Rank’s directory is indexed by position, so its scan is bounded in positions. Select’s is indexed by rank, so its scan is bounded in ones, and converting that bound into positions requires dividing by a density the structure does not control. At high density the conversion is favourable and at low density it is not, and the crossover on this vector is somewhere around one bit in twenty.

The construction, walked once #

It is worth walking a query through the structure, because the two cases are easy to describe and easy to get wrong, and one of the ways to get them wrong is the rejection this essay’s machinery carries.

Ask for the position of the $k$-th one. Divide $k$ by $L$ to get the stretch it falls in and the offset within that stretch — one integer division, no search. Look the stretch up in the sparse table; if it is there, the answer is written down and the query is over in two array reads. Otherwise divide the offset by $M$ to get a sub-block, read the offset of that sub-block’s first one from the dense table, add it to the stretch’s anchor, and scan forward past at most $M-1$ ones.

Nothing in that walk is a search. Everything is an index computed by arithmetic from $k$, which is what makes the whole thing constant in the analysis’s unit — and the reason it is possible at all is that the anchors re-impose regularity on a sequence that had none. A stretch is $L$ ones wide by construction, so “which stretch” is a division; what varies is how many positions a stretch covers, and the two cases exist precisely to handle both regimes of that.

The failure this admits is silent, and it is the one worth a rejection. Every table above is built once from the vector and none of them holds a copy of it. Change a single bit in the vector afterwards and nothing throws, nothing is out of range, and no query reports an error — select simply returns a position that now holds a zero. The check carried beside this structure clears the bit that a query has just returned and requires the next identical query to answer somewhere that is not a one. It is the same shape as a stale rank directory, and it is the reason both structures are built from an immutable vector in this collection rather than maintained.

The second rejection is smaller and is about the parameters. $L$ must be a whole number of sub-blocks, because the dense table stores one offset per $M$ ones within a stretch of $L$; an $L$ that is not a multiple of $M$ leaves a final partial sub-block whose scan is unbounded, and the bound is then quietly wrong rather than absent. That is refused at construction.

Why the structure exists anyway #

None of that makes select support useless, and it is worth being precise about where it earns its bits, because the answer is not “when the vector is dense”.

It earns them when the query is on a hot path. A binary search over the superblock counts is a handful of dependent memory accesses, each a potential cache miss, and the dependency chain cannot be broken by a wider machine. The two-case structure’s lookup is two independent array reads followed by a short local scan, and locality is the whole of the difference — this collection has measured that distinction elsewhere and it is worth more than the operation counts suggest.

It earns them when a bound is required rather than an average. The binary search’s 510 positions is a worst case over this vector, and a different vector gives a different number; the two-case structure’s bound in ones holds by construction on every vector.

And it earns them where select is called once per output character, which is where it actually appears: walking a wavelet tree, decoding a compressed sequence, iterating the set bits of an index. A structure queried once does not need any of this. A structure queried $n$ times does, and the bits are amortised over the calls rather than over the vector.

One consequence of that locality is worth separating from the rest, because it is the practical reading. A structure whose cost cannot be predicted from a density is a structure that has to be built before it can be budgeted for, and building it requires the vector, which requires the data. Every other size in this family — the payload, rank’s directory, the sample marks — is a function of the vector’s length and a parameter, and can be worked out on paper before anything exists. Select support is the one line in the budget that has to wait for the data to show up, and a design that has committed to a memory footprint before then has committed to a number it cannot yet compute.

What the vector costs beside it #

The support is measured against the vector it supports, which is this family’s standing rule.

Thirteen per cent of the vector, to answer a question the vector could already answer with a binary search over a directory that was there for something else. Whether that is a good trade is a question about how often the question is asked, and it is not a question the size alone can settle — which is why every plate in this family prints what the thing being supported costs beside what the support costs.

The zeros need their own structure #

Everything above answers “where is the $k$-th one”. A great many uses need the other question — where is the $k$-th zero — and the structure just built answers it not at all.

Symmetry makes that easy to underrate. Select over the zeros is the same construction over the complemented vector, so it is the same code and the same parameters, and a reader may reasonably assume it is the same cost. It is not, and the reason is the inversion two sections above: the size depends on how far apart the selected bits are, and complementing a vector changes that completely.

On the vector this essay measures — 65,536 positions, one bit in ten — the ones are spread thinly and the zeros are packed nine to ten. So select over the ones meets the expensive case, and select over the zeros meets the cheap one. The two structures answering mirror-image questions about one vector differ in size by roughly the ratio of the densities, and the expensive one is always the sparser bit.

That matters because the structures that need select need both directions. Walking a wavelet tree upwards from a leaf follows a zero at some levels and a one at others — which branch was taken is what the code says — so a tree with select support has both structures at every node, and the node’s total is the sum of a cheap one and an expensive one rather than twice either. The accounting a reader would do from the table above, doubling the select row, is wrong in a direction that flatters the structure at high densities and understates it at low ones.

There is one consolation and it is worth stating because it is the only place in this essay where the sparse case pays for itself. A vector’s ones and zeros cannot both be sparse. Whichever direction is expensive, the other is cheap, so the sum of the two supports is far better behaved than either — it is largest at a density of a half, where both are moderate, rather than at the extremes where the naive reading would put it.

The case is decided locally, which the totals hide #

The eleven-to-one table is the essay’s most striking number and it is a worst case, because it was measured on a vector whose ones are spread evenly everywhere. Real vectors are not like that, and the structure is better than the table suggests for a reason worth naming.

The sparse-or-dense decision is taken per stretch of $L$ ones, not once for the vector. A stretch whose ones are packed gets an offset table costing a few bits each; a stretch whose ones are spread gets its answers written out. So a vector with a dense head and a thin tail pays the cheap rate over the head and the expensive rate over the tail, in proportion to how many of its ones live in each, and neither region’s cost is contaminated by the other’s.

The structure is therefore adaptive at a granularity no summary statistic of the vector reports. Two vectors with the same length, the same number of ones and the same variance of gap lengths can differ by a large factor here, because what decides the cost is how the wide gaps are clustered — many wide gaps inside a few stretches is cheap, the same wide gaps spread one per stretch is expensive.

That is an unusual shape for a space bound and it is the same one the compressed index’s blocks have: a per-block encoding whose total is a sum over local decisions, so the cost tracks local structure and no global parameter predicts it. In both cases the practical consequence is identical and slightly uncomfortable. The size has to be measured on the actual vector, a size quoted for a density is a size quoted for one arrangement at that density, and the only defensible way to report either structure is to build it over the data in hand and weigh it.

What is not measured here #

A true worst-case constant. The scheme here is the two-level one everybody ships, whose scan is bounded by a parameter. The three-level scheme that achieves a worst case bounded by a universal constant replaces the sub-block scan with a table indexed by a machine word — which is still a constant chosen by the word size, and is the honest form of the claim in every case.

Select on a compressed vector. The vector here stores its bits. A vector stored as a class and an offset per block, which is what makes a compressed index compressed, needs a different construction, and its select is not this one with different constants.

A clock. Every number above is a position inspected, a one passed, a machine word touched, or a bit retained. Which of them dominates on a particular processor is exactly the question this collection refuses to answer from a count, and the three-unit table is the closest it gets.