The blocks the searches ask for

A price the levels share asked whether the flag that codes a bidirectional index’s wavelet-tree levels should charge a different price at different depths of the tree. Each level is a bit vector cut into blocks, and a block whose bits are not all one value is stored either as the index of its arrangement or as the gaps between its changes of value. A flag that weighs the work as well as the bits had chosen between them by bits plus a price on the work a rank costs inside the block: an arrangement decodes every bit before the position asked, a gap code only the changes before it. A price for each level reached no further below the curve the block lengths draw than one price for all, on any of four texts, because every level’s blocks trade bits for work at the same rate.

Its closing section looked at the one assumption every price so far had shared. Work was averaged over every position of a vector, as if a rank were equally likely to land anywhere. A pattern search’s ranks land where the pattern’s occurrences sort among the text’s suffixes, at the ends of its interval, and those are not spread evenly over the levels. A block that is asked often should be priced by the work its many ranks do, and one that is rarely asked by its few. It proposed weighting each block’s in-block work by how often a pattern search’s ranks land in it, and predicted, from the levels’ result, that the flag would reach the same frontier either way unless the blocks that are often asked differ from those rarely asked.

They differ, and the difference is worth a tenth of a bit a character on English words.

Where the ranks land #

The index is the earlier essays’: both wavelet trees of a bidirectional index over 16,384 characters, every level coded as a class and an offset per block, at blocks of 63, 255 and 1,023 bits. A workload of pattern searches is run against it. Each pattern is eight characters of the text, searched as a bidirectional index is meant to be searched, from its middle outward: its second half extended to the right through the reverse tree, then its first half to the left through the forward tree. Pattern starts are drawn evenly from the text, or so that each eight-character substring is drawn in proportion to how often it occurs, the way a workload of common queries would ask. Every rank on every level is recorded by vector and position, 160,000 ranks for 2,000 searches.

A block’s asked work is what the ranks that land in it cost inside it: for an arrangement, the bits before each rank’s position; for a gap code, the first bit, the change count and the gaps passed. The flag priced where the ranks land flips a block to its gap code when its extra bits are less than the price times the asked work the gap code saves, per rank of the workload. The flag priced on every position is the earlier essays’ exactly. To keep the comparison honest, the asked pricing reads its landings from one sample of 2,000 searches and both pricings are charged on a second, independent sample. The bits counted are the mixed blocks’ offsets and their flag bits, the only part of the index the flag changes.

Not evenly, and not by depth #

At 255-bit blocks the busiest tenth of English words’ mixed blocks takes 22% of the ranks of evenly drawn patterns and 35% of the ranks of common ones; an even spread would give it a tenth. The repetitive collection’s busiest tenth takes 23%. Nearly every block is asked something: fewer than one block in two hundred on English words receives no rank at all, and one in twenty on the repetitive collection.

The concentration has a plain cause. A search narrows an interval of suffixes, and every extension asks for ranks at the interval’s two ends in one node per level of the tree. The ends of common patterns’ intervals lie in the parts of the sorted order where common substrings sort, so the same stretches of the same vectors are asked again and again, while stretches that hold the order of rare contexts are asked rarely. The earlier essay found that depth does not separate blocks; the workload does, within every level.

A tenth of a bit at the same work #

On English words with evenly drawn patterns, the flag priced where the ranks land reaches 0.111 bits a character below the flag priced on every position equally, at the same in-block work a rank: 1.158 offset bits for 3.7 units of work, where the old pricing needs 1.269. Both are charged on searches neither was chosen on. Every point on both frontiers is at 63-bit blocks, the length the flag’s arrival had made the cheapest, which are short enough that a rank’s work inside one is small whichever code it uses, and the frontiers run from 6.4 units of work a rank with no block flipped down to about 3.1 with nearly every block flipped.

