A second level that pays in one band

An r-index locates its matches through the positions where the runs of its Burrows–Wheeler transform start, a sorted set of a few hundred to a few thousand values over a text of sixty-five thousand characters, and cuts that follow the gathering stored that set as a partition: chunks of consecutive values, each coded as a plain bitmap, an Elias–Fano list or a run, cut where a shortest path over every possible cut says the total bits are least. On copies of one text the run starts gather in a few dense stretches, and the cheapest partition put most of them in one large bitmap chunk. Every select into that chunk — find the $j$-th value — scanned the bitmap from its start: 1,065 bits read a select, against 33 for a single Elias–Fano list over the whole set.

The essays since have given the chunks directories. A select that starts near its answer put a select sample every $t$ values inside each chunk, the bit position of every $t$-th value, so a select jumps to the sample before its value and scans from there: every 64 values, 111 bits read a select for 3.45 bits a value. A sample that has to be found tried rank samples instead, the count of values before every $s$-th bit, which bound the scan to $s$ bits but have to be searched for, and found the two kinds drew one frontier with rank samples coming in finer steps.

Its closing section saw that each kind removes one of a select’s two kinds of ignorance. A select sample knows which stretch to start in and not how far to scan; a rank sample bounds the scan and does not know where it is. A two-level directory gives a select both: a select sample every $t$ values that holds not a bit position but the number of the rank block containing its value, and rank samples every $s$ bits. A select reads its select sample by arithmetic, which names a block near its target; steps forward through the rank samples until the count passes its rank, usually one or two of them, it said; and scans at most $s$ bits. The prediction was under 70 bits read a select for under 3.6 bits a value on exact copies, and under 70 for about 6.2 at a divergence of 0.01, points neither kind reaches. The named risk was the second level’s bits in chunks only moderately long, where the path might cut those chunks instead and leave the frontier where it was.

Both levels, charged in the path #

The sets, partition and charges are the earlier essays’. A select is charged the bits it reads: the upper level that finds its chunk, then inside the chunk the directory and the scan. Under the two-level directory a chunk whose scanned vector — its bitmap, or its Elias–Fano high part — is $L$ bits long holds $\lfloor (L-1)/s \rfloor$ rank samples, each as wide as the chunk’s count of values needs, and a select sample every $t$ values, each wide enough to name a rank block. A select for the $j$-th value reads the select sample before it, which names the block $b_0$ holding that sampled value; reads the rank samples after $b_0$ one by one until one counts past $j$; and scans from the start of the block it has found to its value’s bit. Those bits are charged in the shortest path, so the partition is chosen with both levels’ price in view.

The directory was run at every combination of $t$ = 64, 128, 256 values and $s$ = 64, 128, 256 bits, on eight sets: exact copies of one text, copies at six divergences from 0.0002 to 0.01, and scattered marks with no gathering at all.

A point neither kind reaches, and not the one predicted #

On exact copies the two-level directory reaches 62 bits read a select for 3.76 bits a value, with a select sample every 64 values naming a rank block and rank samples every 64 bits, and within a budget of 70 bits read it costs 3.734 bits a value where the better single kind costs 3.929; outside about 65 to 100 bits read it lands on the single kinds’ frontier. Under 70 bits read, only select samples every sixteen values compete, at 3.93 bits a value, and rank samples cannot get there at all: their finest setting, every 64 bits, reads 77. The two-level directory fills that gap, a fifth of a bit a value cheaper than the only thing that reaches it.

But the prediction asked for both halves at once — under 70 bits read and under 3.6 bits a value — and no setting gives them. Under 3.6 bits a value the two-level directory’s cheapest read is 84 bits, at $t = 64$ and $s = 128$, where rank samples every 128 bits read 98 for 3.51. From about a hundred bits read upward, rank samples alone are as good: within 100 bits the two-level directory costs 3.517 and rank samples 3.511. The second level found a point, 62 bits for 3.76, that nothing else offered; it did not find the point it was designed for.

