Bits and steps on one frame

A self-index’s sampling rate is one number and it moves two things in opposite directions.

Sample densely and the index is large and a locate is fast. Sample sparsely and the index is small and a locate walks.

Every result in this strand is a function of that dial, so the strand’s last plate is both quantities against it.

The two lines #

Size, as a share of the plain bidirectional index at the same rate: 99.5% at one in four, falling to 86.3% at one in a hundred and twenty-eight.

Steps to a sampled position, per occurrence: 2.5 at one in four, rising to 63.6 at one in a hundred and twenty-eight.

The size falls by 13 percentage points and the walk lengthens by a factor of twenty-five.

Why the size line is nearly flat #

The share is nearly flat because it is a share of a structure that is also shrinking. Both indexes get smaller as the sampling thins; the improved one gets smaller faster.

In absolute terms the improved index goes from 157,696 bits at one in four to 80,743 at one in a hundred and twenty-eight — a factor of two.

So the plate is showing a relative saving that grows from a half per cent to fourteen, on top of an absolute size that halves. Two different things falling, and the line drawn is the ratio.

That choice is worth defending because the alternative is misleading. A plate of absolute sizes against the sampling rate would show two lines converging steeply and would say nothing about what the improvements are worth — the dominant effect would be the sampling, which is a parameter rather than a result.

Why the step line is exactly what it is #

A locate walks a row backwards by LF steps until it reaches a sampled one. The samples are at every s-th text position, so the expected walk is s/2 and the worst is s − 1.

Measured: 2.5 at s = 4, 63.6 at s = 128. Both are close to s/2 and slightly above it, because the measurement averages over occurrences rather than over rows and the occurrences of a pattern are not uniformly distributed in the text.

That the line follows s/2 is a confirmation rather than a finding, and it is worth confirming: a walk that did not follow the sampling gap would mean the sampling is not doing what its account says.

Every occurrence at the same price is where this collection established the per-occurrence cost of a locate, and this is the same measurement inside a different structure.

The alphabet flattens the size line without touching the step line, which is worth a sentence because it says which of the two quantities is about the data.

The steps depend on the sampling gap and on nothing else: s/2, on any text over any alphabet. A locate’s walk is a property of the sampling policy.

The size share depends on how large the locating apparatus is relative to the rest, and the rest is dominated by the wavelet tree, which grows with the alphabet’s entropy. So on a larger alphabet the same apparatus is a smaller share and the improvements are worth less proportionally.

On DNA the reverse holds sharply: a four-symbol wavelet tree is small, the locating apparatus is most of the index, and this plate’s size line would fall much further across the same dial.

The convention #

This collection’s habit is stated once and applied here: both currencies on one frame, when a change trades. Two plates several pages apart is how a trade gets reported as a win.

The habit came out of the half-index strand, where a saving of bits could be spent on a denser sampling and the two facts were in different essays — so a reader could take away “the structure is a sixth smaller” without the accompanying “or the same size and five times faster”, which is the more useful sentence.

Applying it here has a small cost worth noting. The two quantities are in different units and on different scales, so one of them needs a second axis, and a second axis is a thing that can be misread. The alternative — normalising both to a share of something — makes the step count a share of a maximum nobody chose.

Two axes it is, with the size axis on the left as a percentage and the steps drawn against their own maximum on the right.

There is a third quantity that could have been on the frame and is not, and leaving it off was a decision rather than an oversight: the number of occurrences a query returns.

A locate’s total cost is steps-per-occurrence times occurrences, and the second is a property of the query and the text rather than of the structure. Putting it on the frame would mean choosing a query profile, and the plate would then be about that profile.

So the frame is per-occurrence throughout, and a reader with a workload multiplies. That is the same division every occurrence at the same price settled on, and its reason holds here: a per-unit cost is a property of a structure and a total is a property of a use.

What a system chooses #

The plate is a menu and the entries are worth naming, because the dial’s ends are both real configurations.

