The branch that cannot reach an answer

The branches an error opens measures a bounded-error index walk with one pruning rule in it: stop when the interval is empty. The tree it explores multiplies by an order of magnitude for every error allowed — 16, 314, 3,875, 39,957 interval extensions at budgets of zero, one, two and three.

The errors the rest of the pattern needs builds a second rule: stop when the budget remaining is less than the errors the rest of the pattern must cost. This essay is what that removes.

The measurement #

Sixteen-character pattern, four thousand characters of four-symbol text, four planted occurrences:

The occurrence counts are identical on both sides at every budget. That is checked before anything else is reported, because a pruning that saves work and loses answers is trivially available and is what this whole ladder is exposed to.

The share grows with the budget, and that is the whole argument #

At a budget of zero the walk is an ordinary backward search — sixteen extensions, one per pattern character, no branching. There is nothing to prune and the bound removes nothing.

Every unit of budget added multiplies the tree by roughly ten, and the states the bound removes are the ones deep inside that multiplication: a state that has already spent most of its budget and still has a long stretch of pattern ahead of it that occurs nowhere. Those states are rare at small budgets and dominant at large ones.

So the pruning’s value grows with exactly the thing that makes the search expensive. That is the property a pruning must have to be worth a second index, and it is not automatic — a rule removing a constant share of a tree that grows by a factor of ten per error is a constant-factor improvement on an exponential, which is a different and much weaker kind of help.

Where the share flattens, and what is left #

48.1%, 68.5%, 69.8% is not a straight line, and the flattening says what the bound cannot see.

What survives pruning is states whose remaining pattern occurs perfectly well somewhere in the text and which will fail anyway, because it does not occur where this alignment needs it. The bound is computed from the pattern and the text’s contents; it knows nothing about the interval the walk is currently standing in.

A rule that did know would be a filter: propose the positions this state could still reach, look at the text there, and abandon the state if none of them work. That is exactly the seed-and-extend strategy of the filter that feeds the table, and it is not available here, because this search reads no character of the text at any budget — which is the property that makes it an index walk rather than a filter, and the property the search that spends a budget exists to demonstrate.

So the residue is the price of the seal, and it is about a quarter of the tree.

The alphabet decides almost everything #

The sharpest result on this ladder, and it is a factor of a hundred.

At a budget of two on three thousand characters, the share of the tree removed is:

• two symbols: 0.8% — 5,396 extensions, 5,351 after pruning
• four symbols: 70.8% — 3,742 becomes 1,092
• twenty-six symbols: 80.5% — 10,348 becomes 2,020

The reason is the arithmetic in the previous essay, and it is worth restating because everything on this ladder follows from it: a piece of length $\ell$ over $\sigma$ symbols occurs in $n$ characters with probability about $n\sigma^{-\ell}$, so pieces stop occurring after about $\log_\sigma n$ characters. On two symbols that is eleven characters, on a fourteen-character pattern — so $D$ reaches one, at the very end of the pattern, and prunes nothing that was not about to end anyway. On twenty-six symbols it is two and a half characters, so $D$ climbs five times along the same pattern and cuts the tree off near its root.

A pruning built on absent substrings is worth nothing on an alphabet where nothing is absent. That is a clean statement and it is the kind this collection looks for: not “the alphabet affects performance” but a mechanism, an arithmetic prediction, and a hundred-fold measurement across the range.

What a pruned state would have become #

It is worth looking at one abandoned state concretely, because “prunes 70% of the tree” is a number about a shape nobody has drawn.

Take the pattern at a budget of three, standing at a state with six characters left and one unit of budget remaining. The bound says those six characters need at least two errors — because two disjoint pieces of them occur nowhere in the text. So no completion of this state can finish inside the budget, whatever it does next.

Without the bound the walk expands it anyway: four characters of alphabet times a match-or-substitute, plus an insertion and a deletion, at every one of the six remaining positions, until either the budget runs out or the interval does. That subtree is a few hundred extensions and every leaf of it fails.

The pruning is therefore not shaving branches at the edge of the tree. It is removing whole subtrees near the middle, and the size of what it removes is exactly the size of what would have been explored below a state that was already doomed. That is why the share is large and why it grows with the budget: a deeper budget means more levels below each doomed state.

The alphabet cuts both ways, again #

There is a second effect and the two do not point the same way, which the search that spends a budget already found: the unpruned tree is 5,396 extensions on two symbols, 3,742 on four and 10,348 on twenty-six. Not monotone.

