A spacing priced by what it saves

The run starts of an r-index’s Burrows–Wheeler transform are a sorted set of a few hundred to a few thousand values, sparse on average and dense where it gathers. The strand that has been storing them stores them as a partition into chunks (plain bitmaps, Elias–Fano lists, runs) cut by a shortest path over every possible cut, as cuts that follow the gathering first did. A select, the request for the $j$-th value, finds its chunk through an upper level and then has to find the value inside it, and the last several essays have been about the second half.

A second level that pays in one band gave each chunk two levels of directory: a select sample every $t$ values, naming the rank block that holds its value, and a rank sample every $s$ bits. A select reads its select sample, steps through rank samples until one counts past its target, and scans at most $s$ bits. A select sample spaced by its chunk then gave each chunk its own $t$, the power of two nearest $s$ over the chunk’s scanned bits a value, so that $t$ values span about one rank block, and the steps fell to between 0.94 and 1.33 a select on every set. The cost was bits: on exact copies at $s = 64$ the per-chunk spacing reads 54.8 bits a select for 3.875 bits a value, where a fixed spacing of 64 read 62.0 for 3.763.

That essay’s closing section put the two halves of the design against each other. The spacing rule chooses each chunk’s spacing to make the steps one, whatever that costs in bits; the path chooses the chunks to make the bits least, whatever that costs in reads. Neither sees both. A path could, if each chunk were charged its stored bits plus its expected read bits times an exchange rate $\lambda$ — bits stored a bit read — and allowed to choose among spacings of $t_0$, $2t_0$ and $4t_0$. The prediction was that on exact copies the priced path would reach under 60 bits read for under 3.80 bits a value, and under 70 for under 3.70; that on the scattered marks it would change nothing, since one density has one right spacing; and it named the risk that selects in a real r-index follow the matches, not the values.

The price the path is charged #

Everything is the earlier essays’ but the choice of spacing. The eight sets are the strand’s: the run starts over exact copies, over copies at six divergences from 0.0002 to 0.01, and over scattered marks. The path, the chunk forms, the rank samples and the model of reads are unchanged: a select reads the upper level and the chunk’s entry, the select sample, every rank sample stepped, and the bits it scans in its block.

What changes is what the path is charged for a chunk’s directory. A chunk of $k$ values whose scanned vector holds $d$ bits a value may take a select spacing of $t_0$, $2t_0$ or $4t_0$, and takes the one that minimises its stored select-sample bits plus $\lambda k$ times the bits a select is expected to read in it. The expected read is a model, because the path prices every candidate chunk and cannot replay every one: the select sample’s bits, plus $1 + td/2s$ rank samples stepped — the mean number of block boundaries between a sample’s value and a target up to $t$ values after it — plus half a block of scan. A chunk with no rank samples at all is modelled as scanning half its vector. The path is charged the same sum, so with $\lambda$ in view it may cut different chunks too.

The rate runs from 0.001 to 0.1 bits stored a bit read, at rank samples every 64 and every 128 bits. Every number below is the replayed read, never the modelled one, and every point is compared with every directory the strand has measured on the same set: two levels at fixed spacings of 64, 128 and 256, two levels spaced per chunk, select samples alone and rank samples alone.

At rank samples every 64 bits the priced path draws a curve through the gap the earlier essay pointed at. At a rate of 0.001 it takes a spacing four times the per-chunk one on nearly every value and reads 64.3 bits for 3.751 bits a value; at 0.003, 62.0 for 3.763 — the fixed spacing of 64 exactly, reached by a different route; at 0.01, 56.8 bits for 3.824. That last point is new: no earlier directory read under 60 bits for fewer than 3.875.

The prediction’s first number is missed by a fortieth of a bit: under 60 bits read, the priced path’s fewest bits are 3.824, against the predicted 3.80. Its second is missed outright: nothing priced comes under 3.70 bits a value at 70 bits read or fewer, because the rank-every-128 points, which do go under 3.60, read 85 bits and more. And at the top of the rate the curve turns back on itself, which the next sections explain: at 0.03 it reads 62.5 for 3.902, worse on both counts than the per-chunk spacing, and at 0.1 it reads 42.4 for 5.033.

