A layout the traffic does not move

A bidirectional index answers a pattern search by extending an interval one character at a time, to the right through one wavelet tree and to the left through another, and the search that starts in the middle found it cheapest to start a pattern from its middle and grow both ways. Every step is a rank on a bit vector at some depth of a tree, and the vectors are stored in blocks. A flag for the blocks that change once gave each block a choice of two codes — an arrangement, the block’s bits named by their rank among all blocks of the same count, or a gap code, the distances between its changes — and a flag that weighs the work chose between them by a price $\lambda$ on the work a rank does inside the block against the bits its coding costs.

The blocks the searches ask for moved the price from every position of a block to the positions a workload’s ranks actually land on. A search’s ranks land where its patterns’ occurrences sort, unevenly; the busiest tenth of blocks took 22% to 35% of the ranks, and pricing on those landings saved up to 0.156 bits a character at equal work on English when the patterns were the text’s commonest. Its closing section saw the obvious weakness. A block’s price now depended on its traffic, and traffic changes. An index fitted once to a workload would lose the gain as the workload drifted; one that recorded, block by block, the ranks landing since its last recoding, and recoded a block when its own count said the other code was now cheaper, would keep it.

It proposed a workload that changes — the commonest patterns of one half of the text, then of the other — recoding blocks by their recent counts after every thousand searches, the recoding charged as a rewrite of the block. The prediction was that the recoding index would stay within a few hundredths of a bit of the pricing fitted to each half, and that an index fitted to the first half and left alone would lose most of its gain on the second, since the busy blocks would move with the patterns. It named the risk: a block’s traffic over a thousand searches is a few dozen ranks, noisy enough that blocks near their price might be recoded back and forth, and every recoding is a rewrite.

A stream that changes halfway #

The index and the codes are the earlier essay’s: 16,384 characters, English and a repetitive collection of near-copies, both wavelet trees’ vectors cut into blocks of 255 bits, a block whose bits are all equal coded for free and every mixed block flagged as arrangement or gap code. In-block work is what a rank costs inside its block: the bits before its position for an arrangement, the changes passed for a gap code.

The stream is 4,000 middle-out searches for eight-character patterns, in four windows of a thousand. The first two windows draw each pattern’s start in proportion to how often its eight characters occur within the text’s first half, so the commonest patterns there are asked most; the last two windows do the same for the second half. Four layouts are charged on that stream: priced on every position, as before any workload was read; priced on a separate sample of the first half’s workload and never changed; priced on a separate sample of each half’s workload and switched at the halfway point for nothing — the bound a recoding index aims at; and recoded after each window, every block re-priced on that window’s own landings and recoded if its cheaper code changed, each recoding charged its block’s bits as written. Every price from 0.1 to 30 was run; the plates at a single price use $\lambda = 0.1$, where the workload pricing differed most from the positional.

The second half costs what the first did #

On English, when the searches move from the first half’s commonest patterns to the second’s, the layout priced on the first half and never changed does 8.24 units of in-block work a rank in the second half against 8.13 for the layout refitted to it — 1% more — and the layout recoded every thousand searches 8.14, having rewritten 48 blocks. The second half’s searches are a little dearer than the first’s under every layout, refitted or not, because its commonest patterns land on different positions within the same busy blocks. But the layout that ignored the change loses only a tenth of a unit to the one that followed it perfectly and for free. The positional layout, which never read a workload, does ten to twelve units in every window.

So the prediction was wrong at its centre: there was no gain to lose. Recoding then has nothing to recover, and the plate shows what it costs to try. In the second window, after recoding on the first window’s counts, the recoded layout does 8.08 units against the kept layout’s 7.77 — 4% worse, on the same half’s patterns, because a thousand searches’ landings are a noisy measure of a block’s traffic and it recoded blocks the next thousand searches did not favour. That is the risk the proposal named, and it is real; but it is the only thing recoding does that the plates can see.

