Space accounting — where it appears
Named by 28 essays across 8 fields — each of them below, with the objects they name alongside it.
The filter each run carries
A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.
The keys that arrive late
Insert 131,072 keys into a B+-tree in random order and its leaves end up 70.5% full; in ascending order, 51.6%; in descending order, 50.0%. The rule databases use to fix ascending inserts — split a full leaf at its right-hand end — fills them completely, and it does nothing for descending keys. Let one key in a hundred arrive late in an otherwise ascending stream and the rule's leaves fall from 100% to 53.4% full. How much of an index is empty is decided by the order its keys arrived in, and a trickle of disorder undoes the fix.
A key passed along the row
A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.
The 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.
Six 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.
A 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.
One bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.
The 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.
A division chosen before the queries arrive
A levelled store's range-filter memory, divided among its levels by trying every assignment against the store's own queries, captures 99% of a perfect filter's saving on both arrival orders, with the small levels at twelve to sixteen bits a key and the deepest at one. A store writing a level cannot try every assignment, but it knows its levels' sizes, and a rule giving each level δ more bits a key for every factor of four it is smaller was predicted to match the fitted division on the shuffled store and to land near the even split's 94% on the store filled a cluster at a time. It matches the fitted division on both: 97.2% to 99.0% shuffled and 99.7% to 99.9% filled a cluster at a time from one bit a key up, with δ chosen on a sample of queries and charged on others. One δ of four, set before any query, is within a point and a half everywhere from one bit a key up. The rule fails exactly where the proposal said: a δ of six or more at one bit a key gives the deepest level nothing, and the shuffled store falls from 97.2% to 73.9%.
A 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.
The sizes a store passes through
A levelled store's range-filter memory can be divided by its levels' sizes alone, a few more bits a key for every factor of four a level is smaller than the deepest, and on the full store that rule matched the division fitted to the store's own queries at every budget. Through the fill it does not. At a bit a key or less it falls up to 17 points of a perfect filter's saving behind on the shuffled store and 26 on the store filled a cluster at a time, and every large loss has the same cause: part way through the fill the deepest level is a smaller share of the store, and the rule gives it nothing.
A 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.
A floor under every level
A levelled store's filter memory divided by its levels' sizes lost up to 26 points of a perfect filter's saving part way through its fill, every large loss a level given no filter at all. A floor of half a bit a key under every level was predicted to close every gap above five points at one bit a key and cost nothing at two and four. It closes them: the worst gap at one bit falls from 17 points to 4 on the shuffled store and from 25 to under 1 on the clustered one, and nothing moves at two bits and up. At half a bit a key the floor is the whole budget and the rule becomes the even split, which the clustered store wants half way through and the shuffled store, at the same sizes, loses 35 points by.
A span the queries do not see
A rule for dividing a levelled store's range-filter memory by its levels' sizes, with a floor of half a bit a key, came within five points of the division fitted to the store's own queries at every budget from one bit up — but at half a bit the shuffled and the clustered store wanted opposite divisions of identically sized levels. A level's fences, its first and last keys, say how much of the key space it spans, and a clustered level spans little. Scaling each level's bits by that span was predicted to close the half-bit gap and change nothing above. It changes nothing at half a bit — where the floor is the whole budget, so there is nothing left to scale — and from one bit up it puts the clustered store 30 points behind the fitted division, where the floored rule was within one. A level holding one cluster spans 0.4% of the key space and meets 4.4% of the queries, because half of them start at a stored key: the fences measure the key space, and the queries are aimed at the keys.
The array that says where is twice the samples
An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.
The apparatus, three times smaller again
Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.
What the locating apparatus becomes
The two parts that answer "where" are half an index at a dense sampling and a fifth at a sparse one, and the fifth does not fall further. Represent the marks properly and it keeps falling, to under four per cent.
The ladder, and the rung that spends
Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.
The floor was the marks
A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.
Bits and steps on one frame
The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.
Half an index is three permutations
A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.
A constant factor, not a term
The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.
Entries found by the rank of their tag
A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.
The slack an insertion can reach
A cuckoo table whose entries are packed by tag rank holds half the bytes of a slotted one at half load, and pays by shifting entries on every insertion. It was proposed to keep a few spare entries at the end of each group's region. Charged the copies a full region costs, that slack helps only with the copies: at groups of 16 buckets an insertion still moves over a thousand bytes, against 36 for slots. The same slack divided among the buckets, with an insertion borrowing the nearest free entry, moves 347 — and the group size, which multiplied every earlier cost, stops mattering.
Spare where a bucket can use it
A cuckoo table packed by tag rank keeps a few spare entries in each region of sixteen buckets, and every time a region runs out it divides its spare among the buckets again. Divided evenly, most of the spare ends up in buckets that are already full, which never grow — they kick. Divided in proportion to where insertions have been landing, as proposed, more of it does, and an insertion at 90% load moves 1,159 bytes against 1,005. Divided by the room each bucket has left, only 3% of it is stranded, and at 95% load an insertion moves 10 to 17% less than with an even division. None of the three comes near the half-load figure, because all of the growth from half load to 90% is the cuckoo kicks' own cost.
The keys a capped chain leaves behind
At 95% load five sixths of the bytes a packed cuckoo table moves on an insertion are its kick chain, and the chain is mostly tail: capping it at two kicks removes 72% of the kicks. The proposal was to put the key still displaced into an overflow held in its region's spare, and it predicted that the bytes moved would halve. They fall by 13%. A key placed in the spare costs 1,819 bytes to insert, six kicks' worth, because the free slot nearest the region's end is far away and every entry between moves. The same cap with the overflow in a separate block halves the bytes as predicted, for a byte a key and an overflow that every failed lookup has to read.
The lookups a filter turns away
A capped cuckoo table keeps its stopped keys in an overflow block a region, and at 95% load every lookup for an absent key reads those blocks — 1.93 of them, because a key could have been stopped in either of its buckets' regions. A Bloom filter over each region's overflow at eight bits a key was predicted to let about 2% of those lookups through. It lets 2.07% through, and the prediction was right for two wrong reasons that cancel. Filing every stopped key under its first bucket halves the rest, and then the lookups the filter cannot help, the 3.9% of keys that really live in the overflow, are what is left to pay.
Room the chains could not reach
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys outside their buckets while 13.8% of its entries stand empty. Keeping a few entries in each region aside for the keys the cap stops, at the same memory, was predicted to remove most of the overflow for a tenth of a kick an insertion. It removes none of it: the share outside the buckets stays at 9.2% with up to eight entries kept back, because a key is stopped by the pair of buckets its chain visits, never by a region short of room. What the reserve changes is where the stopped keys sit, and that is worth having. Read with the region's header, four entries a region take the overflow blocks from 9.2% of keys to 6.1% when keys stay and from 4.9% to 2.3% when keys go home with an open block, for no kick anyone can measure — until the reserve takes room the chains were using, at sixteen entries when keys stay and at eight when they go home.
Named alongside it
The objects these essays reach for when they reach for this one.
Index sizeDesign parameterBidirectional indexPredictionBloom filterHonest limitMeasured countWavelet treeCompressed bit vectorCuckoo hashingHash tableLoad factor