The candidates a filter cannot avoid

An index built on the phrases of a text’s own parse answers a search in two halves. The occurrences that cross a boundary finds the occurrences that straddle a phrase edge, and then produces every other occurrence from those by arithmetic. The first half is a search and the second is a propagation, and both of them are a question about which phrase boundaries satisfy two conditions at once.

That is the sentence this essay is about. Two conditions at once is a rectangle, and the index this collection built does not have a rectangle. It has a scan.

The two conditions, and why they are ranks #

A pattern of $m$ characters crosses a phrase boundary in one of $m - 1$ ways: after one character, after two, and so on. Fix one of them — say the pattern is split into a left half and a right half after $j$ characters. An occurrence crossing a boundary at that split needs a boundary with the left half immediately before it and the right half immediately after it.

The index stores the boundaries twice. Once sorted by the text that follows each of them, which makes “the boundaries whose text begins with the right half” a contiguous range of that order, found by binary search. Once sorted by the text that precedes each of them, reading backwards, which makes “the boundaries whose text ends with the left half” a contiguous range of the other order.

So each condition alone is an interval. A boundary satisfying both is one whose rank in the first order lies in one interval and whose rank in the second lies in the other — a point in a rectangle, on a plane whose two axes are the two orders.

There is nothing figurative about the plane. Both coordinates are integers between zero and $z - 1$, every boundary has exactly one of each, and no two boundaries share either coordinate. The point set is a permutation, which is the most structured possible input to a range query and the reason a published index can answer this in time proportional to the number of answers.

What this collection does instead #

It filters. It takes the smaller of the two intervals, walks it, and asks of each member whether its other rank falls inside the other interval. That is correct, it needs no structure beyond the two orders already stored, and it is what an index with z in its size shipped.

The file that shipped it said so, in the docstring, and counted the cost rather than hiding it:

The published indexes intersect the two boundary ranges with a two-dimensional range structure over a $z \times z$ grid, and propagate secondaries with a second one. Here both are done by filtering the smaller range, and the number of points examined is counted and reported.

That count is what this essay reads. It is the number points in every plate of the parse strand, and until now nothing was drawn against it.

The number #

On a collection of English-like text repeated to sixteen thousand characters, with a pattern of eight characters occurring once per copy:

The search examines 4,355 candidates and reports 32 occurrences. Three of the candidates belong to the crossing search and 4,352 to the propagation. The ratio is 136 candidates per occurrence, and the important thing about it is not its size but its slope.

At one copy the search examines 105 candidates for one occurrence. At two copies, 245 for two. At thirty-two, 4,355 for 32. The occurrences grow with the collection because a collection of copies has an occurrence per copy; the candidates grow faster, because each occurrence’s propagation walks a phrase table that is not shrinking. Per occurrence the figure runs 105, 122.5, 129.8, 133.4, 135.2, 136.1 — climbing towards the size of the phrase table itself.

That last sentence is the whole finding. The cost per answer is converging on $z$, the number of phrases, which is the one quantity this entire family of structures exists to be proportional to. The index is $z$ phrases in size and it is spending $z$ work per occurrence found.

Where the 4,352 come from #

Almost all of the cost is in the second half, and the second half is not the same question.

Propagation asks: given an occurrence at position $p$, which phrases copy from a region that contains all of it? A phrase copying from source $s$ with length $\ell$ contains the occurrence when $s \le p$ and $s + \ell \ge p + m$. Every phrase satisfying that produces a new occurrence somewhere else in the text, and the new one has to be propagated in turn, because a phrase can copy from a region that already holds a copied occurrence.

The implementation walks the phrases sorted by source and stops when the sources run past $p$. On this collection that is about a hundred and forty phrase examinations per occurrence, at every size measured.

The picture is the argument. The condition has two sides — the source starts early enough and ends late enough — and the walk enforces one of them by where it stops and tests the other one candidate at a time. Enforcing both at once is again a rectangle, with one corner at infinity: a stabbing query, the classical name for asking which of a set of intervals contains a point.

Why the crossing search looks cheap and is not #

The first half examines three candidates on this collection, against the propagation’s four thousand, and it would be easy to conclude that the intersection is not where the problem is.

