The search that starts in the middle

Four ways of consuming one pattern. The same index, the same six positions found, the same check against comparing the pattern at every position of the text — and 830, 877, 447 or 303 interval extensions to get there.

Nothing about the problem changed between those numbers. What changed is the order the pattern’s characters were fed to the index in, and the constraints the search was allowed to impose because of that order.

The pigeonhole, used differently #

Cut a pattern of m characters into k + 1 pieces. If the whole pattern matches somewhere with at most k errors, those errors fall into the pieces, and k errors cannot touch k + 1 pieces — so at least one piece matches exactly.

That is the observation the filter strand is built on. The q-grams an error cannot destroy uses it one way: search for each piece exactly, then verify the neighbourhood of each hit. The pieces are found by an exact matcher, the verification is a table computation, and the index is a lookup device.

A search scheme uses the same observation inside the index. Instead of finding a piece and then leaving, the search begins at a piece, matches it with the budget set to zero, and then extends outwards through the rest of the pattern with the budget opened up.

The difference matters because of where the two spend their work. A filter’s cost is a candidate count times a verification cost, and the filter that proposes everything is the essay about that product collapsing. A scheme’s cost is a tree, and the tree’s shape is decided in its first few levels.

Why the first levels are what matter #

An index walk with an error budget branches. At each pattern character it can match — one extension — or spend an error, which means trying every other symbol.

So the tree multiplies. On four symbols, an error at some depth turns one live state into up to four, and each of those goes on to produce its own subtree. The branches an error opens measured the multiplier at between eight and twenty per error depending on the alphabet, which is a very steep growth for k of two or three.

A constraint applied at depth two therefore removes far more than the same constraint applied at depth twelve: it removes everything the pruned branch would have produced. Forbidding errors in the first piece searched is the strongest constraint of that kind available, and its whole value depends on that piece being searched first.

It is worth putting a number on how steep that is, because the intuition understates it. At two errors over four symbols the plain walk explores 772 extensions for a pattern of eighteen characters; at three it explores 2,932. The pattern did not change and the text did not change — one more error was allowed, and the tree nearly quadrupled.

Against that, the cost of any constraint imposed at the root is enormous and the cost of the same constraint imposed near the leaves is nearly nothing. That asymmetry is the whole reason a schedule is worth having, and it is the reason a schedule is worth having more the larger the budget is.

What a unidirectional search cannot do #

A backward search consumes the pattern from its last character. Its intervals are always the rows for a suffix of the pattern, and to reach the middle piece it must pass through the last piece first.

So it cannot demand that the middle piece be exact without having already searched the pieces to its right, with the budget open, and paid for the tree that produces. By the time it arrives at the middle, the constraint it could impose there is worth very little.

What it can do is the pigeonhole’s weaker form: run k + 1 separate searches, the i-th of which insists that piece i is exact. Each of those searches still has to reach piece i, so all but one of them is doing exactly the walk described above. That is the pigeonhole row on the plates, and it is a genuine improvement — 447 extensions against 830 — because most of its searches die early.

A bidirectional index removes the “has to reach it” clause. A search can begin at any piece and grow outwards, so the exact piece is at the root of the tree in every one of the scheme’s searches.

The measurement #

Fifteen characters, two errors allowed, four thousand characters of four-symbol text with the pattern planted six times at two errors each.

All four found the same six positions with the same error counts, checked against comparing the pattern at every position of the text.

A factor of 2.74 between the first row and the last, on a problem where nothing but the order of consumption differs. And the ranks fall further than the extensions do — 2.81 — because a scheme’s dead extensions are concentrated where intervals are wide and each of them is one rank rather than a subtree.

The saving grows with the budget #

At one error the ratio is 1.31. At two it is 2.22. At three it is 3.14.

That is the shape the argument predicts, and it is worth checking rather than assuming, because the opposite is also arguable — a larger budget means more errors to distribute, which means more searches in a pigeonhole-style scheme and more overlap between them.

What settles it is that the tree multiplies and the searches only add. Three searches at k = 2 explore three trees, but each is rooted at a constraint that removes a factor of the branching, and a factor beats a summand as soon as the budget is more than one.

At k = 1 and k = 3 the scheme and the pigeonhole coincide, because at those budgets the enumeration that produced the scheme finds nothing better than the pigeonhole’s bounds. At k = 2 it finds a triple whose bounds are tighter, and that is where the extra factor of 1.3 comes from.