A wider alphabet branches more at every state, which grows the tree, and empties intervals sooner, which shrinks it. Four symbols is where the two balance on this pattern length.

Adding the pruning changes the picture completely: 5,351, 1,092, 2,020 after pruning. The interior optimum is still there and it has moved — before pruning the two-symbol case is half the twenty-six-symbol one, and after it is more than twice — so the pruning does not merely scale the curve, it re-orders it.

That is worth stating as a general shape. A parameter with two opposing effects can have its sign changed by a technique that only exploits one of them, and a benchmark run at a single value of that parameter will report the technique’s value wrongly in either direction.

How the two policies are compared, and why that needed care #

Every row of the table above is one text, one pattern, one index, and two walks over it. The index is built once and handed to both, so a difference between the rows cannot be a difference between two Burrows-Wheeler transforms or two samplings.

The occurrence sets are compared before anything is reported, and the comparison is on positions rather than on counts: two searches returning the same number of different positions would pass a count check and are exactly what a subtly wrong pruning produces.

The bound’s own cost is counted separately and in its own currency, so that a plate about the tree is about the tree. Folding the 72 ranks into the extension count would have made the pruned walk look worse by a constant belonging to a different structure, and folding the walk’s own ranks into it would have made both look worse by a constant belonging to neither.

That discipline is one run, four counts, four answers applied to two variants of one algorithm rather than to four algorithms, and it is the reason a 70% figure can be quoted without a caveat about what was included.

What it does to the crossing against the table #

The comparison this pruning was expected to move: at what budget does walking the index cost more than filling the whole rectangle a dynamic-programming table would?

The table is $n \times m$ cells at every budget — 48,000 here — because its size is the text times the pattern and neither depends on $k$. The unpruned walk passes it at a budget of four, at 303,788 extensions. The pruned walk, counting the bound’s own 72 ranks against it, passes it at a budget of four as well, at 107,809.

The crossing does not move. The tree multiplies by an order of magnitude per error and the pruning removes a constant two thirds of it, so it buys about a fifth of one budget — not enough to reach the next integer.

That is a negative result and it is the honest one. A two-thirds saving on a quantity that grows tenfold per step moves a threshold by $\log_{10} 3 \approx 0.5$ of a step, and thresholds are integers. The essays that deferred this pruning guessed it would “move the crossing against the table by an unmeasured amount”; the measured amount is less than one budget.

Why it is still worth having #

Two reasons, and neither is the crossing.

The constant is enormous where it is not a threshold. At a budget of three the pruned walk is 12,051 extensions against 39,957 — well inside the region where the walk beats the table either way, and a factor of 3.3 on the cost of every query in it. A user who runs a budget of two or three, which is what a real approximate search does, pays a third of what they would have.

And on a longer pattern over a wide alphabet it is a factor of eight. The crossing analysis above is on four symbols. On twenty-six with a sixteen-character pattern the pruned walk is 24,254 extensions against 187,692 at a budget of three, and the share removed is still climbing at the top of that sweep rather than flattening.

So the summary is the one this collection reaches often enough to have a thread for it: the technique’s value is a strong function of a parameter that the natural benchmark holds fixed, and the benchmark’s answer is neither wrong nor general.

The bound is not the only thing that shrank #

One number in the table above deserves separating out, because it is the one a reader would use to decide.

The extensions removed at a budget of three are 27,906 and the bound’s own cost is 72 rank operations. That is 388 extensions removed per rank spent — a ratio so lopsided that no plausible exchange rate between the two acts changes the conclusion, which is unusual on this site and worth saying when it happens.

The cost that does matter is not in this essay. It is the second index, and the third essay on this ladder is about it: computing $D$ needs an FM-index over the reversed text, which is 17,033 bits against the forward index’s 17,032 — the same structure again, for a pruning.

Where a constant factor does and does not matter #

The two results in this essay point opposite ways and the tension is worth naming rather than resolved.

A three-quarters saving is large. On any query a user actually runs — budgets of one, two or three — it is the difference between a search costing 40,000 operations and one costing 11,000, and no reader would decline it.

A three-quarters saving is also nothing against an exponential. The crossing against the table is where the walk’s cost passes a fixed number, and a cost multiplying by ten per step passes any fixed number at the same step whether it is divided by four first or not.

