Three savings on one structure

Three changes to a bidirectional index have been measured here, each on its own, each against the same published baseline.

The compound walk. A wavelet tree can return a symbol’s rank and the count of smaller symbols before a position from one descent, at the price of the rank alone. An extension that had been summing σ separate ranks becomes one walk. The count that was already there: 139.7 bit-vector ranks against 10.0 at a twenty-six letter alphabet.

The interval enumeration. One descent returns every symbol present in an interval with the interval each occupies, so a search never attempts an extension that finds nothing. The branches that find nothing: 168,000 ranks against 24,000 on a one-error search over twenty symbols.

The sparse marks. An index’s mark vector holds n/s ones in n positions and is stored as n bits; represented as an Elias–Fano array it is a fifth of that. A position split in two: 15% of a whole index at one sampled position in thirty-two.

A reader with those three numbers has a question, and the answer is not the product.

What the third one composes with #

The mark representation is a size change and the other two are operation changes, so the first question is easy.

Measured directly: the same branching search over the same index costs 12,486 bit-vector ranks whether the marks are plain or sparse. Exactly the same number, because a search never touches the marks — it reads the wavelet tree, and the marks are read only when an interval is turned into text positions.

And the sparser-marked index is smaller: 102,154 bits against 106,160 at the rates compared.

So the size saving is orthogonal to both operation savings, in the strong sense that one of them does not change the other’s number at all. That is what “composes” means and it is worth checking rather than assuming, because a size change that slowed the search would compose differently.

The orthogonality check is worth describing because a weaker version of it would have been easy to accept. The obvious check is that the two indexes report the same occurrences, which they do — but that says nothing about cost, and a change that made the search slower while keeping the answers would pass it.

The check that was written requires the rank counts to be identical, not close: 12,486 against 12,486. An inequality with a tolerance would pass on a change that added a few per cent, and the claim being made is that the marks are not read at all during a search, which is an exact statement.

That is the general shape of an orthogonality claim: not “these do not interfere much” but “this one does not touch that one”, and the check for it is an equality.

What the first two do not compose with #

The two operation savings both act on the same thing — what an extension costs — and the measurement of them together is not the product.

On a one-error search over a twenty-symbol alphabet:

The published loop: 1,478,400 ranks. The compound walk inside the loop: 134,400. A factor of 11.0. The enumeration: 18,916. A factor of 78.2.

An index with both would be expected to cost 1,478,400 / (11.0 × 78.2) = 1,719 ranks. It costs 18,916.

The shortfall is a factor of 11.0 — which is the compound walk’s own factor, exactly.

That is not a coincidence and it is not an interaction cost. Two factors that do not multiply is the arithmetic: one descent over an interval returns each present symbol’s sub-interval, which is the compound walk’s rank; and running-summing the counts in leaf order gives the walk’s smaller-count for every symbol at once. Taking both is taking the second one twice.

That the shortfall is exactly the walk’s factor rather than approximately it is what turns this from an observation into a claim. An interaction, an overhead or a shared constant would produce a shortfall of some number nobody could predict; a shortfall equal to one of the two factors says that one of them contributed nothing.

The check requires it: the measured combined factor must fall short of the product, and the shortfall must equal the walk’s factor to within two per cent. Both hold at 11.0 against 11.0.

Which is which #

Since two of the three turn out to be one, it is worth restating what the three actually are.

A size saving, in the marks, which composes with everything.

An operation saving for a search that knows its character — the compound walk. One extension by one named symbol, at a fixed cost instead of σ ranks.

An operation saving for a search that does not — the enumeration. Every present symbol at once, which subsumes the walk on that kind of search.

So there are two operation savings and they apply to two different query shapes, rather than one applying on top of the other.

An exact search branches nowhere and wants the walk. A backtracking search branches everywhere and wants the enumeration. The saving that is a loss measures the enumeration on an exact search and finds it costing about twice the walk — so the split is not a preference, it is a crossing.

The two operation savings behave differently as the search gets harder, which is another way of seeing that they are not the same kind of thing.