Why three searches are not three times the work #

A reader meeting a scheme for the first time reasonably asks why running three searches is not three times as expensive as running one.

The answer is that two of the three die almost immediately. Each search begins by matching its own piece exactly, and an exact match of five characters over four symbols narrows the interval to a handful of rows or to none at all. A search whose first piece has an error in it — which is two of the three, for any given occurrence — finds nothing at that first step and stops.

So the three searches share the text between them rather than each paying for all of it, and the total is closer to one search’s worth of surviving states plus two searches’ worth of first pieces. The plate that shows this is the dead-extension one: the scheme’s 303 extensions include 205 that found nothing, which is a higher share than the plain walk’s 391 of 830 and a much smaller number.

Where the pieces go #

A pattern of fifteen characters cut into three pieces gives five, five and five. That is the obvious cut and it is not obviously right.

The first piece searched is the one that must be exact, and a longer first piece is a stronger constraint — it narrows the interval further before any branching starts. A shorter first piece leaves more of the pattern to be searched under the budget. The best cut is therefore not equal, and it depends on the alphabet, since a piece’s selectivity is σ to the power of its length.

Nothing here optimises it. The pieces are equal, and that is stated rather than tuned, because a strand comparing four schedules has to hold everything else fixed — a scheme measured with its own best cut against a plain search measured with an arbitrary one would be measuring two things at once. What the equal cut costs is a deferral, and it is a real one: the same pattern with pieces of six, five and four is a different measurement and nothing here takes it.

The equal cut also interacts with the budget in a way worth naming. At k errors there are k + 1 pieces, so a longer pattern is cut into the same number of longer pieces and a larger budget cuts the same pattern into more, shorter ones. At three errors a fifteen-character pattern gives pieces of four, and a four-character exact match over four symbols selects one row in 256 — which on a text of four thousand characters is fifteen candidate rows before any branching starts.

That is the point at which the first piece stops being a strong constraint, and it is the same collapse the filter strand measured from the outside. The difference is where each is left: a filter that stops being selective has to verify everything, while a scheme that stops being selective has merely lost its advantage and still walks a bounded tree.

The equal cut is not arbitrary after all #

The deferral above is stated as a deferral, and part of it can be closed with arithmetic rather than with a second measurement — the part that matters, because it decides whether the equal cut is a shortcut or the answer.

The reasoning that makes an unequal cut look attractive considers one search: a longer first piece is a stronger constraint, so lengthening it prunes harder. That is true and it is about the wrong object. A scheme runs $k+1$ searches, and lengthening one piece shortens another, so the quantity to minimise is the total over all of them.

Write it out. A first piece of length $\ell$ matched exactly over $\sigma$ symbols leaves about $n/\sigma^{\ell}$ surviving rows on a text of $n$ characters, and each of those roots a subtree. The scheme’s total root count is therefore $\sum_i n\sigma^{-\ell_i}$, with the lengths constrained to sum to $m$.

And $\sigma^{-\ell}$ is convex. A sum of a convex function over arguments with a fixed total is smallest when the arguments are equal — which is the opposite conclusion to the one-search reasoning, and it is not close.

The numbers say how not close. Fifteen characters over four symbols on four thousand characters of text: an equal cut of five, five and five leaves $4000/4^5 = 3.9$ rows per search and 11.7 across the three. A cut of six, five and four leaves 0.98, 3.9 and 15.6 — 20.5, three-quarters again as many roots, because the four-character piece selects one row in 256 and gives back far more than the six-character piece saves. Push it to seven, five and three and the total is 66.7, nearly six times the equal cut.

The asymmetry is the whole of it. Lengthening a piece divides its survivors by $\sigma$; shortening one multiplies them by $\sigma$. Multiplication and division of the same factor do not cancel when they are applied to numbers of different sizes, and the shortest piece is always the largest term in the sum.

So the equal cut is optimal for this term, and the term is the dominant one — the remaining walk’s size varies with $m - \ell_i$ far more gently than $\sigma^{-\ell_i}$ varies with $\ell_i$, since one is roughly linear in the remaining length and the other is exponential in the piece length. What is left of the deferral is a second-order correction that could shift the best cut by a character, in the direction of very slightly unequal pieces, and cannot reach the six-five-four that the one-search argument recommends.

