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

Median of means — where it appears

Averaging within groups and taking the median across them, which turns a bound on variance into a failure probability falling exponentially in the group count. It converts a variance bound into a failure probability, so more groups buy certainty exponentially and more samples per group buy accuracy only as a square root.

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

+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 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures

The estimate that is a median of means

An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.

randomness · Sketch 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 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 0.313103000.250.50.7511.251.52Zipf exponent s of the stream — 0 is flatvariance of one copy ÷ moment²sampling, F4sampling, F3sampling, F2signs, F22,048 keys, 60,000 items, exactdashed: tug-of-war

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.

streaming · Moment

Named alongside it

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

EstimatorRelative errorSketchState bitsUnbiased estimatorZipf distributionSecond frequency momentTug-of-warVarianceAdditive errorCount-Min sketchFailure probability

All concepts