Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Histogram — where it appears

A table of how many times each key arrived, with the order of the arrivals thrown away. It is what a capacity plan usually has about a stream, and it is enough to predict a summary's floor and a merge's damage — except where the discarded order is what decided them, as on a stream whose popular keys drift.

Named by 12 essays across 7 fields — each of them below, with the objects they name alongside it.

0231436845165232shards mergedkeys whose count movedthree orders:folded in one at a timecombined pairwise, in a treefolded in, last shard firstMisra-Gries, k = 32 · hashedworst gap 298 arrivals

What a fold charges per level

Thirty-two counter tables folded in a chain come out wrong by 323 where the same thirty-two combined pairwise are wrong by 148, and the quantile summaries prefer the chain by exactly as much in the other direction. What is being charged in each case is the depth of the fold, and the two families are charged on opposite ones.

bounds · Merge shard 1 · 120 → 119shard 2 · 121 → 120shard 3 · 120 → 120shard 4 · 121 → 120shard 5 · 119 → 118shard 6 · 124 → 123shard 7 · 121 → 120shard 8 · 122 → 121floor, in arrivalsnaive: tail ÷ kfixed pointmeasuredstationary Zipf · round · k = 321.006× the measured floor

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.

streaming · Merge 010020030040021φ 382φ 7203φ 17434φ 42885φ 1012486φ 242measured 409counts chargedlevel of the foldcharged at this levelrunning total64 shards · k = 32 · hashedcharged 409 · measured 409

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.

floors · Floor 0.111010010³10³10⁴floor, in countsarrivals in the shard, nround-robin — n^1.02hashed — fit refusedresidual 2.7%slope 5.2 → 1.19k = 32 · 40,000 arrivalsthe table holds 1.33 of a hashed shard's keys and 0.01 of the stream's

A floor with two variables in it

Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.

floors · Floor depth 0190.1%depth 19642.9%depth 24,92915.0%depth 37,00921.4%depth 48,47325.9%depth 56,24119.0%depth 63,31010.1%depth 71,2503.8%depth 84221.3%depth 91240.4%depth 10270.1%positions32,768 characters · 1172 phrasesmean 3.98

The number that would choose a cap

A depth histogram is one linear pass — 3.16 operations a character over thirty-two thousand of them — and it says the whole text sits at a mean depth of 3.98 with a worst of ten. Nobody prints it, and every choice of cap in this collection was made without it.

practice · Parse f = 6,3628/8 holdingf = 3,0748/8 holdingf = 1,9638/8 holdingf = 1,3738/8 holdingf = 1,0988/8 holdingf = 9353/8 holdingf = 7690/8 holdingf = 6560/8 holdingpredicted damage, in arrivals — every row totals 967Space-Saving's shareMisra-Gries's share8 shards · round · k = 32bill 967 arrivals

The 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.

structures · Merge 0.000.250.500.751.00stationarydepartingburstydriftingprediction ÷ measurement, as a factorshare of the top k that moves between halves8 shards · round · k = 327.1× out where the statistic reads 1.00

The 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.

wrong · Merge 0.60.81.01.21.41.61.84φ share 0.908φ share 0.8516φ share 0.8032φ share 0.7564φ share 0.70predicted ÷ measuredshards, mlevel floors, uncorrectedleaf floorslevel floors, correctedk = 32 · hashed · 40,000 arrivalsworst 22% against 73% and 46%

The floor a merge does not settle at

Compute a fold's level floors from the shard histograms and the prediction over-shoots by 1.73. A merged summary's floor is not the floor a summary settles at on the same arrivals — it is 0.90 of it at four shards and 0.70 at sixty-four, straight in log₂ m at a 3% residual, because merging preserves the heavy counters and never runs their eviction cascade.

wrong · Merge how far the top k movedthe order warninghow far the floors are from doublingthe regime warningstationary Zipf0.160.53 (54%)one key floods a stretch0.170.59 (54%)a heavy hitter that stops0.170.65 (52%)the popular keys drift0.9134.00 (0%)k = 32 · 40,000 arrivalsin brackets: the leaf model at sixty-four shards

The 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.

wrong · Merge 02468101214mean 5.71depthshare of the collectionten revisionstwelve essays75,658 characters · 2,966 phrasesworst 14, mean 5.71

The shape of a real history's depth

Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.

text · Parse 05101520510revisions in the collectiondepthone revision alone: 8worst depthmean depthfourteen revisions of another9 generations added exactly one

One revision, one level

The cap ladder assumed depth is generations of copying. On a real file it is exactly that — one more revision, one more level, nine times running — plus eight levels the first revision already had before any history existed.

structures · Parse 73 characters long24 runsto depth 7270 characters long24 runsto depth 69longest: 73 × "-" at position 11,0162,685 positions below depth 20, 2,685 of them inside a runeight source modules · worst depth 78100.0% in runs

The deepest text is punctuation

Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.

wrong · Parse

Named alongside it

The objects these essays reach for when they reach for this one.

PartitionShardSpace-savingFixed pointMeasurementHeavy hitterMerge treeEstimatorExtractionGuaranteeHonest limitMergeable summary

All concepts