What is still proportional to n

The previous essay’s headline is that a run-length index over thirty-two copies of a text is 11,900 bits against a compressed self-index’s 30,557, and that its run count has not moved since the second copy.

It was 4,440 bits at two copies. So it grew by a factor of 2.7 while the quantity it is supposed to be a function of grew by a factor of 1.00.

At two copies the $n$-sized terms are 7% of the structure. At thirty-two they are 50%.

What the two terms are #

Everything that stores the transform is proportional to $r$: the run starts, the run heads, the per-symbol run lengths. Those grew 1.45× across a sixteenfold growth in the collection, and the growth is entirely the widths — a position in 16,384 needs 14 bits where a position in 1,024 needs 10.

Everything that answers where is proportional to $n$:

• sampled positions — the text position of one row in every $s$, so $n/s$ entries of $\lceil\log_2 n\rceil$ bits;
• sample marks — a vector saying which rows are sampled, so that a row can ask in one operation whether it is one.

Neither has anything to do with the transform, with runs, or with repetition. They exist because locate has to turn a row into a position, and the only way to do that without walking to the end of the text is to have written some positions down.

A sample is a position, and positions do not compress because there are $n$ of them and they are all different. That is the whole of it, and it is why the term is there in every self-index this collection has built regardless of what the transform is stored as.

The shape of the claim, and where the term hides in it #

“An index of size $O(r \log(n/r))$” is a true description of a structure this essay is about, and it is a description of the transform’s representation only. The full size is

$$O\!\left(r \log \frac{n}{r}\right) \;+\; O\!\left(\frac{n}{s}\log n\right)$$

and the second term is not $o$ of the first. On a highly repetitive collection $r$ is small by design, so the first term is small — and the second is unchanged, which means the more repetitive the collection, the larger the share the sampling takes.

This collection has met that shape before, from the other direction. The entropy-bounded index is “$nH_k + o(n)$”, and the $o(n)$ turned out to be a quarter to three-fifths of it at the block lengths anybody actually uses. Here the leading term has been made small on purpose and the same thing happens harder: making the leading term small does not make the lower-order term smaller, it makes it the answer.

The obvious repair, and what it costs #

The sampling rate is a parameter. Turn it down.

At one sample in 1,024 the $n$-sized terms fall to 459 bits — 7% of the structure — and a locate walk costs up to 1,023 LF steps per occurrence. At one in sixteen they are 21,525 bits, which is three and a half times everything else in the index put together.

That is not a repair, it is the trade the field has had since it opened, and on a repetitive collection it is a worse trade than usual. A pattern occurring in thirty-two documents has thirty-two occurrences, each needing its own walk — so the collection that makes the transform cheap is the collection that makes locate expensive, because repetition is exactly what multiplies the occurrence count.

The two costs move in the same direction and it is the wrong one.

The repair that works is a different sampling #

Sample at the boundaries of the transform’s runs.

The observation behind it is that the suffix array is not arbitrary at a run boundary: within a run of the transform, consecutive rows have consecutive text positions offset by the same amount, so knowing the position at one end of a run gives every position in it for the cost of the walk within the run. Keep $O(r)$ samples chosen that way and locate no longer needs $n/s$ of them.

That is the r-index, it is not built here, and the reason it is worth naming precisely rather than gesturing at is that it is the only part of this structure that would make the whole thing proportional to $r$. Everything else already is.

What can be said from what is built: the term it removes is 50% of this structure at thirty-two copies and 4% at one, so the construction’s value is a function of the repetition and not of the size — the same statement that has been true of every part of this strand.

Why the r-sized terms grew at all #

The 45% growth in the parts proportional to $r$ deserves an explanation, because $r$ did not move and a term proportional to a constant should be constant.

It is the widths. Every part of the transform’s representation stores positions, and a position in a longer collection needs more bits:

Four extra bits per position across the sweep, and the structure holds each run’s position twice — once in the run-start vector and once in that character’s run-length vector — so the growth should be $224 \times 4 \times 2 = 1{,}792$ bits. Measured: 1,872.

