Every essay — page 13
What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search
One pass, and no room
The data goes past once and there is not room to keep it. What survives is a summary of a few hundred bits, and the answer it gives is wrong — the whole design is a choice about how wrong, and every structure here buys accuracy with bits at a rate that can be measured.
An error measured against the answer
A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.
The floor a histogram already knows
A summary of thirty-two counters settles at a smallest counter of 119, and the number can be computed from the shard's key frequencies before a single counter is allocated. The obvious way to compute it is wrong by a factor of two, and the reason is that the heavy counters carry no error at all.
The tuples a merge does not give back
A merge of thirty-two quantile summaries keeps seven times the tuples of one summary over the same values, and sixty-four keeps ten and a half. Fitted across the sweep the count goes as the shard number to the power 0.56, which answers what it converges to — it does not.
The window that is even in the wrong currency
A window of four thousand arrivals in eight blocks retires a block every 5.1 seconds on a steady stream and anywhere between 0.57 and 14.8 seconds on a stream whose rate moves. The structure cannot tell, because it is counting arrivals, and the alert written against it is in seconds.
The period that is not a promise
Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
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 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.
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 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 keys worth counting before sampling
The sampling estimator for the third frequency moment spends most of its copies on keys that barely contribute to the answer. Finding the heavy keys first with a Count-Sketch, counting them, and sampling only the rest cuts the state for ten per cent from 5,260 words to about 1,500 on a moderately skewed stream, and from 23,598 to under a thousand on the stream built to be worst for the sampler. It costs five times more than it saves on a flat stream, where there is no heavy key to find. What decides it is how the frequencies are shaped, not how long the stream is, and the frequencies must be counted, not read off the sketch, because the sketch's error on a heavy key is cubed.
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.
The rise the correction kept subtracting
A burst detector that subtracts a rising background's offset, read off its own slow counter, goes on subtracting it after the rise has stopped. The prediction was a deficit for about one slow half-life that would cost bursts of 300 arrivals. Measured, the deficit is deeper and longer: down to 1.46 spreads below zero, below half a spread for seventeen minutes after a 40% rise. Bursts of 300 are never missed. What the deficit costs is small bursts — 30 arrivals caught 27% of the time where the rise saw 77% — and a fifth of a large burst's visible time.
A share of a list of equals
Estimating the third frequency moment by finding the heavy keys first and sampling the rest works best with one counted candidate on steep streams and sixteen at Zipf 0.5, and a system that does not know its stream's skew has to pick. Keeping a long list and counting a candidate only if it holds a stated share of the list's own moment was predicted to come within a few per cent of the best fixed list on every exponent. The share does choose: at 3% it keeps one candidate at Zipf 2, three at Zipf 1, five at Zipf 0.5. But a list the stream shortens is not a short list. Its sixty-four candidates cost 192 words on every stream, four times the whole of the best estimator on the steep ones. On a flat stream every candidate is a near-equal share of a list of equals, and no share can tell that none of them is heavy. No list length and share comes within 10% everywhere; at Zipf 0.5 alone, the chosen list beats every fixed one.
A list that gives back its places
An estimator of the third frequency moment keeps a list of candidate heavy keys beside a Count-Sketch and samples the rest, and cutting a long list at the end of the pass to the candidates that hold a share of its moment picked the right keys and paid for the whole list. Dropping a candidate during the pass, as soon as it falls below that share, was predicted to make the list's memory follow the stream: under four candidates on steep streams, within a fifth of the best fixed list, and about ten on Zipf 0.5 with most of the earlier win kept. The list ends the pass the right length — three candidates on Zipf 1 — but its memory is its peak, and the peak is set by the twenty-fifth arrival, before any key has stood out: nineteen candidates on Zipf 1, and on flatter streams the most a share θ allows, one over θ. Charged its peak, it beats the end-of-pass cut on every stream from Zipf 0.75 up, 208 words against 364 at Zipf 1, and never reaches the best fixed list, 159.
A check as slow as what it checks
A burst detector that subtracts a rising background's offset goes on subtracting it after the rise ends, and loses small bursts in the trough that opens. Capping the subtraction by what the difference itself shows, averaged over one slow half-life, was predicted to close the trough to under half a spread. It lifts it from 1.46 spreads to 1.24, because that average is as late as the estimate it checks. Averaged over a quarter of the time it lifts it to 0.70 and catches small bursts in the trough more often than any other design but the one that alarms on a fifth of its readings. Neither cap helps after a large burst, which every slope correction reads as a rise.
A variance that had seen one hash
A budget of 40,960 bits split between a HyperLogLog and a bottom-k sample answers an intersection best by weighting the two estimates by their variances, except in one corner: a sample of 160 hashes asked about sets sharing one key in a thousand, where the weighting's worst regret was 4.46. The sample was said to see nothing, report a variance of nought and be believed completely. Its variance was never nought — it was taken at one shared hash whenever none was seen — and it was believed too little, not too much. Half a shared hash in the variance gives the sample more weight and cuts the corner's regret to 3.08, not under the 2.5 predicted; half a hash in the estimate too gives 3.74 there, and 1.61 at five eighths of the budget in registers, the lowest worst regret any split and rule has reached. No weighting measured gets the corner under the sample's own 2.30: 160 hashes expecting a sixth of a shared one is a limit, not a formula.
Structures
Heaps, trees, hash tables and dynamic arrays — each with its advertised bound put through the same measurement as everything else here.
What amortised means
Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.
Choosing a growth factor
When a dynamic array fills up, how much bigger should the new one be? Doubling costs 2.02 units per append and leaves 39% of the allocation empty. Growing by an eighth costs 9.89 and leaves 10%. Every factor is a trade between time and space, no factor wins on both, and real implementations disagree about the answer for reasons that are measurable.
The order nobody fixed
The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.
The tree that is a list
A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.
Building a heap from the bottom
Bottom-up heap construction is Θ(n) and repeated insertion is Θ(n log n), and the second of those is a worst case quoted as a behaviour. On random input, repeated insertion measures linear too — 2.22 comparisons per element against 1.87 — and the famous logarithmic factor never appears. On ascending input it appears in full, and it is a factor of six.
The priority nobody supplied
Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.
The probe nobody waits for
Robin Hood hashing makes an inserting key steal a slot from a key that has probed less far. The mean number of probes afterwards is 4.817, and before it was 4.817 — identical, and it cannot be otherwise, because the total displacement is fixed by the hash. What changes is the worst case, from 114 slots from home to 19, and a table reported by its average lookup cost shows no difference at all.
A bucket that becomes a tree
Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.
A tree with nodes the size of a block
A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.
The index that is the text
A suffix array sorts all 4,097 suffixes of a text — 8.4 million characters of string, in total — and examines exactly zero characters doing it. It then answers a search in 91 characters where a scan costs 1,472, and the whole thing pays for itself at six queries. Both halves of that are worth the same amount of attention, and the first is the one that is usually skipped.
The items that survive k counters
Misra-Gries keeps k counters, decrements all of them on a miss, and never returns a count above the truth — with no hashing, no randomness and no failure probability. At equal state it is more accurate than the randomised sketch on the question both are usually asked, at every size measured.
The summaries that add
Two sketches built over two streams and merged are, for three of the four structures here, byte for byte the summary the concatenated stream would have produced. For the fourth the guarantee survives and the state does not, and calling both properties mergeability hides the difference that matters.
Every substring, in fewer states than substrings
A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.