The saving that is a loss

The interval enumeration is the largest operation saving in this strand: 78× on a backtracking search over a twenty-symbol alphabet at one error.

On an exact search it costs 1.90 times what it replaces.

The measurement #

Sixteen exact patterns of twelve characters, over eight thousand characters of a twenty-symbol alphabet.

A loop over the alphabet: 107.9 ranks a step. It asks about every symbol and uses one.

The compound walk: 10.0 ranks a step. One root-to-leaf descent for the named symbol, returning its rank and its smaller-count.

The enumeration: 19.0 ranks a step. It descends the subtree containing every present symbol, collects each one’s interval, and the search picks out the one it wanted.

So the enumeration is 5.7× better than the loop and 1.90× worse than the walk.

Why #

The two operations answer different questions and an exact search only asks one of them.

The walk answers “where does symbol c go?” — one path, 2⌈log₂ σ⌉ ranks, which at σ = 20 is ten.

The enumeration answers “which symbols are here, and where does each go?” — one subtree, 2d(1 + log₂(σ/d)) ranks for d symbols present.

At d = 1 those are the same descent. At d = 20 the enumeration costs about twice, and returns twenty times as much.

An exact search wants one answer per step. Getting nineteen more is not free, and the enumeration’s cost is the price of the nineteen nobody asked for.

There is a second way to see the same thing that makes the magnitude predictable rather than measured.

The enumeration’s cost at d = σ is 2(2σ − 1) ranks, or about 4σ. The walk’s is 2⌈log₂ σ⌉. At σ = 20 those are 78 and 10, a ratio of 7.8 — which is nowhere near the measured 1.90.

The measured figure is smaller because an exact search does not sit at d = σ. Its intervals narrow as the pattern is consumed, so the number of symbols present falls: at the root all twenty, and six characters in perhaps three or four. Averaged over the twelve steps of a twelve-character pattern, the enumeration’s cost is 19.0 rather than 78.

So the loss is worst at the start of an exact search and nearly nothing at its end, which is the opposite of where a backtracking search’s saving is worst. Both are consequences of intervals narrowing, read in opposite directions.

The crossing is not on a dial #

It would be convenient if the two operations crossed somewhere on a parameter a system could tune, and they do not.

The relevant quantity is how many symbols the search wants at this node. An exact search wants one, always, at every node. A backtracking search wants all of them, at every node.

There is nothing between. A search either has a specific next character or it does not, and the answer is a property of the query rather than a setting.

So the “crossing” is a switch, and the switch is on something known before the search starts.

That is a comfortable place for a decision to be. This collection has several thresholds that need measuring against data — a filter’s selectivity, a cache’s size, a sampling rate — and this one is decided by the query’s own shape.

The loss grows with the alphabet, which is the direction that makes the branch worth having rather than optional. On four symbols the enumeration on an exact search costs about 1.3 times the walk; on twenty-six it is over two.

The reason is that an exact search’s early intervals hold more symbols on a larger alphabet, so the enumeration returns more that nobody asked for. The walk’s cost rises only logarithmically.

So on the alphabets where the enumeration is most valuable for branching searches, it is also most wasteful for exact ones, and a system on a large alphabet has the most to gain from choosing per node.

What a real search does with both #

The consequence is that an index should support both operations and choose per node, which is more machinery than choosing one and is what the numbers say.

The index this strand builds has both: extendLeft for a named symbol, using the compound walk, and branchLeft for every present symbol, using the enumeration. They share every array — the same wavelet tree, the same C table, the same directories — so having both costs nothing in bits.

A search calls whichever suits its node. An exact backward search calls the first m times. A backtracking search calls the second at every node. A partitioned search — the pigeonhole schemes, where a pattern is cut into pieces and each piece is searched exactly — calls the first inside its pieces and the second only if it verifies approximately.

That third case is the interesting one because it is what a real aligner does, and it means a production search spends most of its time in the regime where the enumeration is a loss.

