A rectangle over a permutation

The question at the centre of a phrase index is: which of these $z$ points lie inside this rectangle? The candidates a filter cannot avoid establishes that it is a rectangle and measures what answering it by scanning costs. This essay builds the structure that answers it without scanning, and the interesting part is how little the structure has to store.

A permutation is the easy case, and this is one #

The points are not arbitrary. Every boundary has exactly one rank in the prefix order and one in the suffix order, and both orders are total, so the map from one rank to the other is a bijection on $\{0, 1, \ldots, z-1\}$.

That is what makes the structure cheap. A general set of $z$ points on a $z \times z$ grid needs its coordinates stored — $2z\lceil \log_2 z\rceil$ bits before anything is indexed. A permutation needs half of that in principle and, stored the way below, needs $z\lceil \log_2 z\rceil$ bits including the index: the $x$ coordinates are the positions in a sequence, so they are not stored at all, and the $y$ coordinates are the paths through a tree, so they are not stored either.

The whole structure is a pile of bits saying, at each level, which half of the remaining value range each point’s $y$ falls in.

The construction, in one paragraph #

Take the sequence $y_0, y_1, \ldots, y_{z-1}$, where $y_x$ is the second rank of the boundary whose first rank is $x$. Write one bit per element: zero if the value is in the lower half of $[0, 2^L - 1]$, one if it is in the upper. That is level zero. Now stably partition the sequence — all the zeros first, in their original order, then all the ones — and repeat on each half with its own halved value range. After $L = \lceil \log_2 z\rceil$ levels every group holds one value and there is nothing left to split.

A level is $z$ bits however many groups it contains, because the groups partition the same $z$ points. So the payload is exactly $z\lceil \log_2 z\rceil$ bits, plus the rank directory each level needs to answer questions about itself.

This is the same object rank is the only thing it does built over a text, with values in place of symbols and a balanced shape in place of a Huffman one. The reason it is a different object here is that the query is different: a text’s wavelet tree is asked how many times a symbol occurs before a position, and this one is asked which positions hold a value in a range.

The descent #

A query is a rectangle $[x_0, x_1) \times [y_0, y_1]$. Start at the root with the whole sequence and the whole value range.

If the node’s value range misses the rectangle’s, stop: no point beneath it can qualify. If the node’s value range is contained in the rectangle’s, every point in the node’s slice of the current $x$ interval qualifies, and they can be reported without looking any further down. Otherwise split: the points of the node whose bit is zero go left, those whose bit is one go right, and the $x$ interval maps into each child by a pair of rank operations on the level’s bit vector.

The visited nodes are the ones whose value range straddles an edge of the rectangle, plus the ones contained in it. In a balanced tree of $L$ levels that is $O(L)$ straddling nodes and however many contained ones the answer needs — which is why the descent costs a logarithm and not a range.

The lifting, which is the part that costs #

A node deep in the tree knows how many points qualify and it does not know where they are. The position of a point inside a level-$\ell$ node is a position in a sequence that has been stably partitioned $\ell$ times, and recovering its original $x$ means undoing each partition.

Undoing one is a select. If the point came down the zero branch, its position in the parent is the position of the $k$-th zero, where $k$ is its offset inside the child; if it came down the one branch, the position of the $k$-th one. So reporting a point costs one select per level between it and the root, and reporting $t$ points costs $t \log z$ selects in the worst case.

That is where the “plus one times a logarithm” in the published bound lives, and it is why a query returning every point in the grid should be answered by reading the level-zero sequence instead. The structure is worth having exactly when the answer is small compared with the range — the same condition the previous essay measured and the same one a filter has a selectivity states for filters.

What a rank and a select cost, since the answer is denominated in them #

The descent spends ranks and the lifting spends selects, and this collection has already measured both against the same bit vectors.

A rank is a superblock counter, a block counter and a scan of the remainder — an index larger than what it indexes is the essay about what happens when the directory is not built carefully, and the index that is smaller than the text is where the two-level directory’s own arithmetic is set out. A select is a binary search over the superblock counters and then a scan, which is select is not rank backwards: the two are not symmetric, the second is dearer, and a structure that spends one per level per reported point is spending the dearer one.

