A sixth of what, exactly

The deferral that asked for a counting-only reverse half priced it at about a sixth of the second index, and the measurement agrees: 16.7%.

At one sampled position in every 32. At one in four it is 30.5%, and at one in a hundred and twenty-eight it is 14.0%.

Same structure, same text, same alphabet, a factor of 2.2 between the ends of a parameter nobody states when stating an index’s size.

The dial #

The sampling rate is the only free parameter in an FM-index that changes its size by an order of magnitude, and it is set by what the index is for.

Store every position and the index contains a suffix array — n⌈log₂ n⌉ bits, which is the thing the whole family exists to avoid. Store one in a thousand and the index is nearly as small as its counting parts, and a locate walks up to nine hundred and ninety-nine steps backwards before it finds a stored position.

Between those, everything is a trade: bits against LF steps, and the exchange rate is exactly linear in both directions. The sampling that goes the other way is the second sampling this collection prices, the one indexed by position rather than by row; this is the first.

What the sweep on this page adds is that the share of the index the sampling accounts for is what the saving is, so quoting a saving means quoting a rate.

What it does to a locate #

The other side, measured on the same structure.

At one in 4: 1.67 steps an occurrence. At one in 8: 3.0. At one in 16: 7.0. At one in 32: 15.0. The prediction is (s − 1)/2, and the measurements sit on it — 1.5, 3.5, 7.5, 15.5 predicted against 1.67, 3.0, 7.0, 15.0 measured.

That agreement is worth checking rather than assuming, because the rows a search returns are not a uniform sample of the rows: they are the rows of one pattern, which are contiguous and correspond to scattered text positions. The measurement says the scattering is thorough enough that the uniform prediction holds, which is a fact about the transform rather than about the sampling.

Where the floor comes from #

The saving falls as the sample thins, and it stops falling at 14%. That floor is the interesting part of the plate.

The locating apparatus is two things and only one of them shrinks. The sampled positions are (n/s)⌈log₂ n⌉ bits and halve every time s doubles. The marks are a bit vector over every row — n bits — saying which rows are sampled, and n bits is n bits whether one row in four is marked or one in a thousand.

At one in 4, the positions are 28,686 bits and the marks are 8,193: the positions dominate and the saving is large. At one in 128, the positions are 900 bits and the marks are 8,193, nine times larger. So the curve flattens onto the marks, and the marks are what the saving is at the sparse end.

Half of the locating apparatus does not depend on the sampling rate at all, and it is the half that is usually left out of the arithmetic — the usual quoted size of a sampled FM-index is the wavelet tree plus (n/s) log n, with the marks folded into a phrase about “constant-time predecessor support”.

Why this is in the taught-wrongly field #

Not because a number is wrong, but because the number’s argument is missing.

Every measurement here is exact. A counting-only reverse half saves 16.7% is a true sentence about an index sampling one row in 32 over eight thousand characters of a four-symbol alphabet. Written down without those, it becomes a property of a structure, and the structure does not have that property — a family of structures parameterised by s does, with the value varying by 2.2 across the range people actually use.

That is the same failure this collection keeps finding in per-character rates: the half of a fall that is the logarithm is the version where the hidden argument is the text length, and this is the version where it is a configuration setting.

The check standing on it is a two-ended one. Measure the saving at both ends of the dial and require them to differ by at least a factor of two — so the claim “this number needs its rate” is itself something that can fail.

What the same question does to other quoted numbers #

The habit this page is about — ask what a quoted share is a share of — is worth running over the rest of this collection’s index sizes, because it lands somewhere every time.

The wavelet tree’s share of an FM-index is quoted here as about half. That is at a four-symbol alphabet. On English, with a Huffman-shaped tree, the tree is 4.5 bits a character against DNA’s 2 — so the tree’s share rises to two thirds and the locating apparatus’s share falls, without either structure changing.

The directories’ share is quoted as a seventh of the tree. That is at a block size of 64 and a superblock of 512, which are choices; halving the block doubles the directory and makes a rank slightly faster.

And the text’s share of a document index is quoted at n⌈log₂ σ⌉ bits, which is exactly the number two thousand documents of two hundred characters shows moving by 71% when the collection is cut into more documents with distinct separators.

Three shares, three hidden arguments — the alphabet, a block size, a document count. None of them is a mistake, and none of them is stated in the sentence that quotes the share.