That conclusion is a property of the pattern, not of the method. This pattern’s halves are rare: at most split points one of the two intervals is empty and the split contributes nothing at all. A pattern whose halves are common — a short pattern, a small alphabet, a repetitive collection — has large intervals at every split point, and the filter walks the smaller of two large intervals $m - 1$ times.

At four characters the filter examines five candidates and the rectangle holds one; at sixteen characters both examine eight, because by then every interval is a single boundary and there is nothing for a range structure to remove. A range structure is worth having exactly where the ranges are large and the answers are few, which is the same statement a filter has a selectivity makes about filters, and which the sampling that follows the runs makes about samplings, arriving here as a property of a data structure rather than of a pipeline.

The shape of the cost, stated carefully #

Three quantities, and the collection separates them cleanly because it grows by repeating.

The answer grows with the collection: one occurrence per copy.

The phrase count does not. It is 155 at one copy — the property the index that stores the runs established for the run count and the parse strand inherited and 156 at every point from two copies to thirty-two, which is the finding the phrases a text copies from itself is about and the reason the index is small.

The work grows faster than the answer, because it is roughly the answer times the phrase count. A structure whose size stopped growing at the second copy is doing an amount of work proportional to that size for every occurrence it finds.

That is not a defect of the parse. It is a defect of the intersection, and it is the one the published structures fix.

The rounds, which are the copy structure arriving in the search #

The propagation is a queue rather than a loop, and the reason is the property that makes the whole family awkward: a phrase can copy from a region that already holds a copied occurrence, so an occurrence produced in one round can produce more in the next.

How many rounds it actually runs is a measurement nobody had taken, and it is the same quantity as the one the character that costs a chain measures at extraction time. There it is the price of producing one character: follow the phrase back, and back again, until a literal is reached. Here it is the number of times the queue refills.

It grows with the collection, for the reason the copy depth does: each copy is parsed as a copy of the one before it, so an occurrence in the first copy reaches the last one by a chain of single steps. The consequence for cost is that the candidates are not merely one scan per occurrence — they are one scan per occurrence per round, and the rounds are what a plate about the phrase count cannot see.

That is worth separating from the intersection, because the two have different fixes. A range structure removes the scan. Nothing removes the rounds except a different parse, which is what a parse that will not follow a long chain is about — and that one buys its shallower chains with phrases, which is a larger index and therefore a larger $z$ for the intersection to work over. The two ladders pull against each other, and the plate that shows it is the frontier at the end of the second.

Where else this shape has appeared here #

An intersection done by scanning one side is not a new failure and this collection has met it twice before under other names.

The filter that proposes everything is the same arithmetic in a pipeline: a cheap stage whose output is the whole input, handed to an expensive stage that then does all the work. What made that one visible was computing the selectivity — the fraction of the input proposed — before running anything, and the fraction here is the answer over the range.

The cost is the number of subproblems is the same arithmetic in a table: the cost of a dynamic program is the number of cells rather than the number of cells that matter, and a method that visits only the cells that matter is a different algorithm with a different bound.

And the collection decides which index is small is the reason the question is worth an essay at all. Three compressed indexes over one collection differ by a factor of four in size, and the one this ladder is about — the smallest of the three — is the one whose search cost was measured against nothing.

What “output-sensitive” means here, exactly #

The phrase for an algorithm whose cost follows the size of its answer is output-sensitive, and it is worth being precise about what is being claimed, because the claim is easy to overstate.

A range structure over $z$ points reports the $t$ points inside a rectangle in time proportional to $(t + 1)$ times a logarithm of $z$. It is not free per point and it is not free per query; what it is not is proportional to the range. The difference between “proportional to the range” and “proportional to the answer” is the difference between 4,355 and 33 on the collection above.

The logarithm is not decoration either, and the next essay but one measures it. A structure that reports thirty-three points by performing two and a half thousand rank and select operations has saved something real and has not saved a factor of a hundred and thirty, and a plate counting only candidates would say it had. That is three savings in three currencies again, one level down.

Why it was left out, and what leaving it out cost #

Nothing about this was hidden. The index was built to make a claim about size — that a structure proportional to the phrase count is smaller than one proportional to the run count on a repetitive collection — and it made that claim honestly, with the query cost counted and reported beside it.

What it could not do is say what the query cost would have been. A number counted against no alternative is a number without a scale: 4,352 phrase examinations is either an outrage or the price of doing business, and nothing in the parse strand could tell a reader which.

