The ladder, and the rung that spends

A bidirectional index over sixteen thousand characters of a twenty-symbol alphabet, sampling one position in thirty-two, with three changes applied one at a time.

Both halves locate. 250,584 bits. The published structure.

The reverse half counts only. 226,504 — 90.4%. Its marks and sampled positions are gone, because a bidirectional search reads occurrences out of the forward interval and never asks the reverse half for a position.

And its marks are Elias–Fano. 210,934 — 84.2%. The forward half’s mark vector, which holds five hundred and thirteen ones in sixteen thousand rows, stops being stored as sixteen thousand bits.

The saving spent on sampling. 241,475 — 96.4%, with a locate about four times faster.

The two savings, and their sizes relative to each other #

The first step removes 24,080 bits and the second removes 15,570.

That ratio is the reason this ladder is drawn in this order and is worth stating plainly: the second step is worth nearly two thirds of the first, on a structure where the first was the headline of an entire strand.

The half that is never asked where reported the first as a saving of about a sixth of both halves, and the flattening of its curve was the marks. The floor was the marks is the retraction, and this ladder is the same arithmetic laid out as a sequence rather than as a correction.

The ordering also matters to the attribution. Applied the other way round — marks first, then the drop — the first step would be worth more and the second less, because what is being dropped would already be smaller. Same total, different credits, which is a general property of cumulative savings on overlapping parts.

It is worth opening the two halves once, because the ladder’s first step is asymmetric in a way the totals hide.

A full half at one in thirty-two holds: a wavelet tree payload of 66,724 bits, rank directories of 13,626, marks of 16,385, sampled positions of 7,695, and a C table of 290. That is 104,720, and two of them plus rounding is the 250,584 the ladder starts at — the reverse half being over a reversed text of the same length with the same alphabet, so the same size to within the transform’s own variation.

The first rung removes the reverse half’s marks and sampled positions: 16,385 + 7,695 = 24,080. Exactly the measured step.

The second rung replaces the forward half’s marks: 19,475 bits of vector-with-directory becoming 3,905. That is 15,570, and again exactly the measured step.

So the two rungs act on different halves and different arrays, which is why they compose without interaction. The ladder’s cumulative arithmetic is a sum rather than a composition, and the only reason the order matters is the attribution.

The rung that is not a saving #

The fourth step is a different kind of thing and it is the reason the ladder has four rungs rather than three.

Take the 39,650 bits saved by the first three steps, and spend them: sample the surviving locating half at one position in eight rather than one in thirty-two.

The index is then 241,475 bits — 96.4% of where it started, so a 3.6% net saving rather than a 15.8% one.

And a locate walks four rows on average rather than sixteen.

That is the trade the saving, spent measured for a different pair, and its argument applies: bits saved and banked are worth their size, and bits saved and spent on the sampling are worth a factor in locate speed. Which is better depends on whether the structure is size-bound or latency-bound, and it is a choice rather than an improvement.

Why the fourth rung is drawn on the same plate #

A saving reported alone and a trade reported elsewhere is how a trade gets reported as a win, and this collection has a convention against it: both currencies on one plate, when a change trades.

Here the plate is bits and the fourth rung’s other currency is in the caption. That is the weaker form of the convention and it is what a bar chart of sizes can do; bits and steps on one frame is the stronger form, where both axes are drawn.

The reason to draw the fourth rung at all is that it is the configuration a real system would choose. A structure that has become 84% of its former size by removing an array and re-encoding another has an option nobody had before: it can go back to its original size and be substantially faster, which is not what a report of “smaller” suggests.

The alphabet changes the shares without changing the steps, which is worth noticing because it means the ladder’s absolute numbers travel and its percentages do not.

The marks and the sampled positions depend on n and s and not on σ at all — a mark is one bit per row whatever the alphabet, and a sampled position is ⌈log₂ n⌉ bits.

The wavelet tree depends on σ through the entropy: a twenty-six letter alphabet gives a deeper tree and a larger payload.