Two steps, not one #

With a select sample every 64 values and rank samples every 64 bits, a select on exact copies reads 2.50 bits of select sample, 17.12 of rank samples — 2.21 of them stepped, not the one or two predicted — and 31.85 in its block; across the sets the rank samples stepped are 1.15 to 2.21 a select. The block scan is what the rank samples promise: at most 64 bits, 32 on average. The select sample is nearly free, two or three bits read once. The stepping is not: a select whose value is among its chunk’s first 64 has no select sample to read and starts at block nought, and every other select starts at the block of a value up to 63 places before its own.

Between that block and the target’s lie as many rank blocks as those values span, and the 2.21 steps a select measured on exact copies say that 64 values of these chunks span two or three blocks of 64 bits. The prediction’s “one or two” assumed a select sample would land in or next to the target’s block, which needs $t$ values to span about one block of $s$ bits, and on dense chunks they span several.

Spacing against steps #

On exact copies a select steps through 2.21 rank samples with a select sample every 64 values and rank samples every 64 bits, and 6.25 with select samples every 256 values: the farther apart the select samples, the more rank blocks lie between a sample’s value and the target, so the steps grow with $t$ and shrink as $s$ widens the blocks. A step reads one rank sample, about eight bits wide on these chunks, so at $t = 256$ and $s = 64$ the stepping costs 50 bits a select, more than the block scan it was meant to save. The directory’s two parameters are not independent: the stepping is set by how many rank blocks $t$ values span, which is $t$ times the chunk’s bits per value over $s$, and the chunks’ density decides it.

That ratio is what the proposal fixed without measuring. A two-level directory steps once when a select sample’s $t$ values span one rank block, which on a chunk with $d$ bits a value means $t \cdot d \approx s$. On the dense bitmap chunks of exact copies $d$ is about four or five bits, and $t = 64$ needs $s$ near 256 to step once — where the block scan is 128 bits on average and the total reads 143. The settings that make the stepping cheap make the scan dear, and the ones that make the scan cheap make the stepping dear. A select sample spaced by bits rather than by values would hold the ratio fixed, but that is a rank sample, and the directory would be one level again.

The other sets #

At a divergence of 0.01 the two-level directory reaches 74 bits read a select for 6.21 bits a value, and within a budget of 100 bits read it costs 6.050 bits a value where the better single kind costs 6.178; under 70 bits read it reaches nothing, where select samples every sixteen values read 55. The prediction there was under 70 for about 6.2, and the directory’s cheapest read misses it by four bits; at 80 bits read rank samples alone are as good, 6.178 against 6.186. At this divergence the run starts are spread over many small chunks, few chunks are long enough to carry select samples, and a two-level select is a rank-sample select that steps from the chunk’s first block instead of searching.

The second level pays only inside a narrow band of reads: within 70 or 90 bits read a select, the two-level directory saves three of eight sets more than a twentieth of a bit a value over the better single kind — the scattered marks 0.49, exact copies 0.20, divergence 0.005 0.10 — and on the rest it saves nothing, or cannot read that little at all. The scattered marks are the surprise. They have no gathering, the partition puts them in a dozen chunks of a few hundred values, and there a select steps through 1.57 rank samples on average, close to the one the design wants; why the marks’ chunks step less than the copies’ was not separated, since their forms were not counted apart. The directory reads 61 bits a select there for 7.39 bits a value, where the cheapest single kind within 70 bits costs 7.86.

What one more level buys #

The closing question of the earlier essay was whether a select’s two kinds of ignorance can each be removed by the directory built for it, or whether the cheapest directory is always one of them, chosen by where the long chunks are. The answer here is narrower than either. Two levels remove both kinds of ignorance only where the select samples’ spacing in values matches the rank samples’ spacing in bits, and on the dense chunks that matter most they do not match. In a band of reads around 60 to 100 bits a select, on the sets with long chunks, the two-level directory offers points neither kind alone reaches, a fifth to a half of a bit a value cheaper. Outside that band, or on sets of many short chunks, the cheapest directory is one of the two.

