Sparse on average, dense where it gathers

Twenty bits apart ended the long account of the sampled marks with a rule for any sparse bit vector. A plain vector assumes nothing and costs one bit a position. Elias–Fano assumes the ones are few and costs about two bits plus the logarithm of the average gap for each one. Compressed blocks assume the bits are locally uniform and cost the entropy of each block’s count. Two numbers measured in one pass, the density and the entropy of the block classes, choose among the three. And a vector that satisfied both assumptions at once, few ones and those few gathered together, should be held by a hybrid that used each where it applied. The marks satisfied only the first, because the transform scatters them, so the hybrid was never built.

A vector that satisfies both exists, and it sits inside the structure that made the marks unnecessary. Every occurrence at the same price replaced the regular sampling with the r-index’s: a suffix-array value at the first and the last row of every run of the transform, and a function, phi, that turns one occurrence into all of them with one predecessor query. The predecessor query is over a set — the values at the run starts, in text order — and the r-index prices that set as Elias–Fano. For each value it charges a low part of ⌈log₂(n/r)⌉ bits and two bits of high part, as if r values were spread evenly over n positions.

What the run-start values look like #

On a collection of 32 exact copies, 661 of the 666 run-start values lie in the last copy, where they are about one position in three; the other thirty-one copies hold five between them, four of those at the end of the copy before it. The reason is the sort. In a collection of exact copies the 32 suffixes that begin at the same offset in every copy agree character for character until the shortest of them runs out, so they sort next to each other, and the shortest sorts first — the one in the last copy, which reaches the end of the text soonest. They are preceded by the same character, so a run of the transform can start only at the edge of such a group, and the first row of a group is its last-copy suffix. The value recorded at a run start is that suffix’s position, and so it is in the last copy almost every time. The four in the copy before it are among its last eight characters, and the one in the first copy is position nought, the first character of the text. So the set is sparse on average, one value in a hundred positions, and almost entirely a dense block of 2,048 positions with a long empty stretch before it.

That is the shape Elias–Fano is wrong about. Its low width is chosen from the average gap — here ⌊log₂(65,537/666)⌋ = 6, and the flat bottom of a shallow curve found the choice is close to optimal for a set whose gaps are near their average. This set’s gaps are of two kinds, a few of about three positions and a few enormous ones, and none near the average of 98. Every value in the dense block is charged a low part of six bits to say where it sits within a gap that is actually two or three positions wide.

Copies that are not exact spread the run-start values out. Each replaced character makes the suffixes around it differ from their twins in the other copies, which starts new runs, and the values at those run starts are positions near the change. At a divergence of 0.0005, where each character of each later copy is replaced with chance one in two thousand, the run-start values are 896, a copy holds anything from none to 230, and within a copy they gather around the changes, as the plate at the head of the page shows. Gathered still, but now in many places rather than one.

Four ways to hold one set #

Partitioned, the run-start values of exact copies cost 4.48 bits a value against Elias–Fano’s 9.04, half as much, and under the floor of 8.05 bits a value that any representation of an arbitrary set of 666 values among 65,537 positions must spend on some set. At a divergence of 0.0005 the partition costs 6.78 against 8.56, a saving of a fifth, and is still under that set’s floor of 7.62. At 0.002 it costs 7.49 against 7.86, and the floor is 6.91. On the marks it costs 7.06 against 7.57 and the floor is 6.42.

The partitioned form is the one published as partitioned Elias–Fano, with chunks of a fixed count rather than an optimal partition. The values, sorted, are cut into chunks of k consecutive values. Each chunk covers the positions after the previous chunk’s last value up to its own last value, a local universe of u positions, and holds its k values in whichever of three forms is cheapest for that chunk alone: Elias–Fano over the local universe, k·w + k + ⌊u/2^w⌋ + 1 bits with w chosen from that chunk’s own density; a plain bitmap of u bits; or nothing at all, when the chunk’s k values are k consecutive positions. An upper level finds the right chunk for a query. It holds the chunks’ last values as an Elias–Fano over the whole universe, with its select directory, and for each chunk a two-bit tag naming its form and a pointer to where its bits begin. Every size on the plate includes that upper level.

Going under the floor is not a contradiction, and it is the point of the page. The floor log₂ C(n, m) counts how many sets of m values among n positions there are and says that some of them must cost that many bits under any representation. It is a statement about the hardest set, and a representation that adapts to a set’s shape pays for its adaptability by costing more than the floor on sets of no shape — the marks, where the partition is above the floor at every chunk size. The run-start values have a shape, and the floor is a price for not having one. A price with no structure under it found the collection charging Elias–Fano’s price for a structure it had not built; this is the converse, a structure built and charged a price set for a different kind of set.