What the sparse end is actually for #

A reader might reasonably ask why anyone samples one row in 128, since a locate then costs sixty-odd LF steps.

Because many queries never locate. A count query — how many times does this occur — needs no sample at all. An existence query needs none. A search that narrows an interval and reports its width is the whole of what many systems do with an index, and for those the entire locating apparatus is dead weight in both halves rather than one.

So the sparse end of this dial is where an index is mostly a counting structure, and at that end the thing this page measures is smaller in relative terms and the thing it is measured against is smaller too. What the plate shows is that even there it is a seventh, because of the marks.

What a size quoted for an index should carry #

Four numbers, and this collection now tries to carry all of them on every plate.

The text length. Sizes here are quoted in bits and in bits per character, and the second is only a rate if the structure is linear — which the wavelet tree is and the directories are not quite.

The alphabet. Every level of the wavelet tree is n bits, and the number of levels is ⌈log₂ σ⌉ for a fixed-length code or the entropy for a Huffman-shaped one. An index over DNA and one over English differ by a factor of two and a half before anything else is decided.

The sampling rate, which is this page.

And the vector representation. A plain bit vector with directories, an entropy-compressed one, a run-length one: the same structure, three sizes.

Any of the four missing turns a measurement into a slogan. All four present makes a size a thing somebody can reproduce, which is the standard an index has a size is about.

The number to carry away #

If one number has to be quoted, quote the one at the setting the structure will actually run at, and say what it is.

For an index that locates often, one row in 8 or 16 is normal, and the saving is 20–24%. For an index that mostly counts, one in 64 or 128, and it is 14–15%. For a structure tuned to a suffix array’s speed, one in 4, and it is 30%.

The honest summary is a range with its axis attached: the reverse half’s locating apparatus is between a seventh and a third of a bidirectional index, depending on how often positions are kept.

That sentence is longer than “a sixth” and it is the one that survives being quoted.

The shape of the dial, and why it is not a curve to optimise #

One more thing about the parameter, since a plate with a monotone curve on it invites the question where is the optimum.

There is not one, because the two axes are not commensurable. Bits and LF steps are different currencies, and the exchange rate between them is a property of the system rather than of the structure: an index held in memory on a machine with a slow store trades differently from one held on disk, and one answering a thousand queries a second trades differently from one answering ten.

What the sweep gives instead is the shape of the trade, and the shape is the useful part. Bits fall geometrically with the rate and steps rise linearly, so the product is roughly constant across the middle of the range — meaning the choice is nearly free within a band and expensive outside it. At one in 4 the index is large; at one in 128 the locate is slow; between 8 and 32 almost nothing changes except which resource is being spent.

That is why the recommendation on the next page is a band rather than a number, and why the honest form of any single number here carries its setting. The model has parameters is the theme, and a sampling rate is the clearest one in this field: it is written in a configuration file, it changes a published size by a factor of two, and it appears in no formula anybody quotes.

What the sweep does not settle #

Whether the marks can be smaller. A vector with one bit in 128 set is a sparse vector, and sparse vectors have representations far below n bits — a bit vector with m ones can be stored in about m log(n/m) bits with rank support. On this collection’s plain representation the marks are the floor; on a compressed one they might not be, and the whole shape of the curve on this page would change.

Whether the floor matters at the sizes anybody runs. Eight thousand characters is a figure’s size, not a system’s. The marks are n bits and the positions are (n/s) log n, so their ratio is s/log n — meaning the crossing between them moves with the text length, and at a hundred million characters one row in 128 puts the positions back above the marks.

And what the second sampling does to all of it. A real index supporting extraction from an arbitrary position carries another array of about the same size, in the forward half. Adding it makes the forward half bigger, the reverse half’s share smaller, and every percentage on this page smaller with it.

The dial has a floor, and it is thirteen per cent #

Three points are enough to separate the part of the locating apparatus that follows the rate from the part that does not, and the second is what the saving bottoms out at.

Write the saving as $L/(C + 2L)$ — one half’s locating apparatus over the whole index — and invert the three measurements. At one in four, $L = 0.782\,C$; at one in thirty-two, $0.251\,C$; at one in a hundred and twenty-eight, $0.194\,C$.