So on a larger alphabet the same two rungs remove the same bits from a bigger structure, and their percentages fall. On DNA they would rise sharply, because a four-symbol wavelet tree is small and the locating apparatus is most of the index.

That is the direction that matters for the field’s main workload: on DNA at one in thirty-two the locating apparatus is well over half the structure, and everything on this ladder is worth more than the percentages here suggest.

What the sampling rate does to every rung #

The whole ladder is at one position in thirty-two and every rung moves with that dial.

At one in four: the drop is worth 12.3% and the mark representation 0.5%, because at that density the sampled positions dominate and Elias–Fano barely beats a plain vector.

At one in thirty-two: 9.6% and 6.9%.

At one in a hundred and twenty-eight: 7.4% and 9.2% — the mark representation is now the larger of the two.

So the ordering of the first two steps inverts across the dial, and a system quoting “the drop is the larger saving” is quoting a fact about dense sampling.

What the fourth rung buys at each rate #

The exchange rate between bits and locate steps is not constant either, and it improves as the sampling thins.

At one in a hundred and twenty-eight the first three steps save more bits and a locate costs sixty-four steps, so spending the saving on a four-times denser sampling takes it to sixteen — a saving of forty-eight steps an occurrence.

At one in four a locate costs two steps and there is nowhere to go: sampling at one in one is a suffix array with extra machinery.

So the fourth rung is worth most exactly where the first three are, which is the sparse end. That is a pleasant compounding and it is not automatic — a trade whose value fell as its inputs grew would be a trade nobody should make.

None of the four rungs changes what a search costs, and it is worth saying so explicitly because a reader who has followed the strand’s operation savings might expect a size ladder to interact with them.

It does not. A search reads the wavelet tree and the C table; it never touches the marks or the sampled positions, which are read only when an interval is turned into text positions. Measured as an equality rather than an approximation: 12,486 ranks whether the marks are plain or sparse.

So the strand has two independent ladders — one in bits and one in operations — and every rung of each is orthogonal to every rung of the other. That is the cleanest possible composition and it is a consequence of the structure’s parts being read by different phases of a query rather than of anybody designing for it.

The reverse half’s guarantee #

The first rung is described as free and that deserves scrutiny, because a structure that has lost the ability to do something is not obviously free.

What the reverse half loses is locate, and the argument that it never needs it is a claim about the invariant a bidirectional search maintains: the two intervals describe the same set of occurrences, one in the text and one in its reverse, and the forward interval is the one whose rows correspond to text positions in the ordinary way.

That invariant is what an interval that grows at both ends established and what the structure that was supposed to halve had to check when the two halves could drift. So the freeness of the first rung rests on a property two earlier essays had to work for.

The check that makes it safe is not a size check. It is that the stripped half raises when asked to locate, so a search that had come to depend on it fails rather than returning something. An object holding the arrays and promising not to read them would have the same size as one that uses them, and this collection has had to guard against that shape three times in this slate alone.

An index that cannot locate is the structure, and its inability is the evidence for the ladder’s first step being what it says.

The four rungs as four decisions #

Stated as things a system chooses rather than as a sequence.

Does the reverse half ever need to locate? In a bidirectional index, no — its rows are positions in a reversed text and the occurrences come out of the forward interval. So the first rung is free and should always be taken.

Are the marks sparse? At one in eight or sparser, yes, and Elias–Fano is between two and fifteen times smaller. At one in four, no. Where the sparse representation loses is the crossing.

Is the structure size-bound or latency-bound? Bank the saving or spend it.

And what sampling rate? Which is the parameter all three of the above depend on, and which is chosen against a workload rather than derived.

Four decisions, of which one is unconditional, one has a crossing, one is a preference and one is the dial the other three are functions of.

What the ladder does not include #

Two changes that would appear on a longer ladder and are not on this one.

A compressed representation of the wavelet tree’s levels. That is the largest part of the structure — 66,724 of 104,720 bits per half — and block-classed vectors reach the text’s higher-order entropy rather than its zeroth. It is a change to a different part and it composes with everything here.

