The other axis

The value every copy asks for

A select directory over an r-index's run starts had been priced as if every value were asked equally often, and an r-index does not ask that way: locating a pattern walks its occurrences, and each step selects the run start that precedes one occurrence. Weighting each value by a workload of located patterns was predicted to place denser samples where the common patterns' run starts lie, reaching 3.80 bits a value for 55 bits read on exact copies, while a directory priced uniformly would read a tenth more on that workload. On exact copies 661 of the 666 run starts sit in the last copy, and 97% of the selects ask one value — the run start at position nought, the predecessor of every occurrence in the other 31 copies. A uniformly priced directory reads 10.5 bits a select there, not a tenth more than 56.8 but under a fifth of it, and the workload's own price is met at 3.0 bits read. Where the run starts spread, at divergences of 0.001 and 0.01, the weighting buys five to seven bits read at the highest rate, and a search log's skew adds nothing to what the copies already did.

An r-index stores a text by the runs of its Burrows–Wheeler transform, and among the things it keeps is the set of text positions at which those runs start. On a repetitive collection that set is small, a few hundred to a few thousand values against a text of 65,536 characters, and sparse on average and dense where it gathers. The strand of essays that stores it cuts it into chunks by a shortest path, as cuts that follow the gathering did, and gives each chunk a directory so that a select — the request for the jj-th value — can find its value without scanning the whole chunk.

A select that starts near its answer gave each chunk select samples and a sample that has to be found rank samples; a second level that pays in one band built the directory from both kinds of sample, select samples every tt values naming a rank block and rank samples every ss bits. A spacing priced by what it saves let the path choose each chunk’s select spacing at an exchange rate λ\lambda, bits stored for every bit read, among t0t_0, 2t02t_0 and 4t04t_0, where t0t_0 makes tt values span about one rank block. On exact copies it reached 3.824 bits a value for 56.8 bits read a select at λ=0.01\lambda = 0.01, a point no earlier directory reached.

Every one of those prices assumed that each value is selected equally often. The closing section of that essay said this is not how an r-index asks. To report where a pattern occurs, an r-index finds one occurrence and then walks the others with a function called φ, which takes one text position to the position of its neighbour in suffix order. Every occurrence at the same price built that walk. Each φ step finds the run start that precedes the current position, the largest value in the set no greater than it, which is a rank and then a select of that value; the answer is that run start’s stored partner shifted by the distance between them. So the values selected are the predecessors of the occurrences being reported, and a pattern that is located often asks for the same values every time.

The proposal was to weigh each value by how often a workload of located patterns asks for it, and to charge each chunk its stored bits plus the rate times its reads weighted by that workload. Its prediction was that on exact copies the weighted price would put denser samples in the few chunks holding the common patterns’ run starts and sparser ones elsewhere, reaching about 3.80 bits a value for 55 bits read on that workload, and that a directory priced uniformly would read about a tenth more on the workload than on uniform selects. The named risk was that on exact copies, where every copy’s run starts interleave, the asked values would be spread across every chunk and weighting would change no chunk’s choice.

A workload of located patterns

The sets are the strand’s: 32 copies of a 2,048-character English-like text, exact or with each character changed with probability 0.001 or 0.01, the set being the r-index’s run starts as text positions. Exact copies have 666 run starts; 0.001 has 1,034; 0.01 has 4,144.

A workload is 2,000 located patterns of sixteen characters. In the first, each pattern is the substring at a uniformly drawn position of the collection, so a pattern is asked in proportion to how often it occurs. In the second, 256 such substrings are drawn once and then asked with Zipf weights of exponent one, the shape of a search log, where a few queries make up most of the traffic. Each pattern is located in full: every text position at which it occurs costs one φ step, which selects the largest run start at or before that position. A value’s weight is its share of all the workload’s selects, scaled so that the weights sum to the number of values; a uniform workload is weight one everywhere.

