A looser budget wastes a larger share

An optimisation usually helps least where it is needed most. A cache helps until the working set exceeds it; a filter helps until the selectivity falls; a bound helps until the search space opens up.

This one goes the other way, and the direction is worth measuring because it decides where the operation belongs in a system.

The sweep #

Eight-character patterns over eight thousand characters of a twenty-symbol alphabet, at zero, one and two errors.

Zero errors. The search follows one path — the pattern’s own characters — so there is one live extension per level and σ − 1 dead ones at each. Dead share 31.3%. Ranks: 6,200 for the loop against 1,078 for the descent, a saving of 5.8.

One error. The search branches once at each level and reaches narrower intervals. Dead share 54.8%. Ranks: 168,000 against 24,086, a saving of 7.0.

Two errors. Dead share 74.9%. Ranks: 2,059,600 against 223,460, a saving of 9.2.

Three things rise together: the absolute work, the dead share, and the saving.

The absolute figures are worth reading beside the shares because they say what regime the search is in. Six thousand two hundred ranks at zero errors, a hundred and sixty-eight thousand at one, two million at two — the work multiplies by twenty-seven and then by twelve. That is the branching factor of an approximate search, and it is the reason this kind of search is expensive at any budget above one on a text of any size.

The search that spends a budget measured that growth on DNA and found the same shape at smaller constants. What this sweep adds is that the composition of the work changes as it grows, and not in the direction that makes it easier to bear.

Why the share rises #

A dead extension is one whose character is absent from the current interval, so the dead share is 1 − E[d]/σ where d is how many distinct symbols the interval holds.

An interval of w rows over σ symbols holds about σ(1 − (1 − 1/σ)^w) distinct symbols. At σ = 20 that is 5.2 at w = 6, 12.6 at w = 20, and 19.9 at w = 100.

So the dead share is a function of the interval’s width, and the budget’s effect is entirely through the widths the search reaches.

A larger budget lets the search take mismatching characters, which are rarer than matching ones, so it descends into narrower intervals. It also lets it go deeper before running out — a zero-error search dies as soon as a character is absent, and a two-error search continues past two absences. Both push the width distribution downward.

That is the whole mechanism, and it means the rising dead share is not a property of approximate matching but of interval width. Anything that narrows the intervals a search visits — a longer pattern, a rarer query, a larger alphabet — has the same effect.

The coupon-collector expression also says how sharp the transition is, and it is sharper than a reader might expect. On twenty symbols the interval width at which half the alphabet is present is about fourteen rows; at six rows a quarter is present and at forty rows nearly all of it. So the dead share goes from 74% to 5% over a width range of six to forty.

A search’s intervals span that whole range in a single query — wide at the top, narrow at the bottom — so the aggregate dead share is a weighted average over a distribution that is bimodal in effect. That is another reason a single number for “the dead share” is a summary of something with structure, and it is why the plate reports it at three budgets rather than once.

What that means for where to apply it #

An optimisation whose value rises with the problem’s difficulty belongs in the hard path rather than in the fast path, and this one is the reverse of the usual advice.

A system doing mostly exact lookups with occasional fuzzy fallback should put the enumeration in the fallback. The exact path gets nothing from it — the saving that is a loss measures the enumeration costing about twice the walk on a search that knows its character — and the fallback gets between five and nine.

That is a rare shape and it is worth naming: an optimisation that is a pessimisation on the common case and a large win on the expensive one. The correct deployment is a branch on the query type rather than a global replacement, which is more code than a global replacement and is what the numbers say.

The absolute numbers, which are the reason #

The shares are the mechanism and the absolute counts are why anyone cares.

At two errors the published search spends two million fifty-nine thousand six hundred bit-vector ranks for twelve patterns. That is a hundred and seventy thousand ranks a pattern, on a text of eight thousand characters.

The enumeration spends two hundred and twenty-three thousand — eighteen thousand a pattern.

A search costing a hundred and seventy thousand operations on eight thousand characters is a search that does not scale to a real text without something changing, and this changes one factor of nine of it. That is not enough on its own — the field’s answer to a two-error search on a large text is a partitioning scheme rather than a faster inner loop — and it is a factor that composes with those.

The search that starts in the middle is where the partitioning schemes were measured here, and the two are independent: a scheme decides which searches to run and the enumeration decides what each costs.

Where the budget stops mattering #

The sweep stops at two errors and it is worth saying what happens past it, because the trend cannot continue indefinitely.

As the budget grows the search eventually visits every interval in the index, at which point the dead share is the average over all intervals rather than over narrow ones — and the average over all intervals includes the root, where nothing is dead.

So the dead share rises, peaks, and falls back toward the census figure as the budget approaches the pattern length. At a budget equal to the pattern length every string of that length matches and the search is a full traversal.

That is a degenerate regime nobody runs and it bounds the trend. Between zero and about a third of the pattern length — which is where real approximate matching lives — the share rises monotonically, and the three points measured are all in that range.

The pattern length, which moves with it #

The budget is not the only dial and the two interact, which the sweep above holds fixed at eight characters.

A longer pattern at a fixed budget reaches narrower intervals, because more characters have been matched before the search gets deep. So a twelve-character search at one error has a higher dead share than an eight-character one.

A shorter pattern at a fixed budget is looser in relative terms — one error in four characters is a lot of freedom — so it stays in wide intervals and has a lower share.

What actually determines the regime is roughly the ratio of budget to length, and the three points here are 0, 1/8 and 1/4. A workload at 2/12 sits between the second and third.

That is worth stating because a factor quoted at “one error” is not comparable across pattern lengths, and read-alignment workloads use patterns of a hundred characters with budgets of five — a ratio of 1/20, which is tighter than any point here.