A run-boundary sampling. A function with r pieces is the structure: 2r suffix-array values and no marks at all, which removes the entire object this ladder’s second and third rungs are about. On a repetitive collection that is a larger change than anything here and on ordinary text it is larger than the structure it replaces.

Both are named because a ladder reads as exhaustive and this one is three changes to two arrays out of five parts.

What “spend it” means as an implementation #

The fourth rung is described as spending a saving and it is worth saying what that is concretely, because “spend” makes it sound like a transfer between accounts.

It is a parameter change. The index is built with sample = 8 rather than sample = 32, and everything else is the same code. The sampled positions quadruple — 7,695 bits becoming 30,735 — and the marks, being Elias–Fano, grow too but far less: 3,905 becoming 10,244, because a denser set has a smaller low width and a longer high vector.

That the marks grow sublinearly in the density is what makes the fourth rung affordable. With plain marks the same change would leave them at 16,385 either way, so a system quadrupling its sampling would pay the full quadrupling on the positions and nothing on the marks — which sounds better and is a consequence of the marks already being too large.

With sparse marks the marks are 2.6 times larger at four times the density, so the total cost of the change is 23,040 + 6,339 = 29,379 bits, against the 39,650 saved. The saving covers it with room.

So the fourth rung is not a full spend — it is a four-times denser sampling for three quarters of the saving, leaving a quarter banked. A system wanting to spend the rest could go to one in six.

Where the ladder would go next #

Two rungs are available and neither is built, and it is worth pricing them roughly so the ladder’s remaining slack is visible.

Compressed levels. The wavelet tree’s payload is 66,724 bits a half, and block-classed vectors reach the text’s higher-order entropy rather than its zeroth. On English-like text that is perhaps a fifth off the payload, or 13,000 bits a half — comparable to the first rung and applying to both halves, so 26,000 in total.

That would be the largest single rung on the ladder, and it costs several times the work per rank on every operation the index performs. Rank is the only thing it does is where the representation was priced here.

Compressed sampled positions. After the marks, the positions are the largest part of the locating apparatus: 7,695 bits at one in thirty-two, and 30,735 at one in eight. They are arbitrary numbers in a fixed range and nothing here compresses them.

The published approach stores differences along the phi function rather than absolute values, which turns them into a sequence with structure. That is what an r-index does and it comes with a different sampling policy attached — 2r values at run boundaries and no marks at all.

So the remaining slack is one large rung on the payload and one on a part the whole ladder is about, and taking the second would remove the ladder’s second and third rungs rather than adding to them.

What a reader should take #

The numbers first. Dropping a counting half’s locating apparatus: 9.6%. Representing the survivor’s marks sparsely: 6.9%. Together: 15.8%. Spent on sampling instead: 3.6% and a four-times faster locate. All at one position in thirty-two, all on a bidirectional index, all moving by a factor of several across the sampling dial.

And the shape. A ladder of cumulative savings has an ordering, the ordering decides the attribution, and only the total is order-independent. Reading a rung as “this change is worth x” is reading a number that depends on what was applied before it — which is fine when the ladder is presented as a sequence and misleading when a single rung is quoted alone.

That is the practical reason to draw all four together rather than to write four essays each reporting one. The first three rungs are three results and the fourth is what a reader would do with them, and the fourth is the one that changes what the first three mean.

There is a last thing worth saying about a ladder as a form. It presents a sequence of changes as though somebody would apply them in that order, and nobody does — a structure is built once with all of them or none. What the sequence is actually for is attribution: it says how much of the total each change is responsible for, given an order, and the order has to be stated because the answer depends on it.

A better form for the same information would be a lattice: every subset of the three changes, priced. That is eight numbers rather than four and it is order-free, and it is not drawn here because eight bars are harder to read than four and the three changes here happen to act on disjoint arrays — so the lattice would be a sum and the ladder loses nothing.

The one case where a ladder is genuinely misleading is when its rungs overlap, and this one’s do not. Saying so is what makes the four numbers usable rather than a sequence somebody chose.