Both are true and they answer different questions. “how much does a search cost” is answered by the constant; “at what budget does a table become the cheaper structure” is answered by the exponent, and the exponent is untouched. This collection has the same pair on record for a different structure: the constant the notation drops is the essay about the first question and a limit is not a prediction is about the second, and the point of having both is that a technique can be excellent by one and irrelevant by the other.

The way that reads as advice: a pruning changes what a search costs and not what it is. Changing what it is requires changing the branching factor or the depth, and nothing in this ladder does either.

Where the constant matters most is next to the crossing #

The crossing does not move and the constant is enormous are both stated and they are treated as separate findings. They are the same finding read at two budgets, and putting the numbers together says which budget to care about.

The table is 48,000 cells at every budget. The unpruned walk is 39,957 extensions at a budget of three and 303,788 at four; the pruned walk is 12,051 and 107,809. So the continuous crossing moves from about 3.1 to 3.6 — the half-step the $\log_{10} 3$ arithmetic predicts — and the integer crossing stays at four.

But look at the margin at three, which is the budget a real approximate search runs. Unpruned, the walk beats the table by $48{,}000/39{,}957 = \mathbf{1.20}$. Pruned, by $48{,}000/12{,}051 = \mathbf{3.98}$.

The pruning is the difference between barely winning and winning by four, at exactly the setting where the choice between the two structures is live. A twenty per cent margin is inside any reasonable uncertainty about what a rank costs against a table cell; a fourfold one is not.

And that generalises in a direction the constant factors are nothing against an exponential framing misses. A constant multiplies the margin, and the margin is smallest next to the crossing — so a constant-factor saving is worth least where the two curves are far apart and most where they are close. At a budget of two the walk beats the table by 12.4 unpruned and 39.3 pruned, and nobody’s decision turns on that. At three the same constant decides the structure.

So the two results sit in a definite order rather than in tension. The crossing is an integer and a constant cannot move it, which is the exponent’s business and is why the pruning does not extend the range of budgets the index walk can serve. The margin at the budgets inside that range is what the constant multiplies, and a factor of 3.3 applied where the margin was 1.2 is the whole practical value of the technique.

Which is the constant the notation drops and a limit is not a prediction not merely answering different questions but answering them at different points on one axis. The first governs everywhere except the last step before the crossing; the second governs the step itself; and a technique evaluated only at the crossing will be reported as worthless by a measurement that is entirely correct.

What the numbers would look like on a text worth searching #

Everything above is measured on four thousand characters, which is the size at which the whole dynamic-programming table can be filled as an oracle. A reader wanting to know what the pruning is worth on a real reference should extrapolate carefully, and the extrapolation has one term that moves and one that does not.

The tree’s growth per error is a property of the alphabet and the pattern, not of the text’s length: the branching is $\sigma+1$ at each state and the depth is $m+k$, and the intervals empty at a rate set by $\log_\sigma n$. So a longer text makes intervals empty later, which makes the unpruned tree larger and — for the same reason — makes $D$ climb later, which makes the pruning weaker.

The bound’s height falls as the text grows: a piece of the pattern that occurs nowhere in four thousand characters may well occur somewhere in three billion. On a genome-sized reference $D$ reaches perhaps one or two for a hundred-character read, where here it reaches two for sixteen characters.

So the honest extrapolation is that the pruning is weaker on a longer text at a fixed pattern length, and stronger at the longer patterns a longer text is searched with. Both effects are the same arithmetic — $\log_\sigma n$ — and neither is measured here, which is why the plates are drawn at the size where the oracle exists rather than at the size where the technique is used.

What is being claimed #

The pruning removes 48%, 69% and 70% of the search tree at budgets of one, two and three, on four-symbol text, with identical occurrence sets on both sides.

The share grows with the budget and flattens at about seventy per cent, and what remains is the part of the tree only the text could rule out.

The alphabet moves it from 0.8% to 80.5%, and the mechanism is the arithmetic of when a random piece stops occurring. On the twenty-six symbol sweep at a longer pattern the share is still climbing at the largest budget rather than flattening, which is the same mechanism seen from the other end: a bound that reaches high enough cuts the tree off before the multiplication starts.

It does not move the crossing against the whole table, because a constant-factor saving on a quantity that grows tenfold per error moves an integer threshold by less than one.

And it costs 388 removed extensions per rank operation spent — before the second index, which is the next essay.