A count that names every point

The level where compression stops paying closed a strand of four essays about compressing the grid inside a phrase index. The grid is a wavelet tree over a permutation. Every phrase boundary of the text is a point, its two coordinates are the boundary’s rank among reversed prefixes and among suffixes, and a search for a pattern asks, for every place the pattern could be split, which points lie in a rectangle. A bit for every bit set the floor every structure of this kind faces: one that can tell one permutation of 3,612 points from another needs at least $\log_2(3612!) = 37{,}485$ bits. The plain grid holds 43,344 bits of payload, and the strand’s three codings recovered almost none of the 16% between them.

The closing section left one question sharper than the one it answered. The floor applies to a structure that can recover the permutation. A structure that answers only how many points a rectangle holds, never which, “is not bound by it and could in principle be smaller”. The phrase index needs the points, so the question was set aside: whether such a structure is smaller enough to be worth having for some other query. Counting is the other query. A phrase index can say how often a pattern occurs without saying where, and for many uses — whether a phrase is common, whether it occurs at all, how much a query will cost — the count is the whole answer.

Counts name points #

The deferral’s “could in principle be smaller” is the first thing to test, and it turns out not to need a measurement so much as a decoding.

A structure that answers every count exactly can be made to report every point, so it is bound by the same floor. Take a single column, a rectangle one unit wide, and ask how many of its points lie at or below a height $y$. The answer is nought below the column’s point and one from it upwards, so a binary search on $y$ finds the point in $\lceil \log_2 z \rceil$ questions. Doing that for every column recovers the whole permutation. On the phrase index’s grid it takes 42,860 count questions, twelve a column, and the decoded permutation is the stored one point for point.

Decoding this way is slow — 42,860 counts, each a descent of the tree — and it does not need to be fast. The floor is a statement about what a structure must hold, not about what reading it costs, and a decoder that takes an hour proves the same thing as one that takes a microsecond: the counts contain the permutation, so whatever stores the counts stores at least the permutation’s information.

So “counting only” saves nothing, as long as every count must be exact. The information a counter holds is the information a reporter holds. The two differ in what they answer cheaply: a counter can decline to carry the apparatus that lifts each point back up the tree, and the structure paid for before the first query measured some of that apparatus. But the payload cannot go below 37,485 bits for any exact counter, however clever. The deferral’s open door was closed by the definition of a count.

It stays open for one kind of counter. A structure allowed to be wrong can be smaller than any exact one, and that is the shape the answer that is allowed to be wrong gave the streaming summaries: error bought with bits, at an exchange rate that is a measurement. The rest of this essay takes that measurement.

Two counters that are allowed to be wrong #

Cut the tree. A wavelet tree over twelve levels halves the range of heights at each level. Keep only its top $d$ levels and it still counts, exactly, how many points of any column range fall into each of $2^d$ horizontal cells $2^{12-d}$ heights tall. A rectangle’s count is exact for the cells it covers whole. For the two cells its top and bottom edges cut, the counter knows how many points of the column range are in the cell but not where, and estimates them in proportion to the share of the cell the rectangle overlaps. Its size is $d$ levels of the full grid, 4,300 bits a level with the rank directory.

Keep a sample. Keep every $k$-th column’s point, store those in a grid of their own, and multiply every count by $k$. Its size is the grid over $z/k$ points.

Both are asked two sets of rectangles. The first is the phrase index’s own. For 300 patterns of eight and sixteen characters taken from the text, every split of the pattern that leaves both a non-empty prefix range and a non-empty suffix range gives a rectangle, 2,057 of them. The second is drawn the way the operations a candidate count leaves out drew them, 600 rectangles up to an eighth of the grid on each side.

The rectangles a phrase index asks #

The rectangles the phrase index asks hold 2.6 points on average, and 35% of them hold exactly one; drawn rectangles hold 12.6. That is the fact the rest of the measurement turns on. A split of a pattern names a prefix range and a suffix range, and on a collection with this much repetition a long prefix and a long suffix each match a few phrases. Their rectangle is 35 rows tall on average and holds a handful of points, often one. The candidates a filter cannot avoid counted the work of finding those few points without a grid, 136 candidates examined for every occurrence found. The grid’s whole purpose was to make those small answers cheap.

A count of a small answer has no room for error. A rectangle holding one point counted as 1.4 is a rectangle counted as one only by rounding, and counted as 0.6 it has become a wrong answer to the question “does this split occur at all”. The drawn rectangles hold more points, so the same absolute error is a smaller share of their answer.

Bits against counts got right #

Below the floor no counter measured here counts even half of the phrase index’s rectangles right. The grid cut to eight levels is 34,400 bits, 8% under the floor, and gets 46% of them. At ten levels it is 43,000 bits, above the floor, and gets 71%. Only all twelve levels count every rectangle right, which is the exact counter and pays the floor and its directory.

On drawn rectangles the same counter at eight levels gets 71% right, and that is the version of the result a reader would have expected. Drawn rectangles are tall, so most of their points lie in cells the rectangle covers whole and are counted exactly. Only the edges are estimated. The index’s rectangles are 35 rows tall over cells of sixteen rows at eight levels, so they cover two or three cells and their edges cut two of them. Most of their points are in the estimated part.

Sampling is worse throughout. Keeping every second point costs 23,771 bits and gets a quarter of the counts right on both sets, about as well as the tree cut to six levels at a similar size. At every thinner sample it falls further behind. A sample’s count is a multiple of $k$, so a rectangle holding one point is counted as nought or as $k$ and never as one.

Resolution, not redundancy #