The other quantity that rises #

There is a third thing rising with the budget and it is the one that eventually decides whether any search is affordable: the number of occurrences reported.

A zero-error search reports the pattern’s exact matches. A one-error search reports those plus everything within one edit, which on a text of eight thousand characters and a twenty-symbol alphabet is a much larger set. A two-error search reports a set larger again.

That matters because the enumeration removes work from the search and not from the reporting. Once the intervals are found, turning their rows into text positions costs LF steps proportional to the sampling gap, per occurrence — and a search whose occurrence count is multiplying by ten per error will spend more on locating than on searching at some budget.

So the factor of nine at two errors is a factor of nine on a component whose share of the total is falling. That does not make it worthless; it makes it a factor on the part of the query that the budget is inflating fastest in operations, while a different part inflates fastest in output.

The composition is not measured here and the two parts are measured separately elsewhere: every occurrence at the same price is where locating’s cost per occurrence was pinned down. Putting them together for a specific budget and sampling rate is arithmetic a system can do and this collection has not.

On DNA, which is where the work is #

Repeating the sweep on four symbols gives a much flatter picture: 9.5% dead at no errors, 18.9% at one, 28.9% at two. Savings of 2.7, 2.8 and 2.9.

The share still rises and the saving barely does, because the saving’s ceiling on four symbols is log₂ 4 = 2 at the worst case and 4 at the best, and there is nowhere to go.

So the encouraging shape of this essay — the operation is worth most where the search is most expensive — is a property of large alphabets. On DNA the operation is worth about the same everywhere, which is 2.8.

Two at binary, five at twenty-six makes that argument in full. The point here is narrower: the budget dependence is also an alphabet effect, and a system tuning its fallback threshold on protein numbers would be tuning on the wrong curve.

The budget is not the only way to loosen a search #

Three other query shapes produce the same effect and are worth naming, because a system may meet them without ever calling anything an error budget.

A wildcard. A pattern with a dot in it branches over every symbol at that position, which is exactly one level of full branching. A pattern with three dots is a three-level branch, and the intervals below it are as narrow as a three-error search reaches.

A character class. A pattern with [aeiou] branches over five characters rather than one, and the fifteen absent ones are dead extensions in the loop.

A regular expression over an index. Every alternation and every closure is a branch, and the search visits an interval per state of an automaton — which is a large amount of branching at every position.

All three have the same shape as an error budget: they multiply the number of extensions attempted and narrow the intervals reached, so the dead share rises and the enumeration’s value rises with it.

The last is the interesting one because the branching there is not bounded by a small integer. An error budget of two is two levels of branching; a regular expression can branch at every position of an arbitrarily long match. So the regime this sweep’s right-hand end approaches is the ordinary regime for an index walked by an automaton, and the operation’s value there should be at the top of the range measured here or above it.

That is a prediction rather than a measurement — nothing in this collection walks an index with an automaton — and it is the kind of prediction the sweep’s shape licenses.

What a threshold would look like #

Putting the pieces together, a system deciding when to use the enumeration has a threshold and the threshold has three arguments.

The alphabet, which sets the range. Below about eight symbols there is nothing to decide.

The budget-to-length ratio, which sets where in the range the search sits. Below about 1/16 the search is nearly exact and the enumeration is closer to a loss.

Whether the search branches at all. Which is the only one of the three that is a hard switch rather than a gradient.

The third dominates and the first two are refinements. A system that uses the enumeration for every branching search and the walk for every exact one has captured almost all of the available benefit, and tuning the other two buys a few per cent.

That is a comfortable place to end a tuning discussion and it is worth saying why it is comfortable: the switch is on a property of the query — does it branch — which is known before the search starts and does not need measuring. That is the same property the threshold that reaches zero found made a filter’s threshold usable: a decision that can be taken from the query rather than from the data is a decision that does not have to be tuned.

Two ways to spend a budget, and only one of them helps here #

An error budget can be spent in two places and the sweep above spends it in one, which is worth flagging because the other behaves differently.

Spent on the pattern, which is what a backtracking search does: at each position, try the pattern’s character for free and every other character at a cost of one. That is the search measured here.

Spent on a partition, which is what a filtering scheme does: cut the pattern into k + 1 pieces, observe that one piece must match exactly, search for each piece exactly and verify the candidates. The q-grams an error cannot destroy is that argument and the search that starts in the middle is the version that runs inside an index.

The enumeration is worth a great deal to the first and almost nothing to the second, because a partitioned search’s pieces are searched exactly: it knows its characters and never branches. So a system that has adopted a partitioning scheme has, incidentally, moved itself out of the regime where this operation pays.

That is not an argument against partitioning — the schemes are worth far more than a factor of nine — and it is an argument for measuring which regime a system is in before quoting either. A search doing both, which is what a real aligner does, has an exact phase where the enumeration is a small loss and a verification phase where it may be a large win.

The general shape #

Two things in this essay generalise past the operation.

An optimisation’s value can be measured against the difficulty of the problem, and the sign is worth knowing. Most help less as the problem hardens. This one helps more, and the reason is structural — it removes work proportional to the search’s own branching, so a search that branches more has more removed.

A share that rises with a dial is not the same as a saving that rises with it. The dead share rises from 31% to 75% — a factor of 2.4 — and the saving rises from 5.8 to 9.2, a factor of 1.6. The gap is that removing three quarters of the work is a factor of four and the descent’s own cost is not zero.

The branches that find nothing is where the dead share is counted directly and where the factor of seven at one error is decomposed into its two halves. A reader given only the shares would over-predict the savings by half. That is a small instance of a general habit this collection has: report the quantity the mechanism produces and the quantity a caller pays, because the relationship between them has a constant in it.