The path and its replay take the weights directly. A chunk’s expected selects are the sum of its values’ weights rather than its size, the priced spacing weighs the modelled read by that sum, and the replay averages each select’s read bits by its weight. Bits a value are stored bits, the same as before. A directory priced under one weighting can be replayed under another, and several of the plates do exactly that.

Where the run starts sit

On exact copies 661 of the 666 run starts sit in the last copy, and 97% of the selects a workload of located patterns makes ask one value, the run start at position nought — the predecessor of every occurrence in the other 31 copies; at divergence 0.001 the run starts spread through the copies and so do the selectsFor 32 copies of a 2,048-character text, the share of run starts in each copy (bars) and the share of φ's selects that land on a run start in that copy (dots), for 2,000 located patterns of sixteen characters, each panel on its own scale. Exact copies: run starts 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 661; selects 96.9%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 0.0%, 3.1%. Divergence 0.001: run starts 3, 5, 3, 7, 39, 33, 35, 51, 14, 1, 36, 19, 34, 47, 23, 48, 2, 134, 141, 83, 80, 44, 32, 33, 16, 12, 12, 6, 15, 1, 12, 13; selects 5.3%, 1.8%, 3.4%, 4.5%, 2.6%, 1.6%, 3.4%, 3.1%, 5.4%, 0.7%, 4.0%, 2.0%, 3.0%, 3.1%, 3.2%, 4.3%, 2.5%, 2.2%, 3.4%, 3.0%, 3.9%, 2.5%, 2.8%, 3.1%, 3.2%, 5.0%, 1.9%, 2.4%, 3.4%, 4.9%, 4.0%, 0.0%.share of run startsshare of selectsexact copies100%0divergence 0.00115%0copy, first to last2,000 located patternsper copy
Fig. 1 Copy by copy, over 32 copies of a 2,048-character text: the share of the r-index’s run starts in each copy (bars) and the share of φ’s selects, for 2,000 patterns located in full, landing on a run start in that copy (dots), each panel on its own scale. On exact copies one run start lies in the first copy, four in the 31st and 661 in the last; 97% of the selects land in the first copy, on one value. At divergence 0.001 the run starts are spread through the copies and the selects follow them.

On exact copies, 661 of the 666 run starts sit in the last copy, and 97% of the selects ask one value, the run start at position nought, which is the predecessor of every occurrence in the other 31 copies. The proposal’s risk pictured run starts interleaved through the collection. In suffix order they are interleaved, which is what makes the Burrows–Wheeler transform’s runs long. As text positions they are not: a run of the transform starts where the suffixes stop agreeing, and among 32 identical copies the suffix that stops agreeing first is the one in the last copy, which reaches the end of the text before its siblings do.

So on exact copies the set is a single value at the start of the text and a cluster at its end. A pattern of sixteen characters occurs about 33 times, once or twice in each copy, and for every occurrence outside the last copy the largest run start at or before it is position nought. A φ step there asks for the first value of the set, and the answer is correct: the stored partner of position nought, shifted by the distance, is the same occurrence one copy along. The structure that looked spread in one order is a point in the other, and the workload lands on the point.

At divergence 0.001 the picture changes because the changes create run starts where they fall, scattered across the copies, and the selects follow them. That set is where the proposal’s question can actually be asked.

Concentrated, not spread