Where the sparse representation loses and sparse on average, dense where it gathers found the same structure in the partition itself: what is cheapest depends on the density of each stretch, not on the set’s average density. A directory is the same question one level down.

What the directory is made of #

The two-level directory is cheap in bits because each of its levels is small. A rank sample on these chunks is about eight bits, the count of values before its block within a chunk of a few hundred values; a select sample is two to four bits, the number of a rank block within its chunk. At rank samples every 64 bits and select samples every 64 values, the directory adds about half a bit a value on exact copies — the difference between 3.27 bits a value with no directory and 3.76 with both levels, partition included — and of that the select samples are a small part. The rank samples are what costs, and they are what the reads at small budgets need.

The comparison with rank samples alone then comes down to one question: is it cheaper to binary-search the rank samples or to step through them from a block the select sample names? A binary search over $E$ samples reads about $\log_2 (E+1)$ of them; stepping reads as many as there are blocks between the select sample’s value and the target. On a chunk with a few dozen rank blocks the search reads five or six, and stepping from a select sample every 64 values reads two or three, which is the band where the second level pays. The band is therefore set by a count of blocks, not by a count of bits read, and a collection whose long chunks held more or fewer rank blocks would move it: fewer blocks shrink the binary search until stepping has nothing to save, and more lengthen the steps until the search is cheaper again. Exact copies sit near the middle of that range, which is why they show the largest saving among the gathered sets. On short chunks with few blocks the search is already short, and on long sparse chunks the select samples span many blocks and stepping is long. A position split in two made the same kind of trade inside Elias–Fano itself, a cheap upper part read by arithmetic and a lower part read directly, and found it paid exactly where the two parts’ sizes were balanced.

What the locating apparatus becomes weighed this whole structure against the r-index it serves. Its run-start values are one of several sampled arrays the index holds, and a fifth of a bit a value on a few hundred run starts is a few dozen bits; whether the select reads matter more depends on how often the index locates, which the bits-a-value axis cannot show.

What the model does not count #

Reads, not time. Every cost is bits read, a model in which a scanned bit and a sampled bit cost the same. The count is not the time is the standing warning: a rank sample read at an arbitrary address may cost a cache miss where a sequential scan of 64 bits costs nothing extra, and on a real machine the stepping would be dearer than this model says and the scan cheaper.

One text, copied. The sets are copies of one text at several divergences, and scattered marks. A collection whose long chunks had a different density would move the band where the second level pays.

Nine settings. Three values of each spacing. The ratio that sets the stepping suggests settings between them — $s$ = 192, or $t$ = 48 — none of which was run.

Still open: a select sample spaced by bits #

The steps come from the select samples’ spacing being counted in values while the rank blocks are counted in bits, so that the number of blocks between a sample and its target depends on each chunk’s density. A directory could space its select samples per chunk, choosing for each chunk the $t$ that makes $t$ values span about one rank block — $t \approx s/d$ for a chunk of $d$ bits a value — and charge the choice in the path as before.

The measurement that follows gives each chunk its own $t$, from 8 to 512 values, set to the nearest power of two to $s/d$, at $s$ = 64, 128 and 256, on all eight sets. The prediction is that the steps fall to about one a select on every set, that on exact copies the directory then reads under 70 bits a select for under 3.65 bits a value, and that the band where two levels pay widens to about 120 bits read. It could fail on the select samples’ own bits: a chunk dense enough to need $t = 8$ carries a select sample every eight values, each several bits wide, and that may cost more than the steps it saves. The question is whether a select’s two directories can be matched to each other chunk by chunk, or whether matching them only moves the cost from the stepping to the samples.