Fit $L = a/s + b$ to the two sparse points and it gives $a = 2.43\,C$ and $b = 0.175\,C$. Evaluate that at one in four and it predicts $0.783\,C$ against a measured 0.782 — a two-parameter model landing on a third point it was not given.

So the apparatus is 2.43/s of the counting parts, plus a fixed 0.175 that no sampling rate removes. The fixed part is the marker structure saying which rows are sampled, which is a bit vector over the rows however few of them are set.

Which gives the dial its two ends. As the sampling goes sparse the saving tends to $b/(C+2b) = \mathbf{13.0\%}$ and stops; as it goes dense towards one in one it reaches about 42%. The sweep’s 14.0% to 30.5% is most of that range and not all of it, and the important half is the lower end: the saving never goes to zero, so a system sampling as sparsely as it likes still banks an eighth of its index by dropping the reverse half’s locating apparatus.

That sharpens the page’s own claim rather than softening it. A number quoted without its rate is a number about a setting somebody chose is right, and the range it is chosen from is bounded — 13% to 42%, with 16.7% at the common default. A reader who cannot find out the rate a saving was quoted at now knows it is somewhere in a factor of three, and knows the floor.

It also says which way the saving, spent’s arithmetic tilts. Spending the saving on a denser forward sampling moves along a curve whose lower end is pinned, so the trade is always available and its size is bounded — and an index that cannot locate is worth building at every rate rather than only at dense ones.

Where this sits in the strand #

The half that is never asked where is the observation — the reverse index answers ranks and never positions. An index that cannot locate builds the thing and prices its parts. This page sweeps the parameter every one of those prices depends on, and the saving, spent is what to do with the result.

The four could have been one page with four sections, and they are four because the middle two are measurements and the last is a recommendation. A recommendation that arrives in the same breath as its evidence is a recommendation nobody can check separately.

Why the prediction is worth drawing #

The dashed line on the locate plate is (s − 1)/2 — the expected walk if a query’s rows fell uniformly among the sampled ones — and it is drawn rather than computed into the caption for a reason this collection is consistent about.

A prediction drawn beside a measurement is a claim that can fail. The rows a search returns are the rows of one pattern: contiguous in the index, and corresponding to text positions scattered by the transform. Whether that scattering is uniform enough for the average walk to be half the gap is a fact about the Burrows–Wheeler transform, not an arithmetic identity — and a text with structure the transform preserves could easily put a pattern’s rows disproportionately near or far from sampled positions.

Measured: 1.67 against 1.5, 3.0 against 3.5, 7.0 against 7.5, 15.0 against 15.5. Close enough to use, and slightly under the prediction at three of four settings, which is a small favourable bias worth noticing and not worth explaining on four points.

What a system actually chooses #

The dial is set once, at build time, and the choice is usually made by default rather than by measurement.

The common defaults are 32 and 64, and they come from the same place most defaults come from: they are powers of two that make the arithmetic tidy and put the index somewhere near the middle of its size range. At those settings the saving this strand measures is 16.7% and 15.2%.

A system that knows its own query mix can do better. If most queries count and few locate, sample sparsely and the whole locating apparatus is small in both halves — the saving falls to 14% and so does everything it is a share of. If most queries locate and return many occurrences, sample densely, and the saving rises to 30% and is worth spending rather than banking.

That is the shape of the recommendation, and the saving, spent is where it becomes arithmetic: at equal total size, an asymmetric index with a forward sampling four times denser locates five times faster.

The check, once more #

The claim this page makes is unusual for this collection: it is a claim that a number needs an argument, rather than a claim about a number.

So the check is unusual too. It measures the saving at both ends of the dial and requires them to differ by at least a factor of two — meaning the assertion “quoting this without its rate is quoting nothing” is itself something the build can refuse. If a future change to the structure made the saving flat across the dial, the check would fail and this page would be wrong.

That is what the check must reject looks like applied to a methodological claim rather than to an algorithm, and it is the only instance of it in this collection.

Where this sits #

The half that is never asked where is the observation; an index that cannot locate is the structure; this page is the parameter; the saving, spent is the recommendation.

And the neighbouring strand is about the same object from the other side: every child at once removes a factor of σ from the extensions a bidirectional search performs, where this one removes a sixth of the bits the structure holds. Both apply, neither interacts with the other, and nothing here measures them together.