The cost of the omission is therefore not a wrong number anywhere. It is that every search cost in the parse strand is an upper bound for a structure nobody built, which is exactly how the essays that built it recorded what they had not done. This ladder is the structure, and the four essays on it are: what the rectangle is, what a permutation grid costs to answer it with, what the saving is when the operations are counted rather than the candidates, and what the whole thing costs in bits before a single query is asked.

The honest limit of the measurement #

Three of them, and the third is the one that would change the numbers most.

The collection is copies. Real repetitive corpora are versioned documents and genomes, which are near-copies rather than copies, and the dial that turns one into the other moves both the answer size and the phrase count. At one substitution per hundred characters per copy the phrase count no longer stops growing, and the ratio between work and answer falls.

The pattern occurs once per copy. A pattern occurring many times within each document has a larger answer for the same phrase table, and the ratio improves without anything about the structure changing. The plate above is drawn at one occurrence per copy because that is the case a version history produces, and it is the case where the gap is widest.

And the sizes are small. Sixteen thousand characters is a collection a plate can draw and a quadratic parse can compute. The quantities being compared are counts of primitive operations rather than durations, which is this collection’s habit and is the reason the comparison survives the size: 136 candidates per occurrence at $z = 156$ is a statement about the ratio $z$, not about sixteen thousand.

What it is converging on is not the phrase table #

Climbing towards the size of the phrase table itself is the alarming reading and the six numbers say something more precise. Take the gaps between the measured cost per occurrence and $z = 156$: 51, 33.5, 26.2, 22.6, 20.8, 19.9 at one, two, four, eight, sixteen and thirty-two copies.

Those are not going to zero. Halving the gap’s rate of change with each doubling gives a limit, and fitting the last two points to $c + d/k$ puts $c = 19.0$ and $d = 28.8$ — which then reproduces the measurements at eight, four and two copies as 22.6, 26.2 and 33.4 against 22.6, 26.2 and 33.5.

So the cost per occurrence converges on $156 - 19 = \mathbf{137}$, and it stops there.

Nineteen is the literal count. A phrase that copies from nowhere has no source interval, so the propagation’s walk never examines it — and this collection’s parse has exactly nineteen literals, one per symbol of a nineteen-symbol alphabet, which is the alphabet-sized floor the phrases a text copies from itself measures. The scan’s asymptote is the number of copying phrases, $z - \sigma$, and the residual in the fit is $\sigma$ to a tenth.

That relocates the finding without softening it. The scan is still proportional to a quantity the structure exists to be proportional to, and it is bounded by $z - \sigma$ rather than by $z$.

But it also makes the bound self-limiting on exactly the collections this family is for. As a collection becomes more repetitive, $z$ falls toward its floor of $\sigma$ — and $z - \sigma$ falls with it, all the way to zero. A perfectly repetitive collection has a parse that is almost all literals, and a propagation that examines almost nothing. The 137 here is a statement about a collection whose parse is 88% copying phrases; a collection whose parse is 20% copying phrases would sit at a tenth of it.

Which is the opposite direction from the one the alarm points in, and both are true at once. The cost per occurrence rises with the number of copies and falls with the repetitiveness of the base text, because the first adds occurrences to propagate through a fixed table and the second shrinks the table. The sweep here holds the base text fixed and varies the copies, so it sees only the first.

The four-symbol sweep is the check that ought to follow. There $\sigma = 4$, so the asymptote is $z - 4$ and essentially $z$ — the literal discount vanishes, and the filtering policy is at its worst on the alphabet where a rectangle over a permutation’s grid is cheapest to build. That is the corner where the two ladders’ arithmetic agrees on what to do, and it is not the corner this page’s headline number was taken in.

What is being claimed #

The intersection at the centre of a phrase index is a rectangle query, and this is a definition rather than a measurement: two conditions, each contiguous in one of two stored orders.

Answering it by filtering costs the size of the smaller range, measured at 4,355 candidates for 32 occurrences on a collection of thirty-two copies, converging on one phrase table per occurrence found.

The propagation is the same shape of question with one corner at infinity, and it is where 4,352 of those 4,355 candidates go.

And nothing above says what the alternative costs. That is the next three essays, and the first thing to say about the alternative is that it is not free: it is another structure, over the same $z$ points, that has to be built before the first query and answers nothing on its own.