The saving, spent

A saving is worth what it buys, and a saving in bits can be spent in bits.

The counting-only reverse half removes 16.7% of a bidirectional index at one sampled position in 32. Rather than banking that, give it back to the forward half — the one that does locate — as a denser sampling, and hold the total size fixed.

At one sampled position in 8 in the forward half and none in the reverse, the structure fits inside 98.5% of the symmetric one’s bits and answers a locate in 3.0 LF steps an occurrence against 15.0.

Five times faster, slightly smaller, same answers.

The arithmetic #

A locate walks backwards from a row until it reaches a sampled one, so its cost is about half the sampling gap. A sampling costs (n/s)⌈log₂ n⌉ bits for the positions plus n bits for the marks.

Removing the reverse half’s apparatus frees 11,791 bits at s = 32. Making the forward half four times denser costs 3 × 3,598 = 10,794 more bits for the positions, and nothing more for the marks, since the marks are n bits at any rate.

So the trade is 10,794 bits spent against 11,791 freed, and the locate cost falls from (32 − 1)/2 to (8 − 1)/2. That is the whole of it, and the only reason it works out so neatly is the floor from the last page: the marks do not have to be paid for twice.

What the plate says #

Three asymmetric structures, all fitting inside the symmetric one’s size:

At one in 32 — the same rate, just with the reverse half stripped — the structure is 83.3% of the size and locates at the same 15 steps. That is the saving banked.

At one in 16, it is 88.4% of the size and locates in 7.0 steps: 2.14 times faster, and still 12% smaller.

At one in 8, it is 98.5% of the size and locates in 3.0 steps: 5.0 times faster at essentially the same size.

At one in 4 it no longer fits — 113% — so the range of the trade is bounded, and the boundary is visible on the plate rather than argued about.

Why this is the point of the strand #

The 16.7% on its own is a modest number. Structures in this field are argued about in factors, not in sixths, and an index that is a sixth smaller is an index that is basically the same size.

What makes it worth a strand is that the sixth is asymmetric: it comes out of one half and can be spent on the other. A saving that had come out of both halves equally would buy a proportionally denser sampling in both, and the locate would improve by a sixth rather than by a factor of five.

The general shape is worth naming, because it applies past this structure: a resource freed from a component that cannot use it is worth more than the same resource freed evenly. The bits removed here were, by construction, bits in the half where they did nothing; the bits added are in the half where they do the most.

What it costs #

Nothing in the search, which is the property an index that cannot locate establishes: the same rows, the same nodes, the same extensions, because the reverse half was only ever asked for ranks.

Something in the construction, though not much: a denser sampling means keeping more positions, which is one array write per kept row at build time.

And a real cost in generality. The structure now has an asymmetry somebody has to remember. A future change that asks the reverse half to locate — a query wanting the occurrences of a reversed pattern in their own coordinates, or an extraction starting from a reverse row — finds a structure that cannot answer, and the failure is at the top of a call stack far from here.

That is the honest price, and it is why the counting half raises rather than returning something. A structure that cannot do a thing should say so at the moment it is asked, not at the moment its answer is used.

Why the locate cost is worth this much attention #

A locate is one operation among several, and it is the one that decides whether an index is usable for a query that returns many answers.

A count is one interval narrowing — a few ranks per character of the pattern — and it is fast whatever the sampling. A locate is that, plus a backward walk per occurrence, and the walk is where the time goes: at one in 32 a pattern occurring a thousand times costs fifteen thousand LF steps, each of them a rank on a wavelet tree, each of them several memory accesses. That is the operation that makes an index feel slow.

So an index that answers where frequently is an index whose sampling rate is its dominant performance decision, and this strand’s saving lands exactly there. It does not make counting faster — nothing about the reverse half’s contents affects counting — and it does not make the search explore fewer nodes. It makes the last step, the one proportional to the number of answers, several times cheaper.

Which is also why the trade is worth drawing rather than describing. Both quantities on this page are measured on the same structure with the same code: the bits come out of the size accounting each part reports, and the steps come out of a counter the walk increments. Neither is modelled, and the (s − 1)/2 prediction is drawn as a line to be checked against rather than as the answer.

Where the trade runs out #

