Cuts that follow the gathering

Sparse on average, dense where it gathers built the hybrid that twenty bits apart had described and never needed. The index that stores the runs keeps one suffix-array value for every run of its transform, and on a collection of drifted copies those values are few overall and crowded where the copies differ. Priced as one Elias–Fano over the whole text, they cost about nine bits each, as though they were spread evenly. Cut into chunks of a fixed number of values, each chunk held as whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set cost half as much on exact copies and a fifth less at a divergence of one character in two thousand.

No single chunk size suited every set. Thirty-two values was best on exact copies and at small divergences; at one character in five hundred, only chunks of 512 beat the single Elias–Fano at all. Even the best fixed count put chunk boundaries inside the dense places and let chunks straddle their edges. The closing section proposed choosing the cuts instead. A partition’s cost is the sum, over its chunks, of each chunk’s cheapest form plus the upper level’s charge for one more chunk, so the cheapest partition is a shortest path through the sorted values. It predicted a further 10% on exact copies, from cutting once at each edge of the dense block; 10% to 15% at 0.0005, where the gatherings vary in size; and nearly nothing on the scattered marks of an ordinary index. And it named how the prediction could fail: the cheapest partition might have very few chunks, some of them huge, which a select would have to scan.

The prediction and the named failure both came true, on the same set.

The cheapest partition as a path #

Number the sorted values $v_0 < v_1 < \dots < v_{m-1}$, and give each index $i$ from 0 to $m$ a vertex. An edge from $i$ to $j$ is a chunk holding values $v_i$ to $v_{j-1}$ over the positions after $v_{i-1}$ up to $v_{j-1}$, and its weight is the bits of the chunk’s cheapest form plus a constant $F$ for its share of the upper level. A path from 0 to $m$ is a partition, its weight is the partition’s cost, and the shortest path is found in one pass. For each $j$ in order, every $i$ before it is tried and the cheapest arrival kept, exactly the relaxation a distance that is a path through a grid performed on an edit table. A cap on the values a chunk may hold is a window on $i$, and the capped optimum is exact for its cap.

The upper level does not charge a true constant. It holds the chunks’ last values as an Elias–Fano over the whole text, whose width depends on how many chunks there are, plus a two-bit form tag and a pointer for each. So $F$ starts from a guess, the path is solved, the partition it finds is charged in full by the same accounting the fixed chunks received, $F$ is re-estimated from that partition’s real upper level, and the path is solved again. On exact copies $F$ moves from 28 bits to 44.5 and the partition does not change. Four rounds are run on every set, and the partition with the smallest real total is kept. Every partition is decoded back to the set it claims to hold before its size is reported, as before.

Two chunks for exact copies #

On exact copies the cheapest partition is two chunks: a bitmap of 664 values over the 2,055 positions where nearly all of them gather, and an Elias–Fano chunk holding the other two. The cuts fall at the edges of the dense block, which is what the prediction said they would do. The 21 chunks of 32 values put twenty boundaries inside that block, each paying an upper-level entry for nothing, since every one of those chunks chose the same form as its neighbours.

The block is where it is for the reason the earlier essay gave. In a collection of exact copies the 32 suffixes that begin at one offset agree until the shortest runs out, so they sort together with the last copy’s first, and nearly every run of the transform begins at a suffix of the last copy. The other thirty-one copies hold five of the 666 values between them, mostly at their ends. A bitmap of 2,055 bits holding 664 ones is about three bits a value. Elias–Fano over the same stretch would need two bits plus the logarithm of the gap, also about three bits plus its upper part, so the bitmap wins by a little, and the chunk can be as long as the block.

That partition costs 2,178 bits, 3.27 a value, against 2,983 for chunks of 32: a saving of 27%, not the 10% predicted. The prediction underestimated how much the fixed chunks were paying for their boundaries. Nineteen fewer upper-level entries at about 45 bits each are some 850 bits, about the whole difference of 805.

Uneven chunks where the copies drift #

At a divergence of 0.0005 the cheapest partition has 30 chunks, nearly the same number as chunks of 32 make, and none of them is the same chunk. Fifteen are bitmaps laid over the places the values gather, from 11 values over 30 positions to 212 over 680. Fifteen are Elias–Fano chunks over the gaps between, and several hold a single value over hundreds of positions. The chunk count is close to the fixed partition’s by coincidence. What differs is where the boundaries are. Every cut of the optimum sits at an edge between a gathering and the sparse stretch around it, and every gathering is held whole.

