The thread: Measured, not assumed — page 6
A bound right for the wrong reason
Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.
When the algorithm flips a coinTwo hash values and the keys they copy
A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.
When the algorithm is a tableThe classes held-out pairs cannot rule out
A substitution matrix can choose how many distinct costs it has as part of the fit: try all 203 ways of grouping its six pairs into classes and keep the one that best predicts pairs it was not fitted to. On corpora from a generator with two costs, that choice finds the two on about a third of resamples, and no more often at 3,200 pairs than at 50. A spurious split gains the same bit or two of fit at every size, and held-out scoring charges it a fixed price. A penalty that grows with the corpus finds the two every time, and finds a third class half a bit away from 400 pairs.
StructuresThe bill a partition only divides
The two predicted damages for any key sum to the same number under every partition — 967 arrivals here, whatever the arrangement. Round-robin hands nearly all of it to Misra-Gries and hashing hands most of it to Space-Saving, and neither of them is paying more than the other in total.
What is taught wronglyThe digest that promises nothing
The t-digest is the quantile structure most widely deployed and the only one with no proven bound on its rank error at any quantile. Measured, it beats the structure that does have one — and on two clusters with a gap between them it returns 431.5, where the data holds nothing at all between 40 and 800.
The index that replaces the textAn interval that grows at both ends
A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.
The data that is not a numberThe search that starts in the middle
The same pattern, the same six occurrences, the same index — and 830 interval extensions, or 303, according to which end the search begins at. A pattern cut into three pieces has an error-free one, and only a search with two ends can start there.
What a bound isThe cap an automaton cannot see
A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.
Two parametersTwo estimates that must agree
Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.
The floorsEvery pair must be asked
Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.
When the algorithm is a tableA checker that stops at two edits
A nearest-word search that must always answer pays most of its price on the queries whose answer is useless: misspellings of words the vocabulary does not have, whose nearest vocabulary word can be twenty edits away. Capping the answer at two edits keeps every suggestion a misspelt vocabulary word could get and costs 42% of the uncapped search. What it does not do is stop the false suggestions. It declines 95% of unfamiliar words of eleven letters or more and 1% of those of three or four, because two edits is most of a short word, and 72% of what it still says to an unfamiliar word is wrong — against 77% with no cap at all.
What is taught wronglyThe histogram that cannot see the order
A prediction accurate to one per cent on three streams is seven times out on the fourth, and the input that fails is the one every capacity plan is built from. A statistic computed from the same input says in advance which case is in hand — and misses one of the two ways it can go wrong.
StructuresThe shape that moves the bill
Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.
The index that replaces the textA block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
The data that is not a numberThe parse in one pass of the text
The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.
Two parametersOne Bellman–Ford buys every Dijkstra
A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.
The floorsThe floor a merge cannot reach
Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.
One pass, and no roomWhat a heavier tail actually buys
Four decays, each tuned until it is equally quiet on a stream with nothing happening, then given one burst. At a burst of three hundred they see it for 54, 63, 68 and 104 seconds — indistinguishable. At nine thousand the exact polynomial reaches 384 seconds and the exponential 156. The shape of a tail does not decide how far back a scheme can see. It decides how fast that distance grows with the size of the event, and the exchange rate is the reciprocal of the exponent.
When the algorithm is a tableA cost built from two properties
A substitution matrix fitted as a partition gives each class of pairs one cost, and the best number of classes can be chosen from the data. When the true costs are a sum of two terms — a transversion penalty and a graded difference between the letters — every pair costs something different, and the chosen partition's number of classes becomes a statement about the corpus: two classes at 25 sequence pairs, four at 200, five at 1,600. A model with the two terms and three parameters predicts a fresh corpus better than any partition at every size, and gets 191 of 200 alignments right from 50 pairs where the chosen partition needs 3,200. Told the wrong property it is worse than the plain two-class matrix, and nothing in its own fit says so.
What is taught wronglyThe boundary that hides the burst
A window whose blocks hold five hundred and twelve arrivals reports a perfectly even stream — every block the same duration to the tick — while the arrivals it is retiring have an index of dispersion of 0.57. Move the block to a hundred and twenty-five and the same stream varies by 1.8 times.
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.
The data that is not a numberA corpus that was not generated
Every collection in five strands has been copies of a generated text with a fraction of its characters replaced — three numbers, one dial. Here is one that was not — twelve essays, eight source modules, ten revisions of one file — measured beside the model of it.
The index that replaces the textDocuments that are not the same length
A separator per document costs a whole bit per character — on a generated collection whose alphabet is 21 symbols, where adding a few crosses 32. Real prose has 87 symbols and sits 41 short of the next power of two, so the same separators cost 0.04%.
Two parametersWhere the landmarks stand
Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.
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.
The floorsThe order inside a tie
Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.
One pass, and no roomThe moments past the second
Past the second moment no sign trick works, and the estimator that does — pick one position of the stream, count how often its key comes again, report m(r^k − (r − 1)^k) — is unbiased for every moment on every stream. Its variance can be computed exactly rather than sampled, and on real streams it is nowhere near its guarantee: 103 copies give F3 to ten per cent on a flat stream of 2,048 keys, and 2,630 on a moderately skewed one. The guarantee asks for 48,381, and it is not loose. One heavy key among 2,047 keys seen once needs 11,799.
When the algorithm is a tableThe triples a typo writes
A spelling checker capped at two edits keeps every correction it could make and still gives a false suggestion to 72% of the unfamiliar words it answers, because on short words distance cannot tell a typo of a vocabulary word from a word the vocabulary lacks. The query's letters were proposed as the second test: decline a query whose letter-triples the vocabulary has never seen. They cannot separate the two either. One edit writes about one unseen triple into any word, familiar or not, while an unfamiliar word brings 0.59 of its own, and two thirds bring none. Declining at two unseen triples removes a quarter of the false suggestions and costs half the corrections — twenty-two corrections for every false suggestion removed.
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 wronglyThe sampler that cannot alias
A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.