The thread: An index has a size — page 2
Two bits a value, and what undoes them
The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.
The data that is not a numberA million characters of the same thing
Every measurement this collection has published about real text was taken on twenty-four thousand characters, because the phrase count was quadratic. It is linear now, so here is the same corpus at forty times the size — and what forty times does to its own numbers.
StructuresA rectangle over a permutation
Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.
The other axisThe structure that was supposed to halve
A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it.
The other axisA bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
The index that replaces the textTwo thousand documents of two hundred characters
Every collection this field has measured has been a dozen documents of ten thousand characters. A real collection is usually the other shape, and the other shape moves every term in a document index — one of them by a factor of seventy.
What the libraries doThe crossing that never arrives
Output-sensitive document listing exists because a pattern can occur four thousand times in eight documents. On a real collection of two thousand short documents it occurs 1.04 times per document, and the whole apparatus buys nothing at all.
What is taught wronglyA sampling that costs more than the array
On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.
When it does not fitThe small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
When it does not fitThe resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
The data that is not a numberThe array is the length distribution
The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.
When it does not fitOne length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
The index that replaces the textThe half that is never asked where
A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.
The data that is not a numberThe part every saving left alone
A bidirectional index was made smaller three times, one part at a time, and every change left the largest part untouched: the wavelet trees, whose levels are two thirds of the structure. Coding every level in blocks of 63 bits — how many ones a block holds and which arrangement it is — takes that protein index from 210,934 bits to 167,707, a larger step than the two before it together. On English words it takes the same structure from 210,872 bits to 76,054, and an ordered tree, coded, ends up smaller than an unordered Huffman tree, plain. Every rank then reads 1.4 times as many entries, and a smaller superblock buys the reads back for part of the bits.
When it does not fitTwo lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
What is taught wronglyThe operations a candidate count leaves out
The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.
The other axisAn index that cannot locate
Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.
The data that is not a numberSix bits a class
Coding a bidirectional index's wavelet-tree levels in blocks left a part that did not shrink: six bits a block for the block's class, its count of ones, which on English words became a quarter of the levels. Coding the classes by their runs was predicted to halve them. It takes a third off, 0.480 bits a character to 0.323, because two thirds of the blocks are uniform but they come in stretches of about two. One entropy code over the classes does about as well, and on the repetitive collection better. Runs also cut the reads a rank makes by 15%. On random letters runs make the classes larger, and the pointer a variable-length stream needs at every superblock eats most of what an entropy code saves.
When it does not fitThe filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
What is taught wronglyA sixth of what, exactly
The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.
The data that is not a numberA flag for the blocks that change once
A coded wavelet-tree level stores each mixed 63-bit block as the index of its arrangement, as if every arrangement were equally likely. Coding it instead as the gaps between its value changes was predicted to take a third off the offsets on English words. Alone it adds 4%: a third of the mixed blocks change value once, as predicted, but most of the rest change twenty times or more. A one-bit flag that lets each block take the shorter code takes 21% off, and the levels fall from 1.72 bits a character to 1.45. On the repetitive collection the offsets halve.
What the libraries doThe saving, spent
A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.
The data that is not a numberThe optimum the flag took away
A bidirectional index's wavelet-tree levels were coded in blocks of 63 bits because a sweep found 63 the best length: shorter blocks pay for more classes, longer ones for offsets that approach the block's own length. Then the classes were coded as runs and each offset given a flag to choose a code of its value changes instead. Lengthening the blocks to 127 bits was predicted to save on English words and the repetitive collection and to change nothing on random letters. It saves on all four texts, and there is no best length short of 1,023 bits on three of them: English words fall from 1.431 bits a character at 63 to 1.304 at 1,023. Under the codings the optimum came from, the same levels cost 3.728 at 1,023. The flag turned a long block's offset into the cost of its change points, which no block length moves, and left the length to be set by the one thing still growing with it: the work of a rank.
The index that replaces the textEvery child at once
A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.
The data that is not a numberA flag that weighs the work as well as the bits
A wavelet-tree level's mixed blocks are each coded by their arrangement's index or by the gaps between their value changes, a flag choosing the shorter, and longer blocks then save bits on every text at the price of more work a rank. Charging the flag for decoding work as well as bits was predicted to reach the same curve as shortening the block, and to beat it by no more than a hundredth of a bit a character. On English words, DNA and protein it reaches nothing below that curve. On the repetitive collection it reaches 0.156 bits a character below it: 1,023-bit blocks with a price on work cost 0.458 bits a character for less work a rank than 63-bit blocks do at 0.607. The difference is in which blocks the flag codes by their arrangement — on English words blocks that change value ninety-six times, on the repetitive collection blocks holding one short run of ones in two hundred and fifty-five bits.
What is taught wronglyThe occurrences a join invents
Eight documents run together hold forty-nine eight-character windows that span a join, twenty-three of which occur in no document at all. Every index built over the concatenation reports them, and five essays of this collection paid that cost silently.
The data that is not a numberA price the levels share
A bidirectional index's wavelet-tree levels code each mixed block by its arrangement or by its gaps, and a flag that charges each code for the work a rank costs inside it reached below the curve the block lengths draw on one text of four. Setting that price separately for each level of the tree was predicted to find a few hundredths of a bit on English words, where the deep levels hold runs. It finds nothing on any text: under a ten-thousandth of a bit beyond one shared price. The price a block wants is set by the text, not by the depth of the node it sits in, and every level holds a fifth of the index.
StructuresThe tree the operation insists on
The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.
The data that is not a numberThe blocks the searches ask for
A flag that codes each block of an index's wavelet-tree levels as an arrangement or a gap code, charged for the work a rank does inside the block, was priced as if ranks landed on every position equally, and a price for each level found nothing that one price did not. Pattern searches do not ask evenly: on English words the busiest tenth of the blocks takes 22% of their ranks, and 35% when common patterns are asked more. Priced by the work of the ranks that actually land in each block, chosen on one sample of searches and charged on another, the flag reaches 0.11 to 0.16 bits a character below the old pricing at the same work on English, and 0.03 on the repetitive collection.
What a bound isA factor of fourteen, for four per cent
The compound walk removes a factor of σ from every interval extension. It requires a tree whose leaves are in order, which costs between nothing and five per cent of the wavelet tree. Both numbers on one plate, and the trade is not close.