The compound walk is flat at 11.0 across the whole budget sweep. It makes each extension cheaper by a factor that is a property of the alphabet, and the budget does not change the alphabet.

The enumeration moves: 98.1 at no errors, 78.2 at one, 104.6 at two. Its factor follows the share of extensions that find nothing, which rises with the budget.

So a reader choosing between them on a branching search does not have to: the enumeration is ahead at every budget, by between seven and nine times. The choice is on the other axis entirely — whether the search branches at all.

What an index with all three looks like #

The structure this strand builds takes all three and it is worth describing because the combination is not obvious from the parts.

Its forward half locates, with Elias–Fano marks.

Its reverse half counts only — no marks, no sampled positions — which is a fourth change, from a different strand, and composes with the marks because it removes them from one half and shrinks them in the other.

Its extensions by a named symbol use the compound walk.

Its branching uses the enumeration, which requires the trees to be order-preserving — so it refuses a Huffman shape in its constructor, the same guard the compound index has for the same reason.

That last is the one interaction between the operation savings that is not about cost: both need an ordered tree, for the same reason, and an index doing either has the same constraint.

What the strand had to build to answer it #

The measurement above needed an index with all three changes in it, and building one turned out to need two things that neither of the original strands had.

One index rather than three. The compound walk lives in one class, the enumeration in another, and the mark representation in a third. An index with all three has to be a subclass of the first with the second’s method and the third’s field — so the code exists to make the comparison rather than because anybody wanted such an object.

One counter across all of them. Every measurement here is bit-vector ranks on the forward half’s wavelet tree, charged by a counter the index owns. Comparing three machines means running them against the same counter on the same tree, because a rank on one tree and a rank on another are not necessarily the same amount of work.

That second constraint is the reason the comparison is between traversals rather than between implementations. All three machines share a wavelet tree, a code shape, a text and a counter, and differ only in which nodes they visit.

Without that discipline a comparison of three published results would be a comparison of three papers’ experimental setups, which is the thing this collection exists not to do.

The two currencies, on one frame #

Since one saving is bits and two are operations, the composition question has a second form: does the size change cost anything at query time, and does the operation change cost anything in bits?

Neither, and both are checked.

The enumeration adds no bits. It is a different traversal of a structure already built — the same vectors, the same directories, the same code table — so an index supporting rank supports it.

The compound walk adds no bits either, for the same reason.

The sparse marks add no operations to a search and a small number to a locate: a rank on an Elias–Fano array is a select and a bucket walk of 1.25 accesses rather than a directory read, and a locate performs one per LF step of its walk.

So the composition is: two free operation savings that are one, plus a bits saving that costs a little on one operation nobody counted.

Why the question is worth asking at all #

There is a version of this essay that would not need writing, and it is worth saying why this is not it.

If three improvements had been made to three different parts of a structure — one to the wavelet tree, one to the sampling, one to the search — nobody would ask whether they compose. Independent parts compose by construction.

These three are not independent. All three are about the same index; two of them are about the same operation; and the two that are about the same operation were developed one strand apart, by different arguments, and reported as separate results.

That is exactly the circumstance in which a reader multiplies. Two papers, two factors, one structure — and the arithmetic is available and wrong.

What makes it wrong is not visible from either result. The count that was already there describes a saving on an extension by a named symbol and the branches that find nothing describes a saving on a search that branches, and neither says that the second’s operation contains the first’s. Discovering that required building an index with both and measuring it.

The general form is uncomfortable and worth stating: two savings developed separately are reported separately, and whether they compose is a third measurement nobody’s incentives produce. It is not in either strand’s interest to make it and it is the number a reader needs.

The ladder #

Applying the size changes one at a time on a bidirectional index over sixteen thousand characters at one in thirty-two:

Both halves locate: 250,584 bits. The reverse half counts only: 226,504 — 90.4%. And its marks are Elias–Fano: 210,934 — 84.2%. The saving spent on sampling the surviving half four times as densely: 241,475 — 96.4%, with a locate several times faster.