The selects are concentrated, not spread: half of them ask 0.2% of the run starts on exact copies, 2.3% at divergence 0.001 and 4.7% at 0.01, and only 35% of the run starts at 0.01 are asked at all; a search log's skew changes almost nothingCumulative share of the selects made by 2,000 located patterns against the share of run starts, most asked first, for patterns drawn from the text (solid) and from a search log of 256 patterns at Zipf 1 (dashed). exact copies: 666 run starts, 65,524 selects from text patterns, half of them on 0.2% of run starts, 80% asked at all; from the log, half on 0.2%, 28% asked; divergence 0.001: 1034 run starts, 63,475 selects from text patterns, half of them on 2.3% of run starts, 59% asked at all; from the log, half on 2.2%, 28% asked; divergence 0.01: 4144 run starts, 48,773 selects from text patterns, half of them on 4.7% of run starts, 35% asked at all; from the log, half on 2.4%, 24% asked.00.2500.5000.750100.2500.5000.7501share of the run starts, most asked firstshare of the selectsexact copiesdivergence 0.001divergence 0.01diagonal: everyvalue asked equallysolid: text patterns · dashed: search logshare of selects
Fig. 2 Cumulative share of the selects against the share of run starts, most asked first, for patterns drawn from the text (solid) and from a search log of 256 patterns at Zipf 1 (dashed). Exact copies: half the selects on 0.2% of the 666 run starts. Divergence 0.001: half on 2.3% of 1,034. Divergence 0.01: half on 4.7% of 4,144, with only 35% of the run starts asked at all. The diagonal is every value asked equally.

The selects are concentrated, not spread: half of them ask 0.2% of the run starts on exact copies, 2.3% at divergence 0.001 and 4.7% at 0.01, and at 0.01 only 35% of the run starts are asked at all. The risk was that the asked values would be spread across every chunk. Every curve on the plate rises almost vertically before it bends, which is the opposite.

The mechanism at the diverged sets is a weaker form of the exact one. A run start is the predecessor of every text position up to the next run start, so a run start followed by a long gap covers many positions, and every occurrence in that gap selects it. Changes at 0.001 are about two per copy, so gaps between run starts span hundreds of characters, and a few run starts before long, unchanged stretches take most of the traffic. At 0.01 the gaps are shorter and the curve less steep, but still far from the diagonal.

The dashed curves barely leave the solid ones. A search log that asks 224 distinct patterns, a few of them hundreds of times, concentrates the selects no further than 1,249 patterns drawn from the text. The skew that matters is not in the queries but in the set: whatever pattern is asked, its occurrences fall into the same long gaps.

A uniform price, read on the workload

A directory priced for uniform selects reads 10.5 bits a select on the workload on exact copies at the proposal's rate, against 56.8 on uniform selects — under a fifth of it, not a tenth more — because the value asked nine times in ten is the set's first, which a select reaches without a sample; at divergence 0.01 the two are within a bitThe priced path chosen under uniform weights, its stored directory replayed on uniform selects and on the workload of patterns from the text, bits read a select: exact copies, λ 0.003: 62.0 and 10.6; exact copies, λ 0.01: 56.8 and 10.5; exact copies, λ 0.03: 62.5 and 18.4; divergence 0.001, λ 0.003: 66.2 and 53.3; divergence 0.001, λ 0.01: 61.5 and 51.2; divergence 0.001, λ 0.03: 58.8 and 54.0; divergence 0.01, λ 0.003: 72.4 and 71.8; divergence 0.01, λ 0.01: 65.2 and 64.6; divergence 0.01, λ 0.03: 59.3 and 59.6.uniform selectsthe workloadexact copies, λ 0.00362.0 · 10.6exact copies, λ 0.0156.8 · 10.5exact copies, λ 0.0362.5 · 18.4divergence 0.001, λ 0.00366.2 · 53.3divergence 0.001, λ 0.0161.5 · 51.2divergence 0.001, λ 0.0358.8 · 54.0divergence 0.01, λ 0.00372.4 · 71.8divergence 0.01, λ 0.0165.2 · 64.6divergence 0.01, λ 0.0359.3 · 59.6bits read a selects = 64
Fig. 3 The priced path chosen under uniform weights, its directory replayed on uniform selects and on the workload of patterns from the text, bits read a select. Exact copies at λ 0.003, 0.01 and 0.03: 62.0 and 10.6, 56.8 and 10.5, 62.5 and 18.4. Divergence 0.001: 66.2 and 53.3, 61.5 and 51.2, 58.8 and 54.0. Divergence 0.01: 72.4 and 71.8, 65.2 and 64.6, 59.3 and 59.6.