That asymmetry is not a detail here. A query reporting $t$ points at $L$ levels costs about $2L$ ranks for the descent and up to $tL$ selects for the lifting, so the lifting dominates as soon as the answer is more than a couple of points. A structure sold as “output-sensitive” is one whose cost is $t$ times a constant, and the constant is a select — which is the most expensive primitive in the whole field.

The measured consequence is the next essay’s subject and it is worth stating here so the structure is not oversold: on the collection this ladder runs on, the grid examines 33 candidates where the filter examines 4,355, and performs 2,471 rank and select operations doing it.

Why not simply store the other rank #

There is a much simpler structure for the same query and it is worth saying why it is not this one, because it is what the index already has.

The index stores rankInPrefix, an array mapping a boundary to its rank in the prefix order. Given the suffix-order range, the filter reads that array for each member — one array read per candidate, no logarithms anywhere. It is faster per candidate than any grid descent, which is exactly why the comparison in the next essay is not the walkover the candidate counts suggest.

What it cannot do is skip. An array indexed by one rank answers “what is this boundary’s other rank” and nothing else; there is no query it supports whose cost is smaller than the range. The grid is not a faster way of doing what the array does, it is the structure for a question the array cannot be asked — the same relationship a search that runs backwards has with a scan, and the sampling that goes the other way has with a walk.

And the array is not free either: three orderings of $z$ boundaries at $\lceil \log_2 z\rceil$ bits each is 3,744 bits on the collection above, against the intersection grid’s 1,696. A reader deciding what to build should notice that the grid replaces one of the three, which makes its true marginal cost smaller than its size.

The leaves have to exist, and the first version’s did not #

A tree of $L$ levels over a value range of $2^L$ ends with nodes covering a single value each. Those nodes have nothing to split, hold no bit vector, and it is tempting not to build them.

The first version of this structure did not, and it lost points. A rectangle whose $y$ range covers one value of a sibling pair and not the other is answered at exactly those single-value nodes: the parent’s range straddles the edge, so the descent does not stop there, and it walks off the bottom of the tree into a node the construction never made. Across the check’s forty random rectangles it lost twelve points of 614, on ten of the forty — and the first one it stopped at held seven and reported six.

The failure is invisible on any wide query, which is the shape worth noticing rather than the bug. A range structure tested on rectangles covering a decent fraction of the grid is tested on the part of the descent that never reaches a leaf. The check that found it compares against exhaustion on forty random rectangles at every width, which is what a check has to do when the object being checked has a fast path and a slow one: check both, and let the slow one be the oracle.

One vector per level, not one per node #

The layout above stores the levels. The obvious alternative is to store the nodes — one bit vector per node of the tree, each holding only its own points — and it is arithmetically identical in payload, because the nodes of a level partition the same $z$ points.

It is absurd in overhead, and this file measured how absurd before it was rewritten. Each bit vector carries a rank directory whose smallest superblock and block entries do not shrink with the vector, so a node holding five bits still pays for two superblock counters and four block counters. Over the roughly $2z$ nodes of the tree that is a directory much larger than the whole payload: the first version of this structure reported 10,094 bits of grid over a 7,285-bit index — 2,328 bits of payload and 7,766 of directory, which is more than three times the thing it is a directory for.

The level layout reports 3,224 bits for the same two grids — 2,328 of payload and 896 of directory. Same points, same queries, same answers, the same payload to the bit, and a third of the total.

The moral is not about wavelet trees. It is that a structure described as “a tree of bit vectors” has an implementation whose cost is dominated by a per-object constant that no asymptotic statement about it mentions, which is the constant the notation drops at the level of a data structure’s layout rather than of an algorithm’s loop. The same directory arithmetic decides the shape of every compressed index in this field, and what is still proportional to n is where this collection first measured it.

The second grid is the same machinery and a different point set #

Propagation asks which phrases copy from a region containing a given position: source at most $p$, source end at least $p + m$. Both conditions are on values rather than ranks, so the coordinates are ranks of those values — the phrases sorted by source give the $x$ axis, and the rank of each phrase’s source end among all source ends gives the $y$.

The query is then a rectangle with two of its sides at the edges of the grid: $x$ from zero to the number of sources at most $p$, $y$ from the number of ends below $p + m$ to the top. Two binary searches to convert the position into ranks, then one descent.