Compressed blocks, the representation the earlier pages found close to Elias–Fano on the marks, do worse on the run-start values than either: 13.50 bits a value on exact copies. They charge every block of 63 positions its class and directory whether or not it holds anything, and on a set with one value in a hundred positions that is a charge on nearly empty blocks across the whole universe. The dense block they would compress well is three per cent of it.

Where each chunk takes which form #

At a divergence of 0.0005, cut into chunks of 32, twelve chunks are dense enough to be bitmaps and hold 43% of the values in under 2% of the positions; the other sixteen spread over the remaining 64,324 positions, each with its own Elias–Fano. The bitmaps are the gatherings. A chunk of 32 values covering about a hundred positions — one value in three — costs about a hundred bits as a bitmap, three bits a value, where its own Elias–Fano would need a low width of one and about three and a half bits a value, and the global structure charges it eight and a half.

The sixteen Elias–Fano chunks are where the saving is more subtle. Each one prices its values at the density of its own universe, and the universes vary from 131 positions to 12,476. A chunk over 434 positions holding 32 values gets a low width of 3; a chunk over 12,476 gets 8. The global structure gives every value a low width of 6. Where the values are tighter than average the chunk spends less, and where they are looser it spends more, which is the right direction both times: a value is charged for the information needed to place it among its neighbours, not among all the positions.

What it costs to choose is on the plate’s own arithmetic. The upper level is 821 bits — an Elias–Fano of the 28 chunks’ last values, a two-bit tag and a thirteen-bit pointer for each — against 5,252 for the chunks themselves. That 821 bits is 13% of the total, and it is the price of being able to treat each region of the set by its own density. On this set it is repaid twice over.

No chunk size fits every set #

The run-start values of exact copies are cheapest in chunks of 32 or 64 values, 4.48 bits a value, and cost 7.68 in chunks of 512; the marks are cheapest in chunks of 512, 7.06, and cost 10.26 in chunks of 8. A chunk size is a statement about how far apart the set’s changes of density are, and the four sets disagree.

The two ends of each curve are the two ways a fixed partition can fail. With chunks too small the upper level dominates, because every chunk pays its tag, its pointer and an upper-level value whatever it holds: at chunks of 8 that is about 30 bits for every 8 values, nearly four bits a value before any value is stored. With chunks too large a chunk straddles a gathering and the gap beside it, and the density it prices is an average of the two — the global structure’s mistake again, made on a smaller scale. At 512 values a chunk of the exact copies’ run-start values holds the whole dense block and most of the empty stretch with it, and is back to 7.68 bits a value.

On the marks the curve has no interior minimum within the range drawn. They have no gatherings to resolve, so a smaller chunk buys nothing but upper-level overhead, and the larger the chunk the closer the partition comes to a single Elias–Fano without its directory. At 512 the partitioned marks are under the single Elias–Fano’s 7.57 bits a value only because the single structure carries a select directory over its whole high vector, 1,162 bits, and the chunks carry none. Without that directory the single Elias–Fano is 7.00, under every partition. On the marks the partition saves nothing but a directory, and the plate after next prices what a missing directory costs.

How fast the advantage goes #

The partitioned run-start values stay under the floor for an arbitrary set until the copies diverge by about one character in a thousand: 4.48, 5.97, 6.78 and 7.28 bits a value against floors of 8.05, 7.88, 7.62 and 7.41. From 0.002 they are over it, 7.49 against 6.91, and the saving over Elias–Fano falls to what its select directory accounts for. At 0.002 the single Elias–Fano without its directory is 10,791 bits and the best partition 10,917; at 0.005, 15,982 and 16,108; at 0.01, 24,769 and 24,849. On those sets the chunks’ only advantage is that they carry no directory, which is a saving bought by reading more, not by fitting the set better.

The best chunk size moves with the divergence in the same way: 32 values up to 0.001, then 512 from 0.002. That jump is a change in what the set is. Under one replaced character in a thousand, each change of a later copy is far from the next, the run-start values it starts sit together near it, and a chunk of 32 resolves one gathering. Over one in five hundred, changes in a copy of 2,048 characters come every few hundred positions, their gatherings overlap, and the run-start values approach the scattered shape of the marks. The partition has nothing to resolve and the best it can do is be one large chunk.

At a divergence of 0.01 the compressed blocks reach 5.88 bits a value and beat both, the first time on this page they win. By then the run-start values are 4,144 among 65,537 positions — one in sixteen, the density at which twenty bits apart found Elias–Fano and the blocks pricing the marks identically — and the blocks’ assumption, that the bits are locally uniform, has become true. A collection that diverges this much is less repetitive, and the collection decides which index is small found that how much a collection repeats decides which index is smallest; the predecessor set losing its shape is the same fact one level down.

