Measurement design — where it appears
Named by 30 essays across 9 fields — each of them below, with the objects they name alongside it.
What a reordering costs to undo
Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.
A distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate in these essays reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
Proportional to the answer, not the alphabet
At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.
The 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 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.
What 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.
The 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 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.
A result the size of its own noise
Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.
A detector that learns its own quiet
A burst detector built from a fast decayed counter needs a threshold, and the one it was measured with came from sixty independent runs of the background — an oracle no deployed system has. Two counters and a running mean square of their difference can supply it from the stream itself, and on a stream that does not move they hit a 5% false-alarm rate at every setting tried. What they lose is the burst: a scale that learns every reading learns the burst as noise and forgets it in 20 to 40 seconds whatever its size. Holding the scale while alarmed brings the oracle's horizon back for small bursts, turns a slow drift into an alarm that will not stop, and still cannot see past the lag at which the slow counter holds more of the burst than the fast one.
The record that forgets on purpose
A table of every pair selection sort might ask is 131,072 bits at 256 elements and catches every repeated question. A direct-mapped cache of 1,024 pairs is 16,384 bits and catches 91% of them, at a break-even of 3.53 word operations a comparison against the table's 3.12. What decides the cache is not how long the sort waits before asking again — 98% of its repeats come within one pass — but how many other questions it asks meanwhile, and a model with nothing in it but collisions predicts every measured share to within 2.6%.
Where a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
The clock a burst cannot outlast
A burst detector that holds its scale while alarmed keeps a burst visible to a ceiling set by two half-lives, and cannot stop alarming on a slow drift. The repair proposed for it was a schedule: learn again once an excursion has outlasted anything a burst could produce. Timed by how long the alarm has lasted, the schedule changes almost nothing, because on a gentle rise the alarm breaks every few seconds and the clock never reaches the ceiling. Timed by how long the difference between the counters has stayed positive, it keeps every burst to within about a second of the ceiling and falls below the target false-alarm rate on steep drifts — and one quantity, the drift's offset measured in spreads of the difference, says where it still fails.
The spread a merge sort does not have
On 65,536 random keys quicksort's comparison count has a standard deviation of 42,470 and merge sort's has one of 141.9 — three hundred times smaller, on means only a quarter apart. Merge sort's count is a fixed bill minus 65,535 independent leftovers, one per merge, each worth about a coin toss, so its spread grows as the square root of n where quicksort's grows as n. From 256 keys up a single run of merge sort pins its mean to one per cent, and a third of quicksort's whole spread is decided by its first pivot.
The repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
The slope the slow counter already shows
A burst detector built from a fast and a slow decayed counter reads a steady rise in its background as an offset in their difference, β(R − 1)H/ln 2, and alarms on it. Every repair so far waited the offset out. This one subtracts it: the slow counter's own change over one slow half-life is a reading of the slope, and the offset follows from it. At R = 16 the corrected detector alarms on 5.5% to 7.8% of readings on rises that make the held scale alarm on 11% to 63%, and it costs a burst at most 3.7 seconds of detection. The estimate has to be quick: four times slower, it has recovered only 71% of the offset when alarms start to count.
A placement after the traffic moved
Four landmarks fitted to twenty queries that all end at one cell expand two thirds of the corners' cells there. Move the destination ten cells and the advantage is gone; move it thirty and the fitted placement expands nearly twice the corners' cells. Choosing again costs 317,000 cells of search — the saving of 8,600 queries — so on streams whose destination drifts, a policy that refits on a counter never beats fitting once and keeping the result, and past a drift of about ten cells nothing fitted beats the corners.
The deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
The cell nobody filled
Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.
A refit that changes one landmark
Choosing four landmarks again after traffic moves costs hundreds of thousands of cells of search, and on drifting streams it never paid. Keeping three and re-choosing the fourth costs a fifth as much — 0.19 of a full selection, not the twelfth the earlier page guessed. On drifting streams, refitting on the counter goes from a loss of up to 13% to within 2% of fitting once, and it wins where the destination moves six cells. When the destination jumps, it is the cheapest policy measured, 12% under the corners at one jump in 10,000 queries — unless the jumps come as often as one in 2,500.
The order the column cannot see
A sort of rotations by their first four characters leaves ranges that agree on those four, and the full Burrows–Wheeler transform reads deeper to order them. Given a budget of characters below the transform's, spending it on the ranges whose rotations are preceded by the most different characters was predicted to reach within a hundredth of a bit at two thirds of the transform's reading — and spending it on the longest agreements, as the transform does, to waste it. The price was impossible: the four-character sort alone reads 76% of what the transform reads. The ranking was right on average, and right for a reason that makes the budget unnecessary: a range whose rotations are all preceded by one character writes the same run into the output in any order. Skipping every such range writes the transform's column exactly, on all sixteen streams, and reads 11% less on technical writing — up to 19% on the stream with the longest repeats.
What repetition is worth once the logarithm is gone
On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.
The question asked at every split
A range of rotations preceded throughout by one character writes the same run into the Burrows–Wheeler column in any order, and a sort that asked that once, of the ranges four characters leave, read 11% less than the transform. Asked at every split of a sort that partitions on one character at a time, it was predicted to read a fifth less on technical writing and an eighth less on the essays. It reads four fifths less — and nearly all of that is the change of sort, which the prediction expected to cost reading rather than save it. The question's own share, measured against the same sort without it, is 29% on technical writing and 14% on the essays.
A sort that infers the order
A radix quicksort that stops at every group of rotations preceded by one character reads about fourteen characters of a text for every symbol of its Burrows–Wheeler transform. Induced sorting, which reads the order of a third of the suffixes and derives the rest, was predicted to read three. It reads 6.1 on all sixteen streams, within 0.14 of each other, and the same at every length from a thousand characters to thirty-two thousand. The question the quicksort asks saves it nothing, as predicted, for a reason the prediction did not give: its last two passes read the transform's column itself, one character for every rotation, in order to sort.
A boundary that costs nothing
A separator occurs nowhere else in the collection, so it must break a phrase that would have spanned it. Cutting a repetitive text into a hundred and twenty-eight documents raises its run count by two per cent, and cutting prose raises it by ten.
The price of a boundary is what precedes it
A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.
One copy per document is one occurrence per document
The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.
A collection is a construction
The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.
A saving quoted without its collection
A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.
The collections the saving was quoted for
A document array compressed to the entropy of its own symbols saves exactly what the collection's length distribution allows, and the measurements that showed it used four constructed collections. The estimate they ended on — a directory of source files is roughly log-normal, so its array falls about a bit short of the plain one, around 17% — can be checked on a real directory. A project's 222 source files fall short by 0.66 bits and save 10.5%, a fifth of which is only the rounding of ⌈log₂ d⌉. Across six real collections the skew of the lengths is worth between nothing and 0.76 bits, and the log-normal formula overstates it wherever short documents are common.
Named alongside it
The objects these essays reach for when they reach for this one.
Honest limitCorpusBurrows-wheeler transformEntropyBits per symbolMove to frontContext modelDocument collectionVarianceComparison countRepetitionAlphabet size