One in four. Index 157,696 bits, locate 2.5 steps. A read aligner reporting thousands of occurrences per query lives here: the locating cost dominates its runtime and the index fits in memory either way.

One in thirty-two. 89,150 bits, 16 steps. The rate every published size in this collection is quoted at, and a reasonable default.

One in a hundred and twenty-eight. 80,743 bits, 63.6 steps. A structure indexing more text than fits comfortably, where a locate costing a few hundred bit-vector operations is acceptable because most queries are counts.

Between one in thirty-two and one in a hundred and twenty-eight the index falls by nine per cent and the locate lengthens by four times. That is a poor exchange rate and it is the reason the sparse end is less attractive than a size-only plate suggests.

The exchange rate #

Since the fourth rung of the size ladder spends a saving on the sampling, the rate at which bits convert to steps is worth extracting.

Between one in thirty-two and one in eight: the index grows by 30,541 bits and a locate falls from 16 steps to 4. So 12 steps an occurrence cost about 30,000 bits, or 2,500 bits a step.

Between one in a hundred and twenty-eight and one in thirty-two: 8,407 bits for 48 steps, or 175 bits a step.

The rate is fourteen times better at the sparse end, which is the general shape of a hyperbola: the same proportional change in s costs the same proportional change in the samples’ size and the same proportional change in the walk, so the absolute exchange rate improves as s grows.

That says something useful about where to spend a saving. Bits spent moving from one in a hundred and twenty-eight to one in thirty-two buy fourteen times more speed than the same bits spent moving from one in thirty-two to one in eight.

Where the sparse marks change the trade #

The plate’s size line is for the improved structure, and it is worth asking what the trade looks like without the improvements — because the improvements change the shape of the trade and not only its level.

With plain marks, the locating apparatus’s share of an index falls from 49% to 18.5% and flattens. So a system turning the sampling dial to save space finds the saving petering out, and stops.

With Elias–Fano marks it falls to 3.8% and keeps falling. The dial keeps paying.

That means the improved structure has a longer usable range on the dial, not merely a smaller size at each point. A system that had settled at one in thirty-two because sparser sampling stopped helping now has a reason to go further — and the reason is that the thing which had stopped it was a badly represented array.

The floor was the marks is where the flattening is diagnosed and what the locating apparatus becomes is where both curves are drawn. What this frame adds is the other currency: going further on the dial costs steps, and the steps were always there — what changed is that the bits now keep falling to pay for them.

What the operation savings do to this plate #

Nothing, and that is the point of drawing them elsewhere.

The compound walk and the interval enumeration change what a search costs. Neither touches the marks or the sampled positions, so neither moves either line on this plate — checked as an equality: 12,486 ranks whether the marks are plain or sparse.

So the strand has two independent trades. This one, between bits and locate steps, parameterised by the sampling rate. And the operation savings, which are free in bits and split by the query’s shape rather than trading against anything.

Three savings on one structure is where that independence is established and two factors that do not multiply is where the two operation savings turn out to be one.

The trade in one sentence, twice #

Two summaries of this frame, one for each direction a reader might come from.

Coming from size: an index sampling one position in a hundred and twenty-eight is half the size of one sampling one in four, and its locates cost twenty-five times as many steps. The improvements in this strand take a further fourteen per cent off the sparse end and half a per cent off the dense end, so they widen the range rather than shifting it.

Coming from speed: a locate costs about s/2 LF steps whatever else is done to the structure, and the only way to make it faster is to sample more densely, which costs bits at 175 to 2,500 bits a step depending on where on the dial the change is made. The improvements in this strand supply about 39,650 bits at one in thirty-two, which is enough to quadruple the sampling.

Those are the same plate read twice and neither summary follows from the other. A reader with a size budget and a reader with a latency budget are choosing different points and want the curve read in opposite directions, which is the argument for drawing it rather than quoting either end.

