The thread: Two counts, two rankings — page 2
The shift somebody published
The exact rules for shifting a multi-pattern window are a definition that quantifies over every pattern at every offset. The 1979 rules are two tables read off the trie's own failure links, they are computed in one pass, and on this pattern set they agree with the definition at every node.
The index that replaces the textThe collection decides which index is small
Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.
What a bound isThe branch that cannot reach an answer
Seventy-two rank operations over the pattern remove 27,906 of the 39,957 interval extensions a bounded-error index walk performs — 70% of the tree, at a budget of three. The share grows with the budget, which is what a pruning has to do to be worth its cost.
StructuresA sketch that is allowed to be under
Count-Min's estimate is never below the truth, and it pays for that with an error proportional to the whole stream. Give every key a sign and take a median instead, and the same table is 2.7 times more accurate on the keys anybody asks about — and wrong in both directions.
The other axisEvery occurrence at the same price
A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.
CountingThe sort whose count has no distribution
Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.
StructuresThe counter that takes the smallest slot
Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.
CountingThe order equal keys keep
Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.
The other axisA bound that has to be paid for
The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.
StructuresThe fold that minimises the wrong thing
A fold charges per level and a survivor pays the cuts on its path, so the bill looks like a weighted external path length — and Huffman's construction minimises that quantity by proof. Built and measured on thirty-two uneven shards it does minimise it, 181,407 against a balanced tree's 200,000, and leaves more damage than the tree does.
CountingThe questions a sort asks twice
Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.
StructuresThe shape one structure will not fold
Folding thirty-two shards largest-pair-first keeps 2,556 quantile tuples against a balanced tree's 3,211 — a fifth of the space saved. The same fold on the counter tables beside them leaves 403 counts of error against the tree's 148. A deployment holding both cannot fold once and be right twice.
What is taught wronglyA parameter that waits for another
Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.
What is taught wronglyThe warning that is silent for the right reason
The statistic shipped to warn that a merge prediction is about to fail reads 0.160 on a stationary stream, 0.172 on a bursty one and 0.909 on a drifting one. It was asked to be looked at again because it does not catch a burst. It does not, and the reason is that on a burst there is nothing to catch.
CountingThe record measured where it would run
A table of every pair selection sort has compared saves half its comparisons at 1,024 keys, and priced in word operations it was the better record at every size. Replayed through a 32 KB cache it misses 477,824 times to save 258,290 comparisons — nearly two misses for every comparison it removes — while a cache of 1,024 pairs misses 192. The table's size is not the problem. Its layout is: it looks up and writes each question at [key][minimum], a new row every time. Indexed by the ordered pair instead, the same bits miss 3,079 times, and that repair works only for a sort whose smaller operand stays put.
CountingA record the size of a pass's minima
Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.
CountingA record of stretches, not pairs
Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.
What is taught wronglyThree savings in three currencies
The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.
CountingTwo swaps a pass, and the stretches hold
Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.
CountingA run answers what nobody asked
Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.
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.
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 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.
CountingA pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
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.
CountingThe runs too short to drop
A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.
What is taught wronglyThe ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
What the machine doesThe count that was already there
A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.
What the machine doesTwenty bits apart
Two representations of one sparse set, six thousand seven hundred and forty-five bits against six thousand seven hundred and sixty-five. One exploits sparsity and the other exploits runs, and on this set at this density they price identically.
What the machine doesWhat a character costs on four machines
Forty-four operations, one, forty-two, and a number that moves. Four machines for one language, with the construction charged separately from the steps, because a machine that is free per character paid eleven thousand operations before the first one.