The two pricings part where the work starts to come down. Priced on every position, the flag at a price of 1 flips enough blocks to bring the work to 4.8 units for 1.077 bits, and at a price of 3 it flips 881 of the 885 mixed blocks, reaching 3.2 units for 1.349 bits. Nothing between those two prices lands between them, because a price on the average work ranks blocks only by how many bits a flip costs, and most blocks’ flips cost about the same. Priced where the ranks land, the flag at 0.3 flips 592 of the 885 and reaches 3.7 units for 1.158 bits. The 293 blocks it leaves as arrangements are the ones the searches rarely enter, and their arrangements cost less than their gap codes would.

The comparison at 3.7 units reads the old pricing’s bits off a straight line between its points at 3.2 and 4.8, since it has no point there. A layout that used the price of 3 on some vectors and the price of 1 on the others would land near that line, so the line is a fair stand-in for what the old pricing could reach. The gain does not depend on it, though. At its own cheapest point, every block flipped, the old pricing spends 1.352 bits for 3.2 units; the asked pricing’s cheapest point spends 1.294 bits for 3.1 units, less of both, because the few blocks it never flips are blocks no rank of the charging sample enters either.

That is the mechanism the whole plate turns on. Pricing on every position, a block’s work is its average over all its positions, the same for every block of the same length and shape, so the flag can only rank blocks by the bits a flip costs against that average. Pricing where ranks land, a block nobody asks has no work to save, keeps its arrangement and its cheaper bits, and a block many ranks land in is flipped early, because its work is multiplied by its traffic. The asked pricing spends the gap codes’ extra bits where the work is.

When common patterns are asked in proportion to how often they occur, the gain on English words rises to 0.156 bits a character at the same work: 1.151 offset bits for 2.2 units of work against 1.306. The ranks are more concentrated, the busiest tenth taking 35% instead of 22%, so the asked pricing has fewer blocks to flip for the same reduction in work. At a price of 1 it flips 580 of the 885 blocks. Every rank is cheaper here under both pricings, about 3.7 units with nothing flipped against 6.4 for evenly drawn patterns, and that is a property of the workload rather than the flag: a common pattern’s interval is wide, its ends sit in long runs of the same symbol, and a rank inside a long run is cheap to answer from an arrangement as well as from a gap code. The workload that most resembles real use, where some queries are far commoner than others, is the one where weighing the work by use pays most.

The repetitive collection #

On the repetitive collection the gain is 0.031 bits a character at the same work, with either workload. The asked pricing flips 421 of 566 mixed blocks at its best point; the old pricing, at the work nearest it, flips all 566. The earlier essays found this collection’s blocks cheap to flip: almost every arrangement block is a long stretch of one value with a few changes, its gap code is barely longer, and at a price of a tenth almost every block flips. When nearly every block is worth flipping on any reckoning, it matters little which ones the searches ask, and the asked pricing’s advantage shrinks to the few blocks a uniform price flips that no search uses.

The two texts bracket what the workload can buy. Where gap codes are expensive and only some blocks can afford them, as in English words, choosing those blocks by traffic is worth a tenth of the offsets’ bits. Where gap codes are nearly free, the choice hardly matters.

Every text and workload #

Priced where the ranks land, the flag reaches 0.111 and 0.156 bits a character below the old pricing on English words and 0.031 and 0.030 on the repetitive collection, at equal work, on both workloads. On English words that is about a tenth of the offsets’ bits at the work a rank where it is measured. Earlier changes to the flag, the length of a block and a price for each level, were judged at the curve the block lengths draw, on the frame that puts bits and steps side by side, and the asked pricing is the first since the price itself to move the frontier at all on English words.

Bits that depend on the queries #

The asked pricing makes the index’s layout a function of its workload. Two indexes of the same text, built for different query mixes, store different blocks as gap codes, and an index built for one workload and queried with another loses some of its advantage. The comparison here is the mild version of that: the landings are read from one sample of searches and charged on another of the same kind, and the gain survives. A different kind of workload, rare patterns where common ones were expected, was not tried.