What a one-currency plate would have said #

It is worth writing out the essay this plate prevents.

The improvements to a bidirectional index are worth 15.8% of its size at one sampled position in thirty-two, and the saving grows as the sampling thins — reaching 18.4% at one in a hundred and twenty-eight.

Every number correct, and the implication — that the sparse end is better — is what a reader takes away.

The sparse end has a locate costing sixty-four LF steps an occurrence, which on a query returning ten thousand occurrences is several million bit-vector operations. Whether that is acceptable is the whole decision and it is absent from the sentence.

The rule this collection follows is not “report the other currency somewhere”. It is that a plate about a change that trades draws both, because the two facts are only useful together and prose linking two plates is how a reader ends up with one of them.

Three plates, three axes, one structure #

The strand ends with three plates and it is worth saying what each is for, because between them they are the whole of what has been measured and none is a summary of the others.

The size ladder is a bar chart of cumulative changes at one sampling rate. It says what each change is worth and it holds the dial fixed.

This frame is two curves against the dial. It says what the dial does and holds the changes fixed.

The branching plate is three machines on one search. It says what the operation savings are worth and it holds everything else fixed.

Three plates, three axes, and every one of them holds two of the three things fixed. That is the discipline this collection settles on wherever a result has more than one parameter: sweep one, hold the rest, and draw as many plates as there are parameters.

The alternative — one plate with everything on it — is a plate a reader cannot read, and the alternative to that is a single number, which is a number about one configuration.

There is a fourth axis and a fourth plate, which is the budget sweep. So the strand’s parameter space is four-dimensional — sampling rate, alphabet, error budget, and which savings are applied — and four plates cut it four ways.

Whether that is enough is a fair question and the answer is that it covers the axes a system chooses. The alphabet is given by the data; the other three are decisions, and each has a plate.

Why the second axis is drawn against its own maximum #

A small drawing decision is worth recording because it is the kind of thing that quietly makes a plate say the wrong thing.

The two quantities are a percentage and a step count, so the second needs its own scale. Scaling it against its own maximum — sixty-four steps at the sparsest point — puts the two curves in the same visual range and makes their opposition legible.

It also means the step curve’s height carries no absolute information: a reader cannot read a step count off it without the axis label. That is a real loss and the alternative is worse — a shared axis would put a 63.6 against a 99.5 and make the size curve look flat, which it nearly is and not that flat.

The convention this settles for future plates of this kind: two currencies, two scales, and the second normalised to its own range with its endpoint labelled. The endpoints are where the numbers are, and the shape between them is what the plate is for.

What is still missing from the frame #

Two quantities that belong on a complete picture and are not here.

Construction time, which grows as the sampling densifies — more samples to compute and store — and which nothing in this strand measures.

The search’s cost, which is on a different plate for the good reason that it is independent of this dial. A reader wanting a total query cost needs to add a search and a locate, and the two are functions of different parameters.

That second is worth stating as a limitation rather than as a virtue. A query is a search followed by a locate, and the two are drawn separately because they depend on different things — so the composition is arithmetic a reader has to do, and this collection does not do it for any specific workload.

What can be said in general: as the error budget rises, the search’s cost multiplies faster than the occurrence count does, so the search dominates at loose budgets; and as the sampling thins, the locate’s cost per occurrence rises linearly, so the locate dominates on queries with many occurrences. Where the two cross is a property of the workload.

The search that spends a budget is where the first half of that was measured and the branches that find nothing is where the enumeration’s effect on it was, and neither is on this frame because neither depends on the sampling rate. A complete query-cost model would compose four measurements from four plates, and this collection has the four and has not composed them for any named workload — which is honest and is a gap.

The reason it is a gap rather than a decision is that composing them requires a workload, and a workload is a corpus and a query distribution. A corpus that was not generated is where this collection stopped trusting a made-up one, and a made-up query distribution would be the same failure on the other side of the interface.