Two ends, and both are visible on the plate.

Dense. At one in 4 the forward half’s positions cost 28,686 bits, and no saving from the reverse half covers that: the structure is 13% larger than the symmetric one. Past that the trade is simply buying a bigger index, which is a decision anybody can make without this page.

Sparse. Going the other way — sampling the forward half at one in 64 and banking more — the saving grows a little and the locate gets slower. There is no point on that side where the asymmetry buys anything the sampling rate could not buy on its own, because both halves are then mostly counting structure.

So the useful band is narrow and it is where indexes actually run: forward sampling between one in 8 and one in 32, which is where an index that both counts and locates sits.

What a system should do with this #

The recommendation is short.

Build the reverse half without its locating apparatus. It is never asked, the check that it is never asked already exists as an invariant on the intervals, and it is free.

Then set the forward sampling from the freed bits rather than from a default. The natural default is the same rate on both halves, and that leaves a factor of five on the table.

And measure the locate on the text in hand, because the (s − 1)/2 prediction holds here and is a statement about how the transform scatters positions. It held on four sampling rates over eight thousand characters of DNA; it is not a theorem.

The strand, in four numbers #

2.00 — what a bidirectional index costs against a single one. Not 1.5, not 1.8: exactly twice, because reversing a text changes none of the quantities an index’s size is made of.

16.7% — what the reverse half’s locating apparatus is, at one sampled position in 32.

Between 14% and 30% — what it is across the sampling rates anybody uses, which is the number that should be quoted when only one is.

5.0 — the factor by which a locate gets faster when the saving is spent rather than banked, at equal total size.

The first was measured when the structure was built. The second, third and fourth are what came of asking which half of it is ever asked what.

What is deferred #

The same trade with a compound extension. The searches on this page perform an interval extension per character per branch, and each of those costs a rank of every smaller symbol — which every child at once removes, at a factor of fourteen on a twenty-six-symbol alphabet. Both changes are to the same structure and they interact: one makes the search cheaper and the other makes the answers cheaper, and nothing here measures the two together.

A sparse representation of the marks. The floor under the saving is a bit vector with one bit in s set, stored plainly at n bits. Stored sparsely it would be far smaller, the floor would drop, and the whole shape of the saving curve would change — which would move every number on the previous page and this one.

And the second sampling. An index that extracts from an arbitrary position needs a position-indexed sampling as well, in the forward half. It is about the size of the row-indexed one, this collection has priced it and not built it, and adding it changes the budget this page spends.

Two thirds of the saving is the marks, and that decides the factor of five #

The budget this page spends is 11,790 bits, and it is worth opening because its two parts behave completely differently under the deferral named at the end of this page.

At one sampled position in 32 over eight thousand characters, the reverse half’s locating apparatus is 3,598 bits of positions and 8,192 bits of marks — one bit per row, whatever the rate. So 69% of the freed budget is the marks, and the marks are the part that does not shrink when the sampling is made sparser and does not grow when it is made denser.

That is what makes the trade work as neatly as it does. Spending to quadruple the forward density costs three more copies of the positions — 10,794 bits — and nothing more for marks, because the forward half’s marks were already n bits and stay n bits. The budget is dominated by a term the spending does not have to match.

It also says where the boundary is, exactly. The forward positions may grow to $3{,}598 + 11{,}790 = 15{,}388$ bits, which at thirteen bits a position is 1,184 sampled rows, which is one row in 6.9. So one in eight fits with room and one in four does not, and the plate’s two right-hand rows are the two sides of that division rather than two sampled points.

Now apply the deferral. A marks vector with one bit in $s$ set, stored sparsely, costs roughly $(n/s)(\log_2 s + 2)$ bits rather than $n$ — about 1,800 rather than 8,192 at this rate. The reverse half’s removable apparatus then falls from 11,790 bits to about 5,400, and the symmetric index it is a fraction of falls too, so the headline 16.7% becomes something nearer eight.

And the trade on this page loses most of its budget. Five thousand four hundred bits buys the forward positions up to about 9,000 bits, which is 691 rows, which is one in twelve — a locate of about 5.5 steps against the symmetric structure’s 15.