A directory priced for uniform selects reads 10.5 bits a select on the workload on exact copies at the proposal’s rate, against 56.8 on uniform selects — under a fifth of it, not a tenth more — because the value asked nine times in ten is the set’s first, which a select reaches without a sample. The proposal’s second number reverses sign. The workload is not harder for a directory that ignores it; on exact copies it is six times easier.

The reason is the shape of a select for the first value. The directory’s samples exist to start a scan near its target, and the first value of a chunk is already at the start: a select for it reads the upper level, no select sample, and the first rank block, about ten bits in all. Whatever spacing the path chose, a workload that asks for the first value of the set 97% of the time pays almost nothing for it.

On the diverged sets the gap closes. At 0.001 the workload reads five to thirteen bits less than uniform selects, because the heavily asked run starts are often early in their chunks; at 0.01, where the selects are least concentrated, the two are within a bit at every rate. The proposal’s tenth more did not appear on any set: the workload was never harder.

A price fitted to the workload

At divergence 0.001, pricing the directory by the workload pays only at the highest rate: at λ 0.1 it stores 6.600 bits a value and reads 37.1 bits a select on the workload, where the uniformly priced directory stores 6.988 and reads 44.3; at the lower rates the two lie within a few bits read of each otherdivergence 0.001, patterns from the text: bits a value against bits read a select on the workload, for the priced path chosen under uniform weights and under the workload's, at λ 0.001, 0.003, 0.01, 0.03, 0.1: λ 0.001: uniform 6.180 bits, 53.7 read; workload 6.180, 53.8; λ 0.003: uniform 6.182 bits, 53.3 read; workload 6.178, 52.2; λ 0.01: uniform 6.193 bits, 51.2 read; workload 6.218, 48.1; λ 0.03: uniform 6.240 bits, 54.0 read; workload 6.282, 44.1; λ 0.1: uniform 6.988 bits, 44.3 read; workload 6.600, 37.1.6.206.306.406.506.606.706.806.9074050bits read a select, on the workloadbits a valuepriced uniformlypriced by the workloaddivergence 0.001, s = 64both read on the workload
Fig. 4 Divergence 0.001, patterns from the text: bits a value against bits read a select on the workload, for the priced path chosen under uniform weights and under the workload’s, at λ 0.001, 0.003, 0.01, 0.03 and 0.1. Priced uniformly: 6.180 bits for 53.7 read, 6.182 for 53.3, 6.193 for 51.2, 6.240 for 54.0, 6.988 for 44.3. Priced by the workload: 6.180 for 53.8, 6.178 for 52.2, 6.218 for 48.1, 6.282 for 44.1, 6.600 for 37.1.

At divergence 0.001, pricing the directory by the workload pays only at the higher rates: at λ 0.1 it stores 6.600 bits a value and reads 37.1 bits a select on the workload, where the uniformly priced directory stores 6.988 and reads 44.3; at the lower rates the two lie within a few bits read of each other. At those rates both paths store almost no select samples, so there is nothing for the weighting to move. At λ 0.03 the workload’s price reads ten bits less for four hundredths of a bit more, and at λ 0.1 it is better on both axes, because the uniform price at that rate gives every chunk a dense directory and the workload’s gives one only to the chunks that are asked.

On exact copies the proposal’s first number is met at once and by a margin it did not anticipate. The workload-priced path stores 3.751 to 3.776 bits a value and reads 10.6 bits a select at the lowest rates and 3.0 from λ 0.01 up: it cuts the chunks so that position nought sits in a chunk that needs no directory at all, and the selects that ask for it read only the upper level. The predicted 3.80 bits for 55 bits read is passed by fifty bits read, but not because samples were placed where the common patterns’ run starts lie. There is one run start the workload asks for, and it needed none.