A drifted copy differs from the first at a few scattered positions, and each difference starts new runs in the transform for the suffixes that run through it. So the values gather in small clusters near each difference, of different sizes depending on how many suffixes each difference separates. A fixed count can be right for one cluster size only. This partition costs 4,744 bits, 5.29 a value, against 6,073 for chunks of 32: a saving of 22%, above the 10% to 15% predicted. The prediction’s reasoning was right, since the clusters do vary in size and the optimum fits each one. Its size was low for the same reason as on exact copies: the boundaries the fixed chunks put in the wrong places were more expensive than the prediction priced them.

Under every fixed chunk at every divergence #

The cheapest partition is under every fixed chunk at every divergence, and at 0.002, where chunks of 32 cost more than the single Elias–Fano, it costs 6.65 bits a value against Elias–Fano’s 7.86 and the floor’s 6.91. The fixed chunks had lost their advantage by one character in five hundred, because the clusters there are too small and too many for 32 values to fit any of them, and the larger chunks that did beat Elias–Fano did so by holding the sparse stretches too. The optimum makes 59 chunks with a median of 20 values. It is under the floor for an arbitrary set of that size, which is possible only because the set is not arbitrary, as the earlier essay’s floor plate argued. The fixed chunks never got there at this divergence.

The advantage narrows as the copies drift further. At 0.005 the optimum is 6.65 bits a value against the best fixed chunk’s 6.78, and at 0.01 it is 5.92 against 6.00, both above the floor. The clusters have merged into a spread that is nearly even, and an even spread is the case one Elias–Fano was built for; what a partition still saves there is mostly the select directory, which a chunk small enough to scan does without. Where the sparse representation loses put the crossing between Elias–Fano and a plain vector at one marked position in four; an even spread of one value in sixteen is far on Elias–Fano’s side of it, which is why a partition has little left to choose there. The prediction said the optimum would save nearly nothing on the marks. It saves 0.8% against their best fixed chunk, chunks of 512, and that is nearly nothing.

What the cheapest partition costs to read #

The bits are only half the account, which every occurrence at the same price found of the sampling these values serve: a structure’s size and its cost a query move together, and quoting one of them alone settles nothing. A select asks for the $j$-th value. Through one Elias–Fano it reaches a 64-bit block of the high vector by its directory and scans that block, 32.6 bits on average on every set here. Through a partition it does the same on the upper level to find the chunk, then scans the chunk: an Elias–Fano chunk’s high part up to the target one, a bitmap chunk up to the target bit, a run not at all. It is a model of the bits read, the one the earlier essay used, not a timing.

On exact copies the uncapped optimum’s select reads 1,065 bits, a third of its whole size and 33 times what one Elias–Fano reads. That is the failure the prediction named. A bitmap of 2,055 bits holding nearly every value is scanned from its start to the target bit, and on average that is half the bitmap. The partition that minimises space has made the set’s commonest query the slowest it has been since the plain bit vector.

The capped optimum fixes it without giving up the partition. Capped at 32 values a chunk, the cheapest partition costs 4.08 bits a value and reads 92.6 bits a select, against 4.48 and 92.9 for chunks of 32. Its chunks are the same size as before and its reads the same, but the cuts are placed rather than counted, and it is 9% smaller. Capped at 64 it is 18% smaller and reads 116 bits. The prediction’s 10% was the saving at the reads chunks of 32 already paid. The saving past that is paid for in reads, at a rate the frontier makes plain: each doubling of the cap halves what is left to save and roughly doubles the scan. From chunks of 32 upward the fixed chunks sit on a worse curve throughout, so at every read budget there is a capped optimum smaller than the fixed chunk that reads as much. Below that budget only small fixed chunks reach, 41 bits read for chunks of 8 at 6.52 bits a value, and a cap under 32 would be needed to follow them there.

At 0.002 the uncapped optimum reads 83 bits a select, less than the 589 that chunks of 512 read, and is 11% smaller than they are. No cap is needed here. The clusters at this divergence are small, the optimum’s largest chunk holds 100 values, and caps of 128 and above leave it unchanged. Capped at 32 it reads less than chunks of 32 do, 60.7 bits against 69.5, because its Elias–Fano chunks over the sparse stretches hold few values and its bitmaps over the clusters are short. The cuts that minimise space on this set are cuts a select can afford, and the closing section’s question has two answers depending on the set.

The cap is a price, set by the set #

Capped at 32 values a chunk, the cheapest partition saves 9% on exact copies, 15% at 0.0005 and 14% at 0.002 against chunks of 32, at the same or fewer bits read. Most of the partition’s advantage on drifted copies survives the tightest cap. On exact copies most of it does not, because the advantage there was holding one gathering in one chunk, and a cap forbids exactly that.