Which spacing each chunk chose #

At the lowest rate a read is nearly free, so every chunk takes the sparsest spacing it is offered: 94% of values at $4t_0$. As the rate rises the choice moves down one step at a time — at 0.01, 95% of values at $2t_0$; at 0.03, 73% at $t_0$ — and the path’s chunks change with it, from five chunks to seven and then eleven. At 0.1 the path has cut 51 chunks, every one too short to carry a rank sample, and the spacing has nothing left to choose.

So on exact copies the per-chunk spacing of the earlier essay is the choice of a rate between 0.01 and 0.03, and below that rate the steps it bought are not worth their bits: a spacing twice as wide gives up about a quarter of a step a select and saves a twentieth of a bit a value, which at a rate of 0.01 is a good trade.

The rate chooses the chunks #

The plate shows the second thing the price does, which the proposal did not describe. On exact copies the path cuts 5 chunks at a rate of 0.001 and 51 at 0.1; on the scattered marks 12 and 127; at divergence 0.01, 55 and 364. A high rate makes a long chunk expensive, because even with a directory a select in it reads a select sample, a step or two and half a block, and a short chunk with no directory reads half of a short vector. At the highest rate every chunk on every set is short enough to scan.

That end of the curve is real and not useful. On exact copies the priced path at 0.1 reads 42.4 bits for 5.033 bits a value; select samples alone, measured two essays back, read 43 bits for 3.93. The priced path’s options are two-level directories at one rank width and chunks cut to suit them; it cannot choose select samples alone, and at a high rate it reaches for few reads the only way its options allow, by cutting many small chunks, which costs far more bits than the directory it is avoiding. A rate is only as good as the choices it prices.

The scattered marks #

The prediction said the marks would not move, since every chunk there is an Elias–Fano list of about two scanned bits a value and the earlier essay found every one choosing the same spacing. They move. At a rate of 0.01 the path takes twice the per-chunk spacing on 78% of the values and reads 60.4 bits for 7.398 bits a value, against the per-chunk spacing’s 57.8 for 7.436; at 0.003, 61.0 for 7.389.

The prediction confused two senses of right. One density has one spacing that makes the steps one, and the earlier essay found it. It does not have one spacing that is worth its bits, because how much a step is worth depends on the rate, and at most rates a spacing twice as wide is a better trade than the one that makes steps one. On the marks the priced points sit just off the earlier frontier rather than under it — the fixed spacing of 64 already read 60.9 for 7.391 — so the rate there rediscovers a point and does not improve on it.

The model the path paid #

Every choice above was made against a model of reads, and the plate checks it. Across every set and rate the replay reads about a tenth less inside the chunk than the model expected, and never more; the largest gap is about nine bits, on divergence 0.01 at the lowest rate. The model’s average of the steps a select takes runs high, and it runs high uniformly enough that the choices it drives are the choices a replayed price would drive, give or take the boundary cases.

The boundary cases are where the curve turned back. At a rate of 0.03 on exact copies the path cut eleven chunks and put 12% of values in chunks without a directory, on the model’s account of what those chunks would read; the replay reads 62.5 bits, more than the per-chunk spacing’s 54.8 with more bits stored, so the point is dominated. A price paid on a model is a price paid on the model’s errors, and those land somewhere; here they land at the rate where the path begins to trade directories for chunks.

Every set at sixty bits #

The headline comparison is the one a second level that pays in one band used: at a fixed budget of reads, how few bits. At 60 bits read the priced path lowers the fewest bits on five of the eight sets: exact copies from 3.875 to 3.824, divergence 0.0005 from 5.721 to 5.640, divergence 0.001 from 6.360 to 6.240, divergence 0.005 from 7.158 to 7.079, divergence 0.01 from 6.520 to 6.489. On the marks, divergence 0.0002 and divergence 0.002 it changes nothing. At 70 bits read it helps on two sets, by a hundredth on divergence 0.0005 and by 0.28 bits a value on divergence 0.01, where 6.520 becomes 6.238.