At divergence 0.01 the weighting buys about six bits read at the same bits at λ 0.03, 53.3 against 59.6 near 6.49 bits a value, and five at λ 0.1. Across the three sets the gain from fitting the workload is real wherever there is a workload to fit, and it is a few bits read out of fifty.

What a fitted directory gives up

Fitted to its workload, a directory reads no worse on uniform selects at divergence 0.01 — 59.7 bits against 59.3 at λ 0.03 — but on exact copies, where it stored almost nothing outside the one value asked, a uniform select reads 66.2 against 62.5At λ 0.03, s = 64: the directory priced under uniform weights and under the workload of patterns from the text, both replayed on uniform selects, bits read a select, with their bits a value. exact copies: priced uniformly 62.5 read at 3.902 bits, priced by the workload 66.2 at 3.769; divergence 0.001: priced uniformly 58.8 read at 6.240 bits, priced by the workload 53.0 at 6.282; divergence 0.01: priced uniformly 59.3 read at 6.489 bits, priced by the workload 59.7 at 6.495.priced uniformlypriced by the workloadboth read on uniform selectsexact copies62.5 at 3.90266.2 at 3.769divergence 0.00158.8 at 6.24053.0 at 6.282divergence 0.0159.3 at 6.48959.7 at 6.495λ 0.03, s = 64bits read a select
Fig. 5 At λ 0.03, s = 64: the directory priced under uniform weights and the one priced under the workload, both replayed on uniform selects, bits read a select, with bits a value. Exact copies: 62.5 at 3.902 bits and 66.2 at 3.769. Divergence 0.001: 58.8 at 6.240 and 53.0 at 6.282. Divergence 0.01: 59.3 at 6.489 and 59.7 at 6.495.

Fitted to its workload, a directory reads no worse on uniform selects at divergence 0.01 — 59.7 bits against 59.3 at λ 0.03 — but on exact copies, where it stored almost nothing outside the one value asked, a uniform select reads 66.2 against 62.5. The question for anyone building such a directory is how much is lost if the workload changes, and the plate gives a modest answer. On the diverged sets a directory fitted to one workload serves uniform selects about as well as one built for them; at 0.001 it even reads less on uniform selects, because the path the workload led it to is a better path, not only a better-fitted one.

On exact copies the fitted directory is cheaper by an eighth of a bit a value and dearer by four bits a select on uniform traffic. That is the price of a directory that has learned that one value is all anyone asks for: if the workload changed to ask for others, it would find them less well served. Since the concentration on position nought follows from the set’s own geometry rather than from the patterns, any workload of located patterns would ask for it, and the fitted directory’s bet is a safe one.

The copies’ skew, not the log’s

A search log that asks 224 patterns where the text asks 1,249 leaves the workload-priced directory's reads within 0.3 bits on every set: the skew that matters is the copies', which every pattern sharesAt λ 0.03, s = 64, the directory priced by each workload and read on it, bits read a select, for 2,000 patterns drawn from the text and 2,000 asked from a log of 256 at Zipf 1, with the distinct patterns each asked and the share of run starts that takes half the selects. exact copies: text 3.0 (1249 distinct, half on 0.2%), log 2.8 (224 distinct, half on 0.2%); divergence 0.001: text 44.1 (1269 distinct, half on 2.3%), log 44.4 (224 distinct, half on 2.2%); divergence 0.01: text 53.3 (1419 distinct, half on 4.7%), log 53.5 (224 distinct, half on 2.4%).patterns from the texta search logexact copies3.02.8divergence 0.00144.144.4divergence 0.0153.353.5λ 0.03, s = 64bits read a select
Fig. 6 At λ 0.03, s = 64, the directory priced by each workload and read on it, bits read a select: patterns drawn from the text (1,249 distinct) against a log of 256 at Zipf 1 (224 distinct asked). Exact copies: 3.0 and 2.8. Divergence 0.001: 44.1 and 44.4. Divergence 0.01: 53.3 and 53.5. Half the selects land on 0.2%, 2.3% and 4.7% of the run starts for the text patterns and on 0.2%, 2.2% and 2.4% for the log.