The marks’ row needs reading with care. The saving against chunks of 32 rises to 11% with no cap, but chunks of 32 were never the right size for a scattered set. Against the marks’ best fixed chunk, 512 values, the optimum saves 0.8%, and it does so with two chunks whose select reads 1,371 bits. On a set with no gathering, there is no edge for a cut to find, and the shortest path simply prefers fewer upper-level entries, which is a reason to cap it and not a reason to use it.

How large the chunks come out #

The optimum’s chunk sizes track the gatherings: one chunk of 664 values on exact copies, a median of 17 to 20 values from 0.0005 to 0.002, and at the two ends, exact copies and 0.01, a few chunks of hundreds or a thousand. It is the shape of the set read off its cheapest description. Where the values gather in a few large clusters the chunks are large, where they gather in many small ones the chunks are small, and where they stop gathering at all the cheapest description has few chunks again, because the upper level’s charge is all that varies.

That curve explains when a cap is needed. The middle divergences are where the optimum is both small and readable, since their clusters are many and short. At the two ends the cheapest partition is a handful of very large chunks and a select pays for them. It is the same trade the flat bottom of a shallow curve found in a single Elias–Fano’s width, at one level up: near the optimum the total barely moves while the parts trade places, so a constraint that moves the solution a long way costs almost nothing in bits.

What the prediction got right #

The closing section predicted a further 10% on exact copies from cutting once at each edge of the dense block. The cheapest partition cuts once at each edge and saves 27%, and capped at the fixed chunk’s size it saves 9%. It predicted 10% to 15% at 0.0005; the optimum saves 22%, and 15% capped at 32. It predicted nearly nothing on the marks, and the optimum saves 0.8% against their best fixed chunk.

It named the risk precisely: a few enormous chunks that a select must scan, making the structure smaller and slower. On exact copies that happened, with a select reading 1,065 bits against Elias–Fano’s 33. At 0.0005 it happened mildly, 175 bits. At 0.001 and 0.002 it did not happen at all, since the optimum’s largest chunk was 100 to 117 values. The closing section’s question was whether the cuts that minimise space are cuts a select can afford, or whether a partition has to be priced in reads before its optimum means anything. Measured, the answer is that it has to be priced in reads, and that the price is cheap where the hybrid is most useful. The cap is one more parameter, but unlike the fixed count it does not have to be fitted to the set. A cap of 32 or 64 values is safe on every set here, and the path finds the best cuts beneath it.

What these sets do not settle #

One collection. Thirty-two copies of 2,048 characters of English, drifted by independent substitutions. The collection decides which index is small found a repetition alone could reverse the order of three indexes, and the same caution applies to a partition fitted to one kind of drift. A collection whose copies differ by long insertions or by blocks moved would gather its values into fewer, larger clusters, and the optimum would make longer chunks that need the cap more.

A model of reads. The select’s cost is the bits scanned after its directory lookups. Scanning a bitmap is a word at a time with a population count, and scanning an Elias–Fano chunk’s high part is similar, so bits read are a fair proxy within one representation and a rough one across them. Nothing was timed.

The path’s charge. The upper level’s cost is approximated by a constant per chunk, re-estimated four times. A partition that was cheapest under the real, non-constant charge could in principle differ from the one found. On exact copies the estimate settled in one round and the partition did not move, and on the others the kept partition’s total is charged in full by the same accounting as the fixed chunks.

Still open: a select that starts from where it was asked #

The cap exists because a select scans its chunk from the chunk’s start, and a long bitmap chunk makes that scan long. But a bitmap chunk of 2,055 bits could carry its own small directory, one count every 256 bits, eight entries of eleven bits, so that a select jumps to the right block and scans only that block. That is a second level of the same structure inside the largest chunks only, and the upper level already knows which chunks are large.

The measurement that follows gives every chunk longer than a threshold a sampled rank directory at one entry per $s$ bits, charges its bits in the path so that the optimum can choose to pay for it, and draws the frontier of bits against reads again, uncapped, on every set. The prediction is that on exact copies the uncapped optimum, with directories inside its one large bitmap, reads under 150 bits a select for under 3.5 bits a value, which no capped partition achieves. On the middle divergences it should change nothing, since their chunks are already short. The question is whether a cap on chunk length is the right way to buy back reads, or whether a cheapest partition should be allowed to make its chunks as long as the set wants and carry its own way into each one.