What the chunks read instead #

On the run-start values of exact copies, chunks of 16 hold the set in 5.10 bits a value — 56% of the single Elias–Fano’s 9.04 — for 49 bits read by an average select, against 33. Chunks of 32 hold it in 4.48 bits for 93 bits read. On the marks every chunk size that saves any bits reads three times as much or more: 7.44 bits for 104 read at 64, 7.06 for 705 at 512. The plate is the trade the partition actually offers, and it is a different trade on the two kinds of set.

The model counts what a select reads after its directory has sent it to a block. The single Elias–Fano’s directory sends a select to a 64-bit block of its high vector, and the select scans that block to the target one — 33 bits on average on every set. The partition does the same on its upper level to find the chunk, then scans the chunk: an Elias–Fano chunk’s high part up to the target, a bitmap up to the target bit. A chunk’s high part is at most about twice its size in bits, so a chunk of k values costs a scan that grows with k, and the plate’s lines rise to the right.

That makes the marks’ saving at large chunks exactly what the previous section said it was: the directory removed, and the reading it saved put back. On the run-start values the lines start low and left. A chunk of 16 values in a dense gathering is a bitmap of about fifty positions, and a select reads half of it. The saving is real there because it comes from the set’s shape, not from a directory left out, and it costs reads in proportion to the chunk.

What a hybrid buys, measured #

The rule twenty bits apart closed with was that a vector with both properties wants the hybrid, and the measurement says the rule is right in a narrower sense than it sounded. A hybrid pays when the set’s density changes along it, and by how much depends on how far apart the changes are and how different the densities on either side. The marks have one density everywhere. The run-start values of a nearly exact collection have two, one in three inside a gathering and nearly none outside, at a few places in 65,537 positions, and holding each region at its own density halves the set.

Neither number the earlier rule asks for sees this. The run-start values of exact copies have a density of one in a hundred, which says Elias–Fano, and a block-class entropy that is high in the gathering and nought elsewhere, which averages to a middling number that says nothing in particular. What the partition responds to is the variance of the local density along the vector, a third number. It costs one pass to measure, and the plate of chunk sizes is a crude reading of it.

The r-index itself is the reason this matters. The index that stores the runs measured an index whose size follows the number of runs, r, rather than the length of the text, and the r-index’s predecessor set is one of its parts proportional to r. Halving it on a nearly exact collection halves one of the terms that makes the index small. On a collection that drifts by more than one character in five hundred, the partition saves only a directory, and the index has other problems by then.

What these sets do not settle #

One text, one collection shape. Every set of run-start values is drawn from 32 copies of the same 2,048 characters of English, drifted by replacing characters at random. A real versioned collection changes by insertions and deletions in runs, and its changes are not independent across copies; both would move where the gatherings fall.

Fixed chunks. The chunks hold a fixed count of values. The published scheme chooses the cut points to minimise the total, which can put a cut exactly at the edge of each gathering, where a fixed count puts one wherever the count happens to land.

A model of reads. The select cost is a count of bits scanned after the directory, with the directories and the pointers taken as one read each. It is not a timing and makes no claim about caches.

Still open: cuts placed where the density changes #

Every chunk size on the chunk plate is a compromise, and on the run-start values of exact copies the best compromise, 32 values a chunk, still puts several chunk boundaries inside the dense block and lets one chunk straddle its edge. The cut points could instead be chosen to minimise the total. The cost of a partition is a sum over its chunks of each chunk’s cheapest form plus the upper level’s charge per chunk, and the cheapest partition is a shortest path through the sorted values. Each value is a vertex, an edge from value i to value j costs the chunk holding values i to j − 1, and the optimum is found in a pass over the values with a window on chunk length.

The measurement that follows computes that optimal partition for each set, compares its bits and its select reads with the best fixed chunk, and draws where its cuts fall against the gatherings on the head plate. The prediction is that on the run-start values of exact copies it saves a further 10% over chunks of 32 by cutting once at each edge of the dense block, and that at 0.0005 it saves 10% to 15%, because there the gatherings vary in size and no fixed count fits them all. On the marks it should save nearly nothing, since there is no edge to find. It could fail on the upper level: an optimal partition of a set with a few sharp gatherings may have very few chunks, some of them enormous, and then a select must scan a chunk of thousands of values. The bits would fall and the reads would rise past the single Elias–Fano’s, leaving a structure that is smaller and slower in the way the marks’ large chunks already were. The question is whether the cuts that minimise space are also cuts a select can afford, or whether a partition has to be priced in reads as well as bits before its optimum means anything.