What a loop was doing there in the first place #

Both the walk and the enumeration are replacements for a loop over the alphabet, and it is worth asking why the loop was ever the shape, because the answer explains why two replacements exist.

A bidirectional extension needs two things: the interval for the new symbol, and the count of symbols sorting before it. The second is where the loop came from — the published formulation computes it by iterating over the alphabet below the symbol and summing interval widths, which is σ ranks in the worst case.

So the loop is not a way of finding which symbols are present; it is a way of computing a sum. That the same loop also discovers absence is incidental.

The compound walk replaces the sum with an arithmetic identity along one descent. The enumeration replaces the whole loop with a subtree walk that produces the sum as a running total.

Two replacements for one loop, aimed at two different things the loop was doing, which is exactly the condition under which one subsumes the other. Two factors that do not multiply is the arithmetic of that, and this essay is the boundary of when each is the right replacement.

What the numbers are worth in each regime #

Putting the two side by side, because the asymmetry in magnitude matters as much as the sign.

On a branching search, the enumeration is 78× better than the loop and 7.1× better than the walk. Large.

On an exact search, the walk is 10.8× better than the loop and 1.90× better than the enumeration. The first factor is large and the second is small.

So the cost of choosing wrongly is asymmetric: using the walk on a branching search costs a factor of seven, and using the enumeration on an exact search costs a factor of two.

A system forced to pick one should pick the enumeration, and would give up a factor of two on the queries it probably runs most.

A system that can pick per node gives up nothing, and the machinery for it is two methods rather than one.

The asymmetry has a second consequence for how the two should be described. A factor of seventy-eight quoted for the enumeration invites reading it as strictly better, and the correction — that it is 1.90 times worse in the other regime — is small enough to be dismissed as a detail. It is not a detail; it is the whole reason the walk stays in the index.

It is worth being explicit that having both operations costs no bits, because that is what makes the branch free rather than a trade.

Both are methods on one wavelet tree. The walk descends one path; the enumeration descends a subtree. Neither adds an array, a directory or a table, and an index supporting rank supports both.

So the machinery cost of the branch is a conditional in the search’s inner loop and two methods where there was one. That is the whole of it, and it buys a factor of two on exact queries and seven on branching ones against picking either alone.

Why the loss is only two rather than twenty #

The enumeration returns twenty times as much information and costs twice as much, which is worth explaining because it is the reason the loss is bearable.

A descent visiting d leaves enters d(1 + log₂(σ/d)) nodes, and the ancestors of many leaves overlap near the root. At d = σ that is 2σ − 1 nodes for σ leaves — under two nodes a leaf.

A rank walk for one symbol enters log₂ σ nodes for one leaf — five nodes a leaf at σ = 20.

So the enumeration is more efficient per symbol by a factor of two and a half, and it is less efficient overall because it produces twenty symbols when one was wanted.

That is the general shape of a batch operation. It is cheaper per unit and more expensive in total when the batch is larger than the need, and the crossing is at a batch size of one — which is exactly where an exact search sits.

The check that stops the headline travelling #

This strand’s rejection test for the enumeration is not about a wrong answer; it is about a claim, and it is worth describing because a check on a claim is an unusual object.

The test runs an exact search on both machines and requires the enumeration to cost more. If it did not, the boundary this essay is about would not exist and the headline factor could be quoted without a condition.

A test that requires a structure to be worse reads backwards, and it is the right shape: what is being asserted is that a boundary exists where the argument says, and a claim about a boundary needs a point on each side.

The same shape appears three times in this slate — a sparse representation required to lose when dense, a compressed array required to save nothing on an even collection, and this — and each time the check is on the unfavourable case. That is the half a measurement made by somebody hoping for a result will not make.

Where the sparse representation loses is the clearest of the three, and its argument applies unchanged: a check that only ever runs on inputs where the claim holds has been fitted by its inputs, and an exact inequality with no tolerance in it can still be a check that cannot fail.

What this does to the strand’s headline #

