Every occurrence at the same price

Here is a sampling rate being swept on a collection of sixteen copies of a 512-character text, with the two costs it decides beside it.

One value in one: 131,088 bits, no walk at all. One in four: 36,882 bits, 1.71 LF steps an occurrence. One in thirty-two: 5,397 bits, 13.14 steps. One in 128: 1,495 bits, 63.43 steps.

Every one of those points is available and none of them is a mistake. The dial does what a dial does.

Two costs and one parameter #

The shape is familiar and this collection has met it in several fields. A structure has a resource it can spend and a cost it can lower, one number connects them, and the product is fixed by the design rather than by the data. The frontier between time and space is where that was drawn over ten sorts at once, and choosing a growth factor is the same argument in an allocator.

A suffix-array sampling is a clean instance. Keep one value in $s$ and a walk is at most $s$ LF steps; the values are $n/s$ of them; the two multiply out to a constant. Nothing here depends on the text, which is exactly why the curve is smooth and why every point on it looks equally reasonable.

The measurement below is that the r-index is not a point on that curve, and it is worth being careful about what that does and does not mean.

What the r-index spends per occurrence #

One predecessor query. Not on average, not amortised: exactly one, for every occurrence after the first, and the plate that measures it asserts the count rather than computing it from the answer size.

A locate of an eighty-occurrence pattern on a repetitive collection takes 79 applications of $\varphi$, zero LF steps, and 144 ranks in total including the search itself. The same query on a regularly sampled run-length index at one value in thirty-two takes 1,136 LF steps and 6,643 ranks, and at one in sixty-four takes 2,672 and 15,635.

The zero is the part worth checking rather than believing, and the gate checks it: after a locate, the LF-step counter must be exactly where it was before. A structure that fell back to walking in some corner would still return correct occurrences, and its cost would be back on the curve.

The comparison that is like for like #

Two structures with different costs per occurrence cannot be compared by their sizes, and this is where the previous essay’s near-tie becomes informative rather than disappointing.

At thirty-two copies the r-index is 17,047 bits and the run-length index at one in thirty-two is 17,391 — two per cent apart, and a reader could reasonably conclude that the whole apparatus bought nothing. It did not buy size. It bought size at a step count, and the honest comparison holds the step count fixed and asks what each policy costs.

Fixing it at one step per occurrence: the r-index’s sampling is 10,244 bits. The nearest regular rate that reaches one step or fewer is one value in two, at 69,649 bits. Six point eight times as many, for the same answer at the same speed.

Fixing it the other way — at 10,244 bits, the r-index’s own size — the regular sampling is at one value in sixteen and pays 6.29 LF steps an occurrence.

What “one dial” hides about the walk #

The curve above plots the measured steps rather than the rate, and the two are not the same number in a way worth a paragraph.

A rate of one in thirty-two guarantees at most thirty-one steps and does not promise thirty-one. What a query actually pays is the distance from each of its rows to the nearest sampled position, and that distance depends on where the occurrences sit modulo the rate. The measured column on this collection runs 0.57 steps at one in two, 2.86 at one in eight and 13.14 at one in thirty-two — close to half the rate, which is what a uniform offset predicts, and not equal to it.

The same query on a different pattern gives different numbers, and this is one of the places where quoting the rate as though it were the cost quietly turns a bound into an estimate. A limit is not a prediction is this collection’s standing form of that complaint; here it is mild, because the bound and the measurement are within a factor of two.

What it means for the plate is that the curve is drawn from counters rather than from arithmetic, and its points wobble. The r-index’s point does not wobble: one predecessor query per occurrence is exact, and the assertion behind the plate demands exactly $\text{occurrences} - 1$ of them.

The control: the same samples, walked #

There is an obvious objection to all of this, and it deserves to be measured rather than argued away. Perhaps the run boundaries are simply good places to sample — perhaps the win is the sample set and the function is a detail.

So build the structure that makes exactly that claim: the same $2r$ suffix-array values at the same run boundaries, marked in a bit vector, and a locate that walks LF from each row until it lands on one. No $\varphi$, no toehold, everything else identical.

On a collection of sixteen copies with a six-character pattern, that structure takes 2,955 LF steps per occurrence, with a worst single walk of 6,907 steps. The regularly sampled structure at one value in thirty-two takes at most 32.