Better, as a slope. Per run, the $r$-sized bits go from 18.4 to 26.7 while $\log_2(n/r)$ goes from 2.2 to 6.2:

$$\frac{26.7 - 18.4}{6.2 - 2.2} = 2.08$$

against a predicted 2, one for each of the two width-bearing structures. That is the $\log(n/r)$ in the published bound, fitted rather than quoted, and the departure from the integer is the ceilings in the two widths rounding at different points.

Stated that way it also answers what a run-length index actually is. It is not $O(r)$ and was never claimed to be: it is $O(r\log(n/r))$, and the logarithm is the width of a position rather than anything about how the runs are stored. The constant part of a run’s cost — its head, its share of the C table — does not move at all across this sweep, and the part that does is exactly the part with an $n$ inside it.

Which n-sized terms are avoidable and which are not #

Three of them, and they are not the same kind of thing.

The sampled positions are avoidable, by the construction above, at the cost of a different and more intricate structure.

The sample marks are avoidable more cheaply and are not avoided here. A vector of $n$ bits with $n/s$ ones is stored plainly in this structure and could be stored the way the run starts are — $\lceil\log_2 s\rceil + 2$ bits per one — which at $s = 64$ would take 2,056 bits to about 1,570. That is a real 4% of the structure left on the floor for the sake of one representation being used in one place and a different one in another, and it is recorded rather than fixed because fixing it would change the plate this essay is about without changing its conclusion.

And the $\log n$ in every width is not avoidable at all. A position in a text of $n$ characters needs $\lceil\log_2 n\rceil$ bits whatever else is true, so even a structure with $O(r)$ samples has an $n$ inside it, under a logarithm. That is where the $\log(n/r)$ in every published bound for this family comes from, and it is the one term nothing removes.

Where the sampling rate should actually be set #

The table above is a trade and this collection’s habit is to say what decides it rather than to draw the curve and stop.

The samples cost $\frac{n}{s}(\lceil\log_2 n\rceil + c)$ bits and buy a locate walk of at most $s$ LF steps per occurrence. So the question is what a bit is worth against an LF step, and the answer depends on something outside the structure entirely: how many occurrences a typical query has.

On a repetitive collection that number is not small. A pattern present in one document of thirty-two copies is present in all thirty-two, so the occurrence count is multiplied by the same factor that made the transform cheap. A query returning 32 occurrences at $s = 1{,}024$ costs up to 32,736 LF steps to place them — against a structure of 6,448 bits, which is to say the walk is five times the size of the entire index in operations.

That is the shape of the trade nobody states: on the collections this family of structures exists for, the sampling rate cannot be turned down, because the same repetition that makes the index small makes the walks numerous. The r-index’s run-boundary sampling is not an optimisation of the parameter — it is the only way out of a corner the parameter cannot leave.

And it explains the direction of the whole family’s development. The transform’s representation was solved first because it was the term in the headline; the sampling took longer because it is the term that only becomes visible once the first one is small.

And there is a second one, if the index has to extract #

Everything above counts the sampling that locate needs. An index that can also extract from the middle of the text carries a second array of the same size, indexed the other way round — and it is proportional to $n$ for exactly the same reason.

Two thirds of a structure whose headline is that its size is a function of the run count.

The two arrays are not redundant and neither can be derived from the other in a query’s time. They answer inverse questions and the inverse of a sampled array is not a sampled array — knowing the positions of every sixty-fourth row says nothing about which row a given position sits in unless that position happens to be one of them.

So the honest description of a run-length self-index supporting counting, locating and extraction is a structure with one term proportional to $r$ and two terms proportional to $n$, of which the second and third are the majority on any collection repetitive enough to justify the first. That sentence appears in no statement of the family’s size, and it is arithmetic rather than a measurement — every quantity in it is in the definitions.

The general shape, which this field keeps meeting #

Four times now, in four fields, the same thing.

A windowed cardinality estimator’s registers are its payload and its timestamps are 2,392 bits of 4,592 — the clock is more than half the structure and no accuracy parameter touches it.

A compressed self-index is “$nH_k + o(n)$” and the $o(n)$ is a quarter to three-fifths of it.