A search log that asks 224 patterns where the text asks 1,249 leaves the workload-priced directory’s reads within 0.3 bits on every set: the skew that matters is the copies’, which every pattern shares. The proposal pictured a frequent pattern asking for the same values again and again, and the log makes that happen, with its commonest pattern asked several hundred times. It does not change what the directory should store, because every pattern’s occurrences fall into the same gaps between run starts, and the gaps decide which values are asked.

At 0.01 the log is visibly more concentrated, half its selects on 2.4% of the run starts against 4.7%, and the directory fitted to it reads the same. The extra concentration is on values the text workload also asked heavily, so the chunks the two directories favour are the same chunks.

What decides which values are asked

The proposal asked whether a directory can be fitted to its workload as well as to its set, or whether on a repetitive collection every chunk is asked about equally after all. Neither alternative held. A directory can be fitted to its workload, and on the diverged sets fitting it buys a few bits read at the high rates. But the chunks are not asked equally, and the reason they are not is a property of the set, not of the workload: a run start is asked once for every occurrence in the gap that follows it, and the gaps on a repetitive collection are wildly unequal.

That moves the question from the queries to the geometry. On exact copies, one gap runs from position nought into the 31st copy, more than 61,000 characters, and the rest are inside the last two copies, so every φ step outside the last copy is a select of position nought. A designer who knows only that the collection is repetitive can predict that, and store the set’s first value where it costs nothing to find, without looking at a single query. The sampling that follows the runs made the r-index’s samples follow the runs of the transform; the selects those samples issue follow the gaps between the runs’ starts in the text, which is a second structure the same runs determine.

A select that starts near its answer and the directories after it priced reads as if every value mattered equally. On a collection whose changes are rare, the values that matter are the few that begin long unchanged stretches, and a weight that is each run start’s gap to the next would capture most of what the workload adds without measuring any workload.

What the workloads leave out

Located in full. Every pattern is reported at every occurrence, one φ step each. A query that wants only the first few occurrences asks fewer selects, of the values nearest wherever the walk starts.

One text, 32 copies. Every set is the same text copied 32 times with independent changes. A collection whose copies differ by shared edits, such as versions of one document, would put its run starts in different places, and how unequal the gaps are would change with it.

Sixteen characters. Shorter patterns occur more often within a copy and spread their occurrences over more gaps; longer ones occur about once a copy. The concentration on position nought does not depend on the length, but the diverged sets’ curves would.

The menu of spacings. The path chooses among t0t_0, 2t02t_0 and 4t04t_0, as before. A weighted path might want a spacing sparser than 4t04t_0 for chunks nobody asks, and was not offered one.

Still open: a weight read from the gaps

The workload’s weights on these sets are mostly the gaps’ lengths: a run start is asked once for each occurrence in the stretch of text it precedes, so on a uniform workload its expected weight is the length of that stretch over the text’s. A directory could be priced on those weights without any queries at all, since the gaps are known when the set is built.

The measurement that follows prices the directory with each value weighted by its gap to the next run start, on every set and rate, and compares it with the workload-priced directory on both workloads and on uniform selects. The prediction is that on all three sets the gap-priced directory reads within two bits of the workload-priced one on the workload, because the occurrences of any pattern are spread over the text in proportion to length, and that it gives up less on uniform selects than the workload-priced one does, since the gaps hold no accident of which patterns were asked. It could fail at 0.01, where the gaps are shortest and a pattern’s occurrences are not spread evenly, since a pattern that crosses a change does not occur in that copy at all, and the gap a change sits in is asked less than its length says. The question is whether the asking of an r-index can be read off its own structure, or whether the patterns themselves carry information the set cannot.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Query distributionR-indexRun-lengthSamplingSelectTrade off