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

Zipf distribution — where it appears

A frequency distribution in which a key's count falls as a power of its rank, so a few keys carry most of a stream and most keys occur once or twice. It is what makes heavy hitters exist at all, and it is why a summary tested on a uniform stream reports numbers no deployment will see.

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

one summary, k = 32769one summary, k = 25608 summaries of 32, merged536worst error over the top keys, in arrivalsconcentration 1.00 — the mean share of a heavy key held by one shard8 shards · hashed · balancedmerge 536 against matched 0

The state a merge is standing in for

A merge of eight summaries of thirty-two counters is wrong by 536 where one summary of thirty-two is wrong by 769, which reads as merging helping. One summary of two hundred and fifty-six counters — exactly what the eight were holding between them — is wrong by nothing at all.

streaming · Merge 313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards

The partition the analysis did not mention

Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.

streaming · Merge hash rowh1h2h3h4h1 → cell 30: 10,433h2 → cell 29: 10,624h3 → cell 19: 10,575h4 → cell 4: 10,895key 0 occurred 9,579 times · the minimum of the four is 10,433 · over by 854the additive bound at this width is e/w × N = 5,0974×32 counters · 4,096 bits · Zipf s = 1.1exact would take 162,288 bits

A count that is never under

The Count-Min sketch holds four rows of counters and answers how often a key occurred. Its error is one-sided with no probability attached — the estimate is never below the truth on any stream — and the probabilistic half of its guarantee is only about how far above.

streaming · Sketch +1−1keys, most frequent firstΣ s(x)·f(x) = 9,034squared: 81,613,156true F2: 36,931,352121.0% outa polynomial of degree 4 · cash-register model · counts exactone register, 32 bits

The estimate that squares the stream

The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.

streaming · Moment 1101001,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions4.11% to 34100%

The guarantee that is one query wide

A sketch described as accurate to within a per cent is accurate to within a per cent of the whole stream, not of the number asked about. On a skewed stream the same sketch is 4% wrong about its heaviest key and 34,100% wrong about one of its rarest, and both figures satisfy the bound.

wrong · Sketch key 05,416short by 4,163key 1462short by 4,154key 31short by 2,099key 71short by 943key 19401short by 3counter held (bar) against true count (tick)12 counters · 768 bits · no randomnessbound N/(k+1) = 4,615

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.

structures · Sketch 1×2×5×10×20×50×00.40.811.2skew of the join columnratio, logarithmicestimate off byregret, decided partregret, whole planR 4,000, S 40,000, T 2,000 rows, B = 64, M = 4,096 (M/B = 64)every order writes the same output

The join order is a guess

Three tables, two orders, and an estimate of the first intermediate result that assumes the join column is uniform. When the column is skewed the estimate is out by seventy-two times, and the plan chosen on it costs 1.49 times the better one — which sounds tolerable until the shared output is taken away, and the part of the cost the order actually decided turns out to be 43.9 times worse.

applied · Transfer 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 1×2×5×10×20×50×100×200×00.250.50.7511.251.51.752skew of the join columnregret of the decided part, logarithmicuniform estimate4 counters a side16 counters a side64 counters a side256 counters a sideR 4,000, S 40,000, T 2,000 rows · 64-record blocks, 4,096 in memoryMisra–Gries on each side of the join column

The skew a few counters cannot repair

A join order chosen on the textbook estimate costs 243.9 times the better order at a Zipf exponent of two, and two counters a side are enough to fix it. At an exponent of one half the estimate is out by less than a factor of two, the plan it picks costs 1.37 times the better one, and no number of counters up to 256 changes that. The easy case is the extreme one, and the reason the moderate one is hard is a series that stops converging at exactly one half.

applied · Transfer 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 Count-Min 4×64exact0 under200 overrms 303Count-Sketch 4×64-2,774-1,38701,3872,774120 under80 overrms 256cash register · insertions only, Zipf s = 1.1 · counts exact8,192 bits each

A sketch that is allowed to be under

Count-Min's estimate is never below the truth, and it pays for that with an error proportional to the whole stream. Give every key a sign and take a median instead, and the same table is 2.7 times more accurate on the keys anybody asks about — and wrong in both directions.

structures · Moment 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

Named alongside it

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

EstimatorHeavy hitterMisra–GriesState bitsGuaranteeSketchShardSpace-savingAdditive errorCount-Min sketchMergeable summaryOne-sided error

All concepts