One curve for three layouts #

Over the whole stream the layout priced on the first half and kept, the layout refitted at halfway for free, and the layout recoded every thousand searches draw one curve: at every price their work a rank lies within 0.06 of each other and their bits within a hundredth — and all three lie under the layout priced on every position at equal work. At 7.2 units of work a rank the positional layout spends 1.258 bits a character on the mixed blocks and the workload layouts about 1.232, a gain of about 0.026 bits; at the dearest prices, where every layout sends almost every mixed block to its gap code, all four meet near 6.8 units and 1.28 bits.

The gain of workload pricing over positional pricing is the earlier essay’s finding, here at a smaller size than it measured, since this stream’s workload is the commonest patterns of half a text rather than of the whole. What this plate adds is that the gain does not depend on which half’s patterns the layout was priced on. Fitted to the first half, the layout keeps its whole gain on the second.

What recoding writes #

Recoding pays for nothing it buys: at a price of 0.1 it rewrites 48 of 385 blocks over the stream, 0.714 bits a character, and does 7.92 units of work a rank against the kept layout’s 7.89; at the dearer prices it rewrites a handful of blocks for a hundredth of a unit. The rewrites are not small beside the quantity they serve. The whole difference between workload pricing and positional pricing is a few hundredths of a bit a character; three recodings over four thousand searches rewrite seven tenths of a bit a character, and buy back, on average over the stream, a slightly worse layout than not recoding at all.

At low prices more blocks sit near their price, where a window’s few dozen ranks can tip the choice either way, and the recoder flips them. At high prices nearly every block’s gap code wins by a wide margin and only the five blocks nearest the boundary flip. In no row does recoding move the work by more than a few hundredths of a unit.

The busy blocks stay busy #

The busy blocks do not move with the patterns: on English, 27 of the 39 blocks busiest under the first half’s commonest patterns are among the 39 busiest under the second half’s, and they take 35% of the first half’s ranks and still 29% of the second’s — the ranks land where the text’s common substrings sort, and both halves share them. A rank in a wavelet tree lands at a position determined by where the search’s interval lies in the sorted order of the text’s suffixes, and the commonest eight-character patterns in either half of an English text are built from the same common short strings — spaces and common words, the, and, of. The likeliest reading of the overlap, which the plate measures but does not explain, is that the first steps of every search are taken on those short strings, at positions set by them alone, so the blocks there are busy whichever half the patterns come from.

That is why the layout fitted to the first half keeps its gain: what it learned was not the first half’s patterns but the text’s common prefixes, which the second half’s patterns use too. The proposal pictured traffic moving from one set of blocks to another, as it would between two unrelated texts; within one text, the commonest patterns of any large part of it share the blocks that matter.

What a thousand searches can see #

The recoder’s one measurable effect, the 4% worse second window, comes from how thin a window’s evidence is. A thousand searches of eight characters make 80,000 ranks, about 45,000 of them in the 385 mixed blocks; the busiest tenth of those takes about a third, so a typical mixed block outside it receives under a hundred ranks a window, and many far fewer. A block whose two codes cost nearly the same at its long-run traffic flips if those few ranks happen to fall at positions one code serves better, and the next window’s ranks, falling elsewhere, make the flip a loss.

The kept layout was priced on a sample of two thousand searches drawn from the first half, twice a window, and that is enough for the decision to be stable: at the price of 0.1 the layouts priced on the first half’s sample and on the second half’s differ in their codes for 15 of the 385 mixed blocks, about as many as each of the recoder’s three recodings changed. So the evidence that decides the layout has to be larger than a window for the layout to be right, and once it is, the layout no longer needs to follow anything within one text. A recoder worth running would need a window as large as the sample the layout was first priced on, and then it would change as little as the plates show the traffic does.

The repetitive collection #

