Model — where it appears
Named by 8 essays across 6 fields — each of them below, with the objects they name alongside it.
The matrix a corpus wrote
A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.
The pass that was never a parameter
One pass is the streaming model's defining restriction, and this collection has enforced it by making a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.
A floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.
The floor charged at every level
A key surviving a fold of sixty-four shards is charged 2, then 8, then 20, then 43, then 88, then 248 — the floor of whatever summary it was merged against, level by level. They sum to 409, and the damage read off the merged table is 409. The model that charged sixty-three copies of the leaf floor said 222.
What the generated collection was right about
Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built.
The sort that makes none of them
Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.
A 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.
The dial that has no setting
The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.
Named alongside it
The objects these essays reach for when they reach for this one.
MeasurementCorpusHeavy hitterControlEdit distanceGenerated collectionGuaranteeHonest limitLower boundMerge treeMergeable summaryMisra–Gries