Nothing else changes. The same class, the same levels, the same descent, the same lifting — which is the reason the two are one file and one structure rather than two, and the reason the propagation’s saving could be measured the day the intersection’s was.

Two ways to get a correct-looking structure that is wrong #

Both were found by checking against exhaustion rather than by reading the code, and both produce answers that pass every test asking whether the points reported are inside the rectangle.

A rectangle whose upper edge is exclusive where it is meant to be closed. The suffix-range search returns a half-open interval and the grid takes a closed $y$ range, so passing the interval’s end where its last element is meant drops the top row. On most queries the top row is empty and nothing happens. Shrinking every rectangle by one row across sixty random queries loses sixty points, which is the check.

A grid whose axes have been exchanged. Both coordinates are ranks of the same boundaries, both are permutations of the same range, and a grid built with the roles swapped is a perfectly valid grid over a perfectly valid permutation. It answers rectangles correctly and answers the wrong rectangles: on the check’s collection it reports zero occurrences where there are eight, and every one of the zero is right.

That second one is the one worth carrying, because it has no signature at all. There is no exception, no impossible value, no assertion that could notice — the only symptom is a smaller answer, and a smaller answer from a search is indistinguishable from a pattern that does not occur.

The per-object constant, and where it stops mattering #

The two layouts differ by 6,870 bits over an identical payload, and the difference decomposes into two terms that behave completely differently — which is worth doing, because the second term is the one a bound would call negligible.

A rank directory over a vector of $b$ bits costs a part proportional to $b$ — a block counter of nine bits every sixty-four, a superblock counter of eight every five hundred and twelve, so about 0.156 bits per bit — plus a part that is fixed per vector, being the counters a vector pays for existing at all.

Both layouts hold 2,328 bits of payload, so both owe the same 363 bits of proportional directory. The level layout reports 896, leaving about 530 across sixteen vectors: roughly 33 bits of fixed cost per vector. The node layout reports 7,766, leaving 7,400 — which at the same 33 bits apiece is about 224 vectors, the nodes of two trees that hold more than a single point.

So the entire 6,870-bit difference is one constant times a count, and the count is the only thing the two layouts disagree about: sixteen bit vectors against two hundred and twenty-four.

Written that way it generalises, and the generalisation is sharper than the moral this page draws. A tree-of-vectors layout has about $2z$ nodes, so its fixed directory cost is $\Theta(z)$ bits against a payload of $\Theta(z\log z)$ — formally a lower-order term, and exactly the kind of thing an $o(z\log z)$ absorbs without comment.

Evaluate the ratio. Fixed cost per point comes out near 25 bits here, against a payload of $\log_2 z$ bits per point, so the directory exceeds the payload whenever

$$\log_2 z < 25,$$

which is to say whenever $z$ is under about thirty-three million points.

That is the number worth carrying. The per-node constant is asymptotically negligible and it is larger than the thing it is a directory for at every size any of these structures is built at — a factor of 3.3 here, and still above one at ten million points. A term that becomes lower-order somewhere past the largest collection anybody indexes is not a lower-order term in any useful sense; it is the leading term with an apology attached.

Which is the constant the notation drops with a crossing point rather than an anecdote, and the same shape what is still proportional to n found in an index’s sampling. The level layout does not make the constant smaller — 33 bits a vector is 33 bits a vector — it makes there be sixteen of them instead of two hundred, and that is the whole of the third.

What is being claimed #

A permutation grid costs $z\lceil \log_2 z\rceil$ bits of payload, measured exactly, plus a rank directory that is 38% of the payload at the sizes here and shrinks as a share when $z$ grows.

A rectangle is answered by a descent of $O(\log z)$ straddling nodes, plus one select per level per point reported — so the cost is the answer times a logarithm rather than the range.

The two grids in a phrase index are one structure over two point sets, and the second one’s query is the first one’s with two sides pushed to the edges.

And the structure is easy to build wrongly in ways nothing notices. Both defects above return real points, in the right order, from a correctly built tree. That is the same shape as the failure the occurrences that cross a boundary guards against — a search reporting its primaries and skipping the propagation returns nothing but real occurrences and a fraction of the answer — and it is why every check in this ladder compares against exhaustion rather than against a property.

What has not been claimed here is that any of it is worth it. The descent costs operations, the operations are not the candidates it replaces, and the bits are paid before the first query — which is the next essay and the one after it.