That reverses the note above, and it is worth saying which of the two arguments was wrong rather than quietly replacing it. The one-search argument was right about its own object and applied to the wrong one, which is the same error as pricing a filter by its selectivity and forgetting that the q-grams an error cannot destroy has to search for every piece. The budget forces $k+1$ pieces; the pieces are searched; the cost is a sum, and a sum of a convex function has its minimum where nothing is short.

One consequence for the branches an error opens’s collapse at large budgets: it cannot be delayed by cutting cleverly. At three errors the equal cut gives pieces of four and is already the best available, so the fifteen candidate rows before branching are a floor rather than an artefact of a lazy partition.

The alphabet, and why the effect survives it #

A wider alphabet branches more per error, which makes the tree bigger, and empties intervals faster, which makes branches die sooner. Both effects are large and they pull in opposite directions.

Measured across three alphabets at two errors: the plain right-to-left search explores 625 extensions on two symbols, 772 on four, and 4,560 on twenty-six. The scheme explores 298, 266 and 904. So the branching wins on both, and the scheme’s advantage widens — from 2.1 to 5.0 — because the thing it removes is precisely the branching.

That is a more useful result than the headline factor, because it says where the technique earns its keep. On DNA — four symbols, which is where index-based approximate matching is most used — the factor is 2.9. On text it is 5.

What it costs, in the other currency #

The tree falls by 2.74 and each of its nodes costs more, because a bidirectional extension is 16.5 ranks on four symbols against a backward step’s two. An interval that grows at both ends is the essay about that, and the reason it is stated here as well is that a ratio quoted without it is a ratio in a currency nobody pays.

In ranks the scheme is 4,916 against 13,806 — still a factor of 2.8, because both sides here are bidirectional extensions and the σ term cancels. The comparison that would not cancel is against a unidirectional walk over a single index, which spends two ranks an extension and would come out ahead in ranks while exploring nearly three times the tree.

That comparison is not drawn, and the reason is that it compares two structures rather than two schedules. The operation that closes the gap — asking a wavelet tree for every child at once — exists, is what real implementations use, and is not built here.

The other end of the same idea #

It is worth noticing that the filter strand reached the same wall from the other side and stopped.

The filter that proposes everything measured a seed-and-extend filter collapsing as the seeds get short: at some budget the pieces are too short to be selective and the candidate count becomes the text. The response there was to make the seeds longer by allowing fewer of them, which needs a different partition.

A scheme is the same move made inside the index. Its first piece is a seed and its “verification” is the rest of the walk, and the reason it does better is that the walk is bounded by the index rather than by the text — a candidate that a filter would verify against m characters, a scheme rejects with one dead extension.

What is checked #

Every schedule finds exactly what exhaustive comparison finds — positions and error counts, at two budgets, on all four schedules. That is the check the whole strand rests on, and it is against comparing the pattern at every position rather than against another search, because two searches sharing a framework can share a mistake.

Every scheme covers every distribution of the errors. That is a finite condition and it is enumerated rather than argued; a schedule nobody writes down is the essay about what happens when it does not hold.

And a scheme with one search removed must lose occurrences. It does — seven of eight found — and it is worth knowing that the loss is small enough to look like nothing. Every position it reports is real, at the right error count, and the ones it misses are the ones whose errors fell the way the missing search covered.

What this does not do #

Two things, and both are worth stating because a factor of three invites over-reading.

It does not change what is found. Every schedule returns the same positions with the same error counts, and that is checked rather than assumed. A scheme is a way of not looking at branches that cannot hold an answer; it is not an approximation and it has no accuracy to trade.

And it does not touch the index’s size. The structure is two transforms whatever schedule runs over it, which is the finding the structure that was supposed to halve records. A reader who cannot afford the doubling cannot have any of this, and the plain walk over one index remains what they should build.

What it does change is the relationship between the budget and the cost. An unconstrained walk’s tree multiplies by about ten per error; a scheme’s multiplies by about six. That is still exponential, and at five errors both are hopeless — the honest reading is that a schedule buys one or two errors of headroom rather than a different growth.

What decides this, and what does not #

The schedule is worth a factor of between two and five, and nothing in the pseudocode of an index walk names it. That is the shape of finding this collection keeps recording — the queue decides the class, and the pseudocode does not name it is the earliest instance — and it is why the next essay is about the schedule itself rather than about what it buys.