So the factor of five is a factor of about 2.7 once the marks are stored sparsely, and the whole of the difference is that the plain marks are a large, rate-independent block of bits sitting in the half that never uses them.

That is worth stating as the strand’s sharpest dependency rather than leaving in the deferral list, because it inverts how the two open items should be read. The sparse marks are described as a change that “would move every number”; the direction and the size are now known — the saving roughly halves and the spent-saving factor falls to under three. It is still a real trade and it is no longer a factor of five.

Which is a bit for every bit’s finding arriving in a place it decides an entire recommendation: the marking vector is the part of a sampling that nobody counts, it is larger than the thing it marks at any reasonable rate, and here it is two thirds of a saving whose headline it silently sets. A sixth of what, exactly is where the floor the marks put under the saving is measured; this is what that floor is worth once it is spent.

Where this sits in the strand #

Four pages, one structure, and they are best read in order.

The half that is never asked where establishes what the reverse index is used for — ranks, several hundred a search, and never a position — and why its rows could not be read as positions even if somebody wanted them.

An index that cannot locate builds the counting-only half and prices it: three parts kept, two dropped, 23,514 bits against 35,305.

A sixth of what, exactly sweeps the sampling rate, because 16.7% is a number about a dial at one setting, and finds the floor that the marks put under the saving.

This page spends it. And the reason the four are separate rather than one is that only the last is a recommendation: the first three are measurements, and a measurement that gets folded into a recommendation stops being checkable.

The same move, elsewhere in this collection #

Two other structures here have a redundant half, and it is worth asking the same question of both.

A document index’s chain of previous occurrences is a full array the walk never reads — the array the walk never reads — and the answer there is stronger than this one: the array is not merely unused by half the structure, it is unused entirely, and what replaces it is one bit per document.

A phrase index’s grid holds points twice, once by prefix rank and once by suffix rank, so that a query can enter from either side. Whether both orderings are ever exercised by a real query is exactly the question this page asked about the reverse index, and nothing in this collection has asked it.

The general form: wherever a structure is duplicated for symmetry, ask which of the duplicate’s abilities are exercised. Symmetry is usually a property of the construction rather than of the workload, and the parts that go unused are the parts a careful implementation deletes.

What a reader should take #

Three sentences.

A bidirectional index’s reverse half never locates, so the two parts of it that answer “where” can go: 16.7% of the structure at one sampled position in 32, between 14% and 30% across the dial.

The saving is asymmetric, so it is worth more than its size. Spent on the half that does locate, it makes a locate five times faster at 1.5% less total size than the symmetric structure.

And the invariant that makes it safe was already there. The forward interval is exact because both intervals are maintained in step, which is a property an earlier check already enforces — so nothing new has to be believed for this to be correct.

One more number worth writing down #

The strand’s four pages produce one figure that is not a size or an operation count, and it is the one worth carrying: the reverse half of a bidirectional index is asked for a position zero times per query.

Not rarely. Zero, over every search scheme, every error budget, every alphabet measured — because the occurrences a search reports come out of the forward interval, and the reverse half’s rows are coordinates in a text nobody has.

A component that is asked for something zero times is a component whose machinery for that something is removable, and the only work in this strand was noticing the zero and then being careful about what removing it costs. That care is the three pages before this one: the invariant that makes the forward interval exact, the parts split into what answers how many and what answers where, and the dial that decides how big the second group is.

The one measurement that would change the recommendation #

If one thing on this page is worth re-measuring on a real system, it is the assumption that a locate’s cost is what a query’s cost is dominated by.

Every number here counts LF steps, and an LF step is a rank on a wavelet tree plus an access — several memory operations, scattered. A search’s extensions are also ranks, and every child at once removes a factor of σ from them. Which of the two dominates a query depends entirely on the ratio between the extensions performed and the occurrences returned.

For a pattern occurring a handful of times, the search dominates and the compound operation is the thing to build. For a pattern occurring thousands of times, the locate dominates and this page’s trade is the thing to build. Both are on the same structure, both were measured separately here, and the combination is what a real workload pays.

That is the honest limit of a strand that measures one axis at a time, and it is the deferral this page ends on rather than a hedge: a factor of fourteen, for four per cent is the other axis, and nothing here has drawn them on one plate.