The strand’s largest number is 78×, and this essay is the boundary of the claim.

Stated fully: on a search that branches, over an alphabet of twenty symbols, at one error, the enumeration costs a seventy-eighth of a loop over the alphabet. Change any of the three conditions and the number moves; remove the first and the sign changes.

Two at binary, five at twenty-six moves the alphabet: on DNA the branching factor is 2.8 rather than 78.

A looser budget wastes a larger share moves the budget: 5.8 at no errors on protein, 9.2 at two.

And this moves the query shape, which is the condition that flips the sign rather than scaling the number.

Three conditions, three essays, and the one that flips the sign is the one a reader is least likely to check — because “does this search branch?” sounds like a question about implementation rather than about applicability.

What a partitioned search actually spends #

The claim that a production search spends most of its time in the exact regime deserves numbers rather than an assertion, and this collection has the pieces even though it has not put them together.

A pigeonhole scheme cuts a pattern of m characters into k + 1 pieces, observes that one piece must match exactly if there are at most k errors, searches each piece exactly, and verifies the candidates. The q-grams an error cannot destroy is the filtering argument and the search that starts in the middle is the version that runs inside a bidirectional index.

The exact searches are k + 1 searches of m/(k+1) characters each — so m steps in total, every one of them a named-symbol extension.

The verification is either a direct comparison against the text, which uses no index operations at all, or a bounded approximate search around each candidate, which branches.

So the split between the two regimes is the split between filtering and verification, and which dominates is the filter that feeds the table’s subject: a filter proposing many candidates spends its time verifying and one proposing few spends it filtering.

That is a measurement this strand does not make and it is the one that would say what an aligner’s mix of the two operations actually is. What can be said without it is that both regimes occur in every query, which is the argument for the branch.

Three regimes, one index #

Collecting what the index built here does, because the answer is a small table rather than a rule.

An exact backward search. m named-symbol extensions, using the compound walk. Ten ranks a step at σ = 20. The enumeration would cost nineteen.

A backtracking search. Every node branches, using the enumeration. Eighteen thousand nine hundred ranks for twelve eight-character patterns at one error. The walk inside a loop would cost a hundred and thirty-four thousand.

A locate. Neither operation. s/2 LF steps, each a rank and an access on the wavelet tree, plus a mark lookup — which is where a position split in two’s representation is read and where the strand’s third saving lives.

Three phases of a query, three different parts of the structure exercised, and the two operation savings apply to one phase each while the size saving applies to the third.

That is the tidiest statement of what three savings on one structure found: not three improvements to one thing, but three improvements to three phases, two of which had been described as improvements to the same one.

The general shape #

A saving that is a loss in a neighbouring regime is a common enough object to be worth a name, and the useful question about one is where the boundary is.

Here the boundary is sharp and known in advance: one symbol wanted or all of them. That is the best case.

The uncomfortable case is a boundary that is neither sharp nor known — a saving that helps on data of one shape and hurts on another, where the shape has to be measured and can change. This collection has several: a filter’s threshold, a cache’s working set, a sampling rate.

The distinction is worth drawing because it decides whether an adaptive implementation is needed. A boundary known from the query is a branch; one known from the data is a measurement; one that moves is a controller.

This is a branch, which is why the answer is to have both operations and call the right one.

There is one further property that makes it the best kind of branch, and it is worth naming because it is not automatic even for a query-determined decision. The branch is on a static property of the call site rather than on a run-time value: an exact search’s code always wants one symbol and a backtracking search’s always wants all of them, so the choice is made when the search is written rather than when it runs.

That means there is no predicate to evaluate, no misprediction, and no code path that has to handle both. Two searches, two methods, and neither ever calls the other’s.

A decision that can be moved from run time to write time is worth moving, and the way to find such decisions is the question this essay asks: not “which is faster” but “what does the caller know”. An exact search knows its character; a backtracking search knows it does not have one; and the operation each should use follows from what each knows rather than from either’s cost.