On the repetitive collection the second half’s patterns cost exactly what the first half’s did under every layout, 2.25 units of work a rank, and the recoding layout recodes no block at any price: the halves of a collection of near-copies are near-copies, and their commonest patterns are the same patterns. The collection is the earlier essays’ test of what a repetitive text does to an index: its two halves hold the same documents with a few edits, so a workload drawn from either half’s commonest substrings is the same workload with different starting positions, landing on the same blocks. It is the limiting case of the English finding, where only the prefixes were shared.

When a layout would have to move #

The closing question was whether an index can follow its queries cheaply enough to keep what following them is worth. On this stream following was worth nothing, so the question was answered by the stream rather than by the index. A shift of workload between the two halves of one text moves the patterns but not the blocks they land on, and a layout priced on either half’s patterns is priced on the text’s common prefixes. A price the levels share found the same kind of indifference across the trees’ depths: a single price served every level, because every level traded bits for work at the same rate. Here a single fitting serves every part of the text, because every part asks the same blocks.

A stream that would make a layout move needs searches whose common prefixes differ: queries in a second language against a bilingual collection, a code search switching from one programming language to another, a log index whose traffic shifts from one service’s messages to another’s. The half that is never asked where found that a bidirectional index’s two trees are asked very differently by one workload; two workloads with different prefixes would differ between blocks within one tree. None was run here, and the gain such a layout might keep is the earlier essay’s 0.156 bits a character at most.

What the stream does not show #

One text, cut in half. Every shift measured is between the halves of one text. The finding is that such a shift does not move the busy blocks; it says nothing about shifts between texts.

Recoding by one window’s counts. The recoder re-priced every block on the last thousand searches alone. A recoder that kept a decaying count, or recoded only blocks whose count had moved far past their price, would recode less and lose less in the noisy windows; it would also gain nothing here, since there was nothing to gain.

One pattern length. Every search was eight characters long. The finding rests on searches spending their early steps on short strings both halves share, and a search spends a larger share of its ranks there the shorter it is, so shorter patterns should make the halves agree even more closely. Longer patterns put more of each search’s ranks in its later steps, on longer stretches of the pattern that the two halves no longer share, and those steps land at positions the shared short strings do not set — which is where a recoder could first find blocks whose traffic moves. How long a pattern must be before the busiest tenth stops being shared was not measured.

One block length. 255 bits, the middle of the earlier essays’ three lengths. Shorter blocks would make each block’s traffic thinner and the recoder noisier; longer ones would put more of each tree’s busy region in fewer blocks, so a shift between workloads with different prefixes would move fewer blocks but each further. Neither was measured.

Bits and steps on one frame priced a block’s two costs together; six bits a class and an interval that grows at both ends described the structures whose blocks these are. The layouts here differ in which blocks they code which way, and on this stream the choice is the text’s, not the traffic’s.

Still open: two workloads with different prefixes #

The flag’s workload pricing kept its gain through a shift between the halves of one text because the halves share their common prefixes. The case the proposal meant is a shift between workloads that do not: a collection of two languages, searched first in one and then in the other. There the commonest patterns of each workload begin with different short strings, their ranks land in different blocks of the trees’ upper levels, and a layout priced on one would be priced on blocks the other rarely asks.

The measurement that follows builds the index over a collection of English and a second language of the same size, interleaved by document, and runs the same stream with the first two windows drawn from the English documents’ commonest patterns and the last two from the other’s, with the same four layouts and a recoder that recodes a block only when its count over the last two windows has crossed its price by a margin. The prediction is that the kept layout then loses most of its gain over the positional layout on the second half — its work rising toward the positional layout’s at equal bits — and that the margin recoder keeps within a hundredth of a bit of the refitted layout for under a tenth of a bit a character rewritten. It could fail on the shared structure that remains: two languages written in one alphabet share spaces and punctuation, and their trees’ top levels may stay busy in the same blocks anyway. The question is how different two workloads must be before a layout fitted to one stops serving the other.