The three codings the strand tried before this one all looked for redundancy in the grid. A block, a class and an offset coded each block of a level by how many ones it held and which arrangement it was, and took 7.6% off; the runs a permutation does not leave coded runs and made the grid 17.8% larger, because the permutation’s runs average 2.34 positions against a break-even of six. Each was an exact coding, so each was bounded below by the floor, and each found that this permutation sits close to it. A grid built from a parse of a repetitive text is, level by level, nearly as disordered as a random permutation of the same size.

The cut counter does not look for redundancy at all. It throws away resolution: the bottom four levels of the tree say which of sixteen adjacent heights each point has, and the cut counter simply does not know. That is why it can go below the floor on any permutation, ordered or not, and why its error does not depend on the data’s structure but on the queries’ shape. A rectangle many cells tall loses only its edges. A rectangle one or two cells tall loses nearly everything.

The arithmetic of the floor makes the size of the opportunity plain. The full grid is 51,600 bits with its rank directories, 38% above the floor; its payload alone is 43,344, 16% above. Cut to eight levels its payload is 28,896 bits, 77% of the floor, and with directories 34,400, 92%. A counter that kept the payload of eight levels and found some cheaper way to rank it would sit at three quarters of the floor and count drawn rectangles to within 6% — a real saving for a structure asked large questions, and none at all for this one.

Where the error goes #

Cut to eight levels, the counter gets 96% of empty rectangles right and 49% of those holding one point. An empty rectangle is easy: if no point of the column range lies in the cells it touches, every estimate is nought. A rectangle holding one point is a coin toss, because the point usually sits in a cell the rectangle cuts and the estimate is the share of the cell overlapped, which rounds to one only if the rectangle covers more than half of it. The absolute error grows with the count, but slower than the count does, and the share counted right falls from half to a quarter as rectangles get fuller.

Why one point is a coin toss can be worked through for a typical rectangle. At eight levels a cell is sixteen heights, and the index’s rectangles are about 35 heights tall, so a rectangle spans one or two whole cells and two parts. A point it holds lies in a part-covered cell more often than not. There the estimate is the rectangle’s share of that cell — say five heights of sixteen, 0.31 — and that rounds to nought. Had the rectangle covered eleven heights of the cell, the same point would round to one. Whether a one-point rectangle is counted right depends on where its edge falls inside a cell, which has nothing to do with the point, so it comes out right about half the time.

Read as a test of whether a split occurs at all — nought or not nought — the cut counter does better than as a counter: 96% of empty rectangles come back empty. But that is a different question, a membership test on rectangles, and a structure built for it would not be a wavelet tree.

The error as a share of the answer #

At eight levels the cut counter is off by 6% of the count on drawn rectangles and 39% on the index’s. If a reader wanted a counter for large rectangles, the cut tree is a good one: eight levels count drawn rectangles to within a sixteenth of their size, and a rectangle half the grid tall would be counted closer still, since its edges are a smaller part of it. That is the general fact the deferral was reaching for. Approximate range counting can go well under the permutation’s floor when the ranges are large.

The phrase index never asks a large range. Its patterns are tens of characters at most and its rectangles a few dozen rows. For the query this index exists to answer, the floor is not a theoretical bound that a cleverer structure might slip under. It is the size of the answer.

What the deferral was really asking #

The deferral was framed as a question about size: could a counting structure be smaller? There are two exact answers and one measured one.

A counter that must be exact cannot be smaller, because counts are a complete description of the points. That is the decoding, and it holds for any structure on any permutation.

A counter that may be wrong can be smaller by any amount, and what it buys depends on the shape of the rectangles. On rectangles that are large compared with the cells it keeps, it is nearly exact. On rectangles the size of a cell or two, it is a guess, and the index’s rectangles are that size because the index’s grid was built to answer specific, narrow questions.

So the closing section’s “some other query” is not a query this index asks. Where a structure is wanted that counts large rectangles of a permutation — how many phrases in a band of the suffix order begin in a band of the prefix order — the truncated tree is the structure, and it is a prefix of the grid already stored. That makes it free: a count at depth eight is a descent that stops four levels early. A rectangle over a permutation built the grid to report, and the same grid, read only to its eighth level, is an approximate counter at no extra space, the four levels under it unread rather than removed.

What the counts were checked against #

The decoding is checked, not argued. The 42,860 questions are asked of a counting function and the permutation they decode is compared with the stored one; a counter that lost any point would fail. The truncated counter at twelve levels is checked to count every rectangle exactly, since at that depth its cells are single heights.

One collection, at one divergence. The grid is the phrase index’s at five per cent divergence, the setting of the whole strand. A less repetitive collection has more phrases and longer rectangles in the suffix order, so its rectangles would hold more points and the cut counter would do better on them. That was not measured.

Estimates within a cell assume an even spread. The cut counter estimates the part of a cell a rectangle overlaps in proportion to its height. A counter that also kept a count of points in each half of each cell — which is one more level, by another name — would do better at a price the plates already show.

Still open: a structure that knows only whether #

The cut counter does one thing well on the index’s rectangles: an empty rectangle comes back empty 96% of the time at eight levels. A phrase index answering “does this pattern occur?” needs only that, split by split, and stops at the first split that says yes. The candidates a filter cannot avoid found that most of a search’s cost is splits that come to nothing, so a cheap test that most splits are empty would do most of the work of an existence query.

The measurement that follows builds the cheapest such test from the grid itself, by stopping the descent at depth $d$ and answering “possibly yes” when any cell the rectangle touches holds a point of the column range, and asks it of every split of patterns that occur and patterns that do not. It counts false yeses, the splits a full search must still check, and bits. The prediction is that at six levels, half the grid, the test turns away nine in ten empty splits and never turns away an occupied one, because a false no is impossible by construction. The question is whether existence, unlike counting, is a query a phrase index can answer for less than its floor, or whether the splits that come to nothing are the ones whose rectangles sit closest to points they miss.