That is the second level’s band widened again, in the direction the earlier essay found it widening: downward, toward fewer reads. On the five divergent sets, where earlier directories could not read under 50 bits at all, the priced path’s high-rate points are the only ones that do — at seven bits a value or so, which is the price of scanning many short chunks.

The strand’s directories, priced #

Read through the rate, every directory this strand has built is a point some price would choose. A select that starts near its answer put select samples alone in each chunk, which is the right directory when reads are dear and bits are cheap: at 43 bits read on exact copies it is still the best thing measured. A sample that has to be found put rank samples alone, which bounds the scan but must be searched for, and still holds its own stretch of the frontier on exact copies, around 77 bits read. The two-level directory with a fixed spacing is the rate of a few thousandths, and the per-chunk spacing the rate of about a fiftieth.

That reading has a practical side. A structure that stores the run starts does not have to choose its directory once and for all; it can be built at a rate, and the rate is a statement about the machine it runs on and the workload it serves — how dear a bit read is against a bit stored, which is a question about caches and queries rather than about the set. The essays before this one each chose a directory and measured it; the price is the instrument that says which one a given machine should have chosen.

It is also an instrument with a limit the plates make plain. The rate can only choose among the directories it is offered, and at the top of its range it chose many small chunks because the plain select samples were not on its menu. A complete price would offer every directory the strand has measured to every chunk and let the rate choose among all of them.

What the rate is a price of #

The question the earlier essay left was whether a directory can be fitted to a rate of exchange between storage and reading, or whether the rate itself depends on which values are asked for. The plates answer the first half: it can, and the fitting is worth a few hundredths of a bit a value at a fixed budget of reads on most sets, a quarter of a bit on one, and nothing on three.

They do not answer the second half, because every select here is uniform over the values. The risk the proposal named is untouched: in an r-index the selects follow the matches of the patterns being located, and a chunk holding the run starts of a common pattern is asked far more often than its share of values. A rate charged per value, as here, is a rate for a workload that asks every value equally. Every occurrence at the same price and the sampling that follows the runs built the parts of the r-index that issue these selects, and neither said anything about which values they ask for.

What the plates add is a correction to how the earlier essays read their own spacing rule. A select sample spaced so that its values span one block is not the right spacing; it is the right spacing at a rate of about a fiftieth of a bit stored for every bit read. Below that rate wider is better, above it narrower — until the price begins to choose the chunks instead, which is where the path’s own options run out.

What the replays do not cover #

Uniform selects. Every select is equally likely to ask for any value, in the model and the replay alike.

Three spacings a chunk. The path chooses among $t_0$, $2t_0$ and $4t_0$, as proposed. Half the per-chunk spacing was not offered, and at the higher rates the choices pile up at $t_0$, so it might have been taken.

One rank width at a time. Each run fixes $s$ at 64 or 128 for every chunk; a path that chose the rank width per chunk as well was not run.

The read model. The path is charged a model; every reported read is replayed. The model’s errors are measured above, and they are a tenth of the reads, never in the cheap direction.

Still open: a rate for the values that are asked #

Every price here assumes that each value of the set is selected equally often, and the proposal’s own risk said that is not how an r-index asks. When a pattern is located, the run-start values it selects are those of its own matches’ runs, and a frequent pattern asks for the same values again and again.

The measurement that follows draws selects from a workload of patterns over the collection’s text — the run starts each pattern’s locating actually selects — weights each value by how often it is asked, and charges each chunk its stored bits plus the rate times its reads weighted by that workload, beside the uniform price here. The prediction is that on exact copies the weighted price puts denser select samples in the few chunks holding the common patterns’ run starts and sparser ones elsewhere, reaching about 3.80 bits a value for 55 bits read on that workload, and that a directory priced uniformly reads about a tenth more on it than it does on uniform selects. It could fail if the asked values are spread across every chunk, so that weighting changes no chunk’s choice, which on exact copies, where every copy’s run starts are interleaved, is likely. The question is whether a directory can be fitted to its workload as well as to its set, or whether on a repetitive collection every chunk is asked about equally after all.