The second step is worth 15,570 bits against the first step’s 24,080, which is nearly two thirds of what the deletion was — on a structure where the deletion was the headline. The floor was the marks is where that reordering is worked out.

The fourth rung is not a saving. It is the whole of the first three spent on something else, which is the ladder, and the rung that spends.

Bits and steps on one frame #

The strand’s last measurement puts the two currencies on one plate against the parameter that moves both, which is the convention this collection adopted after reporting a trade as a win.

The size falls from 99.5% to 86.3% as the sampling thins, and the walk to a sampled position rises from 2.5 steps to 63.6. Neither line is the answer on its own: a reader choosing a sampling rate is choosing a point on the pair, and a plate showing only the first reports a structure that gets better forever.

What the two operation savings do to that pair is nothing. They move neither line, which is what orthogonal means here and is why they compose with the sampling and not with each other.

Bits and steps on one frame is that plate’s own essay, and the convention it follows was set by the half-index strand: both currencies on one frame, when a change trades.

What the fourth change would be #

The strand has three savings and there is a fourth available that nothing here builds, and it is worth naming so the list does not read as complete.

The sampled positions are (n/s)⌈log₂ n⌉ bits of arbitrary numbers, and they are the largest part of the locating apparatus once the marks are sparse. Nothing here compresses them, and there is a published approach — storing differences along the phi function rather than absolute values — that this collection built for a different structure entirely.

A function with r pieces is that structure, and its sampling is at run boundaries rather than at regular intervals: 2r values and no marks whatsoever. On a repetitive collection that is a different and larger change than anything in this strand.

So the honest state is three savings measured, one of which is two, and a fourth that would replace the thing all three are about.

The other composition question #

There is a second pair worth checking and this strand does check it: whether the size saving composes with itself across the two halves of a bidirectional index.

Dropping the reverse half’s locating apparatus removes marks and sampled positions from one half. Representing the surviving half’s marks sparsely shrinks the other. Those are different arrays in different halves, so they compose trivially — and the measured ladder confirms it: 250,584 to 226,504 to 210,934, with the second step’s 15,570 bits being exactly the forward half’s mark saving.

What makes that worth measuring rather than assuming is the ordering effect it reveals. Reported as “dropping the apparatus is worth 9.6% and then the marks are worth 6.9%”, the two look like a large improvement and a smaller one.

Reported the other way — marks first, then the drop — the numbers are different: representing both halves’ marks sparsely first, then dropping one half’s, gives a first step worth more and a second worth less, because the thing being dropped is now smaller.

Same total, different attribution. That is a general property of cumulative savings on overlapping parts and it is why a ladder’s rungs should be read as a total rather than as individual credits.

What a reader should carry #

Three numbers and a rule.

On a branching search: 78×, on a twenty-symbol alphabet at one error, from the enumeration. The compound walk contributes nothing on top of it.

On an exact search: 11×, from the compound walk. The enumeration contributes a loss on top of it.

On the structure: 16%, from dropping a counting half’s locating apparatus and representing the survivor’s marks properly, at one in thirty-two — and both of those numbers depend on the sampling rate by a factor of several.

And the rule: two savings acting on the same quantity do not multiply, and two acting on different quantities do. Deciding which case is at hand means asking what each removes rather than how large each is, and the question is answerable before any measurement.

Applied here: the marks remove bits and the other two remove operations, so those compose. The walk removes σ ranks from computing a smaller-count and the enumeration removes the extensions those ranks were for, so those do not — the second removes the work the first was making cheaper.

Asking “what does this remove?” of each of three changes takes a minute and would have got the answer without building anything. What building it added was the exactness: the shortfall is 11.0 against a walk factor of 11.0, which turns a plausible argument into a measurement.

That is the division this collection generally settles on. The reasoning says which way the answer goes and the measurement says whether the reasoning was complete, and here it was — which is worth knowing, because the two previous times this collection expected a composition it was wrong about the mechanism as well as the magnitude.