A run-length index is “$O(r\log(n/r))$” and the sampling is half of it.

And in every one of the three, the term that dominates is the one that is not what the structure is about — the clock rather than the count, the directory rather than the payload, the answer to “where” rather than the answer to “what”. A structure is described by the term its designers found interesting, and measured by the term nobody wrote down.

The remedy is the same in all three cases and it is a habit rather than a technique: every size reported here names its parts and the parts are required to sum to it. A total cannot show that one of its terms is the majority of it, and a description in asymptotic notation cannot either, because the whole function of the notation is to drop the term that turned out to matter.

The occurrences the query did not want #

The corner the sampling rate cannot leave has an exit, and it is not a better structure. It is a better question.

A pattern present in one document of thirty-two near-identical copies is present in all thirty-two, and locate dutifully places every one — thirty-two walks, thirty-two positions, thirty-two lines of output that say the same thing about thirty-two copies of the same passage. A reader searching a version history for a phrase does not want thirty-two positions. They want to know which revisions contain it, or that it has been there since revision four, or simply that it is present.

The multiplication that makes locate expensive on a repetitive collection is a multiplication of answers nobody asked for. That is worth separating from the structure’s cost, because it changes what the fix should be. Turning the sampling rate down attacks the price per walk; asking a different question removes most of the walks.

The question that removes them is document listing — which documents contain this pattern — and it is a genuinely different problem with a genuinely different structure, not a filter applied to the occurrence list. Placing every occurrence and then taking the distinct documents is the expensive thing being avoided, so an implementation that answers the cheap question by doing the expensive one and deduplicating has kept every cost this essay is about.

Two things follow that are worth holding together.

The repetitive collections that motivate this whole family of structures are also the collections on which the occurrence list is most redundant. A hundred genomes give a hundred hits for every conserved region; a thousand revisions give a thousand for every line that survived. The property that makes the index small is the property that makes its output repetitive, and both come from the same place.

And it is a second instance of the field’s standing complaint, arriving at the query side rather than the size side. The structure is described by the operation its designers found interesting — counting, which is cheap and beautiful — and is used through the operation nobody wrote down, which on this data is neither.

Three parts, and two of them are subsampled permutations #

Standing back from the accounting, the structure has a shape worth naming, because it says where the family’s remaining work is.

The transform’s representation, which is proportional to $r$ and is what every essay in this strand has been about. Solved, in the sense that it does what it claims.

The row-to-position array, which is a suffix array with all but one entry in $s$ thrown away.

The position-to-row array, which is the inverse suffix array with the same entries thrown away.

So a self-index supporting all three operations is a compressed transform plus two subsampled permutations, and the compression work has been done on the first of the three. The second and third are stored exactly as a suffix array stores them — full-width integers at regular intervals — which is to say that the part of the structure this whole field was invented to replace is still present, at one entry in $s$ instead of one in one.

Read that way, the r-index’s contribution is precise: it is the first construction to make one of the two permutations proportional to the same quantity as the transform. One of three parts remains, and this collection has said what it is, what it costs, and that nothing here removes it.

What is not measured here #

The r-index itself. Named, priced by what it would remove, not built. Its sampling is a genuinely different construction and its locate cost is a different curve, and nothing above says what that curve looks like.

A collection whose documents differ. The copies here are identical, which makes the $n$-sized share as large as it can be. On a collection with real divergence $r$ is larger, so the $r$-sized terms are larger, so the sampling’s share is smaller — and the sweep that would say by how much is not run.

Whether the r-index’s samples are enough for extraction. Run-boundary sampling is stated above as the repair for locate. Whether the same samples serve the position-to-row direction is a separate question with a separate answer, and nothing here addresses it.

What a query costs on this structure. Everything in this essay is bits. The three counted operations a rank performs here are the previous essay’s subject, and the interaction between them and the sampling rate is unmeasured.

Turning the dial once shows the direction; turning it twice shows whether the term ever actually goes away. It does not: at one sample in a thousand the sampling has fallen to a few per cent of the structure and the remaining $n$-sized parts — the ones that are not the sampling — are what is left, which is the whole point of separating them.