That dependence is also why the earlier pricing found nothing by depth. A wavelet tree’s levels hold the same text in different projections, and a text’s character is the same at every depth, as the earlier essay found. The searches are not part of the text, and an index has met that before: one half of a bidirectional index is never asked where an occurrence is, only how many there are, and was made smaller for it. The searches select a small, repeated set of positions in every level, and the blocks that hold those positions are the ones whose decoding is ever paid for. A flag for the blocks that change once chose each block’s code by its own bits; the asked pricing chooses it by its own bits and its own traffic, and the second turns out to matter as much as the first.

Why charge on a second sample #

The asked pricing chooses its flips from where 2,000 searches’ ranks landed. Charged on those same searches it would be measured on the data it was fitted to, and some of what it reached would be the noise of that sample: a block entered by three ranks rather than one by chance would be flipped, and the flip would pay exactly for those three. On a fresh sample the chance ranks land somewhere else, and only the blocks that are busy because of what the workload is, rather than because of which searches were drawn, still pay. Every number above is the second kind.

The sample is not small for this purpose. Two thousand searches of eight characters make 160,000 ranks across 385 mixed blocks at 255 bits, about four hundred ranks a block, and at 63 bits about 180 a block. A block’s count is then good to a few tens per cent, enough to tell a busy block from a quiet one by the factor of several that the concentration shows. The flag’s choices near the price’s threshold are noisier, but those blocks’ choices are worth little either way.

What the flag still costs #

Nothing about the asked pricing changes what the index stores. Each mixed block still carries one flag bit saying which code it uses, and a rank reads that bit before decoding. The difference is entirely at build time, where the builder needs the landings of a sample of the workload before it lays the blocks out. That is a log of queries, which a long-running index already has, or a sample drawn from the text the way a workload is expected to ask. The work is one pass over the sample’s ranks and one comparison per block.

What the prediction got right #

The closing section predicted that, priced one block at a time on the earlier unit, the flag would reach the same frontier as one price does, and it does by construction, since one price already flips exactly the blocks whose own price is under it. It predicted that what could move the frontier is the work unit, and asked whether a block that is often asked should be priced differently from one that is rarely asked. It should: weighted by where a workload’s ranks land, the flag reaches 0.11 to 0.16 bits a character further on English words, at the same work and on searches it was not fitted to.

The question was whether the price a block wants is a property of the block’s bits, which every level shares, or of the queries that reach it, which they do not. It is both, and the queries’ share is the larger on a text whose gap codes are dear.

What the searches leave out #

Exact searches of eight characters. Every pattern is a substring of the text, searched to its end. Approximate searches, which branch and ask many more intervals, and absent patterns, which stop early, would land differently.

Offsets only. The bits counted are the mixed blocks’ offsets and flag bits. The classes, superblocks and the rest of the index are the same under both pricings and are left out; on the earlier essays’ full count, the gains here are the same bits on a larger total.

One seed each. One sample of 2,000 searches to choose from and one to charge on, on one text of 16,384 characters each kind.

Still open: a layout that follows the traffic #

A block’s price now depends on its traffic, and traffic changes. An index whose blocks are recoded as the workload shifts would keep the gain; one built once for a workload would lose it as the workload drifts, at a rate nothing here measures. Between the two is an index that records, block by block, how many ranks land in it since its last recoding, and recodes a block when its own count says the other code would now be cheaper.

The measurement that follows runs a workload that changes, the commonest patterns of one half of the text and then of the other, recodes blocks by their recent counts after every thousand searches, and charges the recoding as a rewrite of the block. The prediction is that a recoding index keeps within a few hundredths of a bit of the asked pricing fitted to each half, and that an index fitted to the first half and left alone loses most of its gain on the second, since the busy blocks move with the patterns. It could fail on the counts: a block’s traffic over a thousand searches is a few dozen ranks, noisy enough that blocks near their price may be recoded back and forth, and every recoding is a rewrite. The question is whether an index can follow its queries cheaply enough to keep what following them is worth.