Why the walk is unbounded, and why that is the interesting part #

The reason is worth stating because it is the mechanism the whole strand depends on, seen from its failure side.

A regular sampling marks every $s$-th text position, so from any row, walking back through the text hits a marked position within $s$ steps. That guarantee is about the text, and it holds whatever the transform looks like.

Run boundaries are positions in the transform. A collection of thirty-two identical copies has a transform of 233 runs over sixteen thousand rows, and the text positions those boundaries correspond to are wherever the sorting put them — clustered, not spread. So a row can be thousands of LF steps from the nearest one, and nothing in the construction bounds it.

A sample set is not a locating strategy. What makes $2r$ values enough is that the structure never walks: the first occurrence arrives with the search and every other one is a jump between suffix-array rows rather than a walk through the text.

Where the two policies do the same thing #

The trade curve and the point are not always far apart, and the plate says so.

At one value in one — every suffix-array value kept — a regular sampling also locates in no steps, and it is the only rate that does. That is the honest ceiling of the curve: 131,088 bits on this collection, against the r-index’s 10,244 for the same behaviour. Twelve point eight times.

That ratio is not a constant. It is $n\lceil\log_2 n\rceil$ against about $2r\lceil\log_2 n\rceil$ plus the predecessor structure, so it is roughly $n/2r$ — a property of the text and not of either structure. On this collection $n/2r$ is 35; on an ordinary English text of the same length it is 1.7; on a four-symbol text it is under one, which is the case a sampling that costs more than the array is about.

The two halves of the win, separated #

A locate on the r-index has two costs and they are paid at different times, so it is worth asking which of them the comparison above is really about.

The toehold is paid once per query, during the search. It costs a lookup on some fraction of the pattern’s characters — 18% of them for a sixteen-character pattern on this collection, 75% for a two-character one, as the occurrence carried through the search measures. It does not scale with the number of answers.

$\varphi$ is paid once per answer. On a query returning eighty occurrences it is 79 applications; on a query returning one it is none at all.

So the two policies separate most sharply on queries with many answers, which is exactly the regime a repetitive collection produces. A pattern occurring once per copy occurs thirty-two times in thirty-two copies, and a regular sampling pays its walk thirty-two times while the r-index pays a lookup or two and then 31 jumps. The advantage grows with the repetition for the same reason the size advantage does, and both come from the same property of the transform.

The step counts are measured, not derived from the rate #

One detail of the sweep is worth mentioning because getting it wrong makes the whole plate meaningless, and the first version did.

The natural way to fill in the walk column is to write $s/2$ — the expected distance to a sampled position. It is a reasonable estimate and it is not what the structure does, so the measurement takes the counter’s own reading instead.

The first sweep did this on a pattern planted at position 128 of a 512-character base, which meant its occurrences were at 128, 640, 1152 and so on — every one of them a multiple of 128, and therefore sampled at every rate the sweep tried. Eight rates, all reporting zero steps per occurrence, and a perfectly clean plate showing that the sampling rate does not matter.

Moving the pattern three characters along fixes it. The lesson is the one this collection keeps relearning: a sweep over a parameter has to be run on an input that does not agree with the parameter, and a parameter that waits for another is the general form of the trap.

What the reader is choosing between #

Set out plainly, because the plates are about mechanism and a practitioner wants the decision.

If the collection is repetitive and locates are frequent, the run-boundary sampling dominates: fewer bits than any rate that matches its speed, and faster than any rate that matches its size. If locates are rare and counts are common, neither policy matters much, because how many costs the same in both and neither touches a suffix-array value to answer it.

If the collection is not repetitive, the run-boundary sampling is a mistake and a rate is what to use, because $2r$ is then a constant times $n$. And if the collection is repetitive but the queries return one or two occurrences each, the toehold is doing all the work and $\varphi$ is doing almost none — the win is still there and it is coming from the other half of the machinery.

A third cost neither plate shows #

Both of the costs above are query costs, and there is a construction cost neither of them contains.

The r-index’s sampling is derived from the suffix array, which has to exist at build time. So does a regular sampling’s. Neither structure avoids building the array; they differ in what they keep afterwards, and the peak memory during construction is a quantity this collection measures elsewhere and does not measure here.

That is worth flagging because it is exactly the sort of term that dominates in practice while being absent from every plate — the shape what is still proportional to n is about, and the reason its finding generalised beyond the structure it was found in.

Why this is a space essay #

The field this sits in is the one that measures what an algorithm keeps rather than what it does, and the placement is deliberate rather than administrative.

Every number in this essay is a size traded against a count of operations, and the structure being compared is one whose entire claim is a size. Measuring what an algorithm keeps opened that field by adding two counters, on the grounds that a sort with a buffer and a sort without one are different algorithms with identical comparison counts; the same argument applies here with the buffer replaced by a sampling and the comparisons by LF steps.

What the index adds to that field is a third possibility. The sorts on the frontier are all on it: nothing dominates, and every point is a real choice. Here one policy is off the curve, and that is only possible because it is a function of something the curve’s parameter cannot see — the shape of the transform rather than the length of the text.

A dial can only trade the quantities it is a dial on. A structure that reads the data can be better than every setting of it, and that is not cheating; it is what makes the measure worth choosing carefully, which is the argument the collection decides which index is small closes this strand with.

The curve is not a hyperbola, and it sags in the unhelpful direction #

“The product is fixed by the design” is the sentence the trade rests on, and the sweep’s own numbers say it is not quite true. Multiplying the two columns: 63,068 at one value in four, 70,917 at one in thirty-two, 94,828 at one in 128. The product rises by half across a thirty-two-fold range of the rate, monotonically, which a hyperbola does not do.

The cause is in the bits rather than in the steps, and it is the part of a sampling that is not the samples. Each kept value costs $\lceil\log_2 n\rceil$ bits, and the structure also has to record which rows carry one — a sparse bit vector with $n/s$ ones over $n$ positions, which costs about $\log_2 s + 2$ bits per one. So

$$\text{bits} \;\approx\; \frac{n}{s}\left(\lceil\log_2 n\rceil + \log_2 s + 2\right)$$

and at $n = 8{,}192$ that gives 36,864 at $s = 4$ against 36,882 measured, 4,608 at $s = 32$ against 5,397, and 1,152 at $s = 128$ against 1,495. Multiplying by the $s/2$ steps a uniform offset predicts leaves $\frac{n}{2}(\log_2 n + \log_2 s + 2)$ — a hyperbola times a logarithm in the rate.

Two things follow, and both sharpen rather than soften the essay’s conclusion.

The first is that a sparse sampling is worse than the naive product suggests, and worse by more the sparser it gets. Each doubling of $s$ halves the value count and adds a bit to every surviving entry’s address, so the last doublings buy progressively less. A reader sizing from “rate times steps is constant” over-estimates what a coarse rate saves, and the over-estimate is 50% by the end of this sweep alone.

The second is that the marking vector is again the term nobody counts. At one value in four it is a fifth of the sampling’s bits; at one in 128 it is nearly half. That is the same accounting a bit for every bit makes about a rank directory and an index larger than what it indexes makes about a whole structure — the part that says where outgrows the part that says what, and it does so precisely where the structure is being made small.

It also explains a number in the like-for-like comparison above. Reaching one step or fewer needs $s = 2$, and the formula gives $4{,}096 \times 16 = 65{,}536$ bits against the 69,649 measured — so the six-point-eight-times figure is not an artefact of a particular rate landing badly. It is what the curve costs where it crosses one step, and the crossing is expensive because that is the end of the sweep where the logarithm has done the least for it.

And it is worth noticing what the r-index does not pay here. Its samples are the run boundaries, which the structure already locates through the run-start vector it needs anyway, so there is no second marking vector and no $\log_2 s$ term — the sampling has no rate for a logarithm to be taken of. The point is off the curve partly because the curve is carrying an overhead the point has no analogue of.

The honest limit #

The trade curve is measured at one collection, one pattern and one length. Its shape is robust — the product of rate and steps is a constant by construction — but the position of the r-index’s point relative to it depends on $r$, and $r$ depends on the collection.

The step counts are also LF steps rather than time. An LF step on a run-length transform is three counted operations and on a wavelet tree over the whole transform it is a symbol rank; a predecessor query here is a binary search over $r$ anchors. Putting them on one axis is a comparison of acts, which is what this collection counts, and it is not a claim about which is faster on a machine. That claim would need the fifth counter and a model of the memory system, and neither is in this essay.