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

Unbiased estimator — where it appears

An estimator whose expectation over its own randomness is the true value, which says nothing about how far any single run lands from it. A single run can be far from the truth while the estimator is unbiased, which is why a variance or a concentration bound is the second half of the claim.

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

1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits

The answer that is allowed to be wrong

Every algorithm on this site so far was checked for correctness before it was measured. A summary of a stream cannot be — the data goes past once and does not fit — so the error becomes a resource, bought with bits, at an exchange rate that is a measurement.

streaming · Sketch 0.1bits the register neededrelative errora = 2a = 1.5a = 1.2a = 1.1a = 1.05a = 1.02√((a−1)/2), predicted200 runs per base · n = 20,000 · exact counter needs 15 bits72.6% at 5 bits

Counting past what the register holds

Morris's counter counts ten million events in five bits by incrementing with probability 2 to the minus c. The estimate is exactly unbiased at every n, its relative error is 71%, and the base is a dial that trades one against the other at a rate of the square root of half of a minus one.

streaming · Sketch exact-11.2%-3.3%0.0%3.3%11.2%rmse 3.61%worst 9.71%23 of 60outside the band5,120 bits · 60 seeds · relative error of one runpredicted ±3.25%

The correction that makes it work

HyperLogLog and LogLog read the same registers and differ only in how they average them. The harmonic mean is worth 30% of the error for nothing, and below two and a half registers' worth of keys the estimator both are built on is 137% high and has to be abandoned.

streaming · Cardinality +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 1 coefficient13 members2 coefficients169 members3 coefficients2,197 members4 coefficients28,561 members1 key2 keys3 keys4 keys5 keysexact92% gone99% gone100% gone100% goneexactexact92% gone99% gone100% goneexactexactexact92% gone99% goneexactexactexactexact92% goneevery member walked · GF(13) · no tolerance and no seeddegree 1, 2, 3, 4

The independence an estimator spends

Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.

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

Named alongside it

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

EstimatorSketchRelative errorState bitsVarianceMedian of meansSecond frequency momentStreaming algorithmTug-of-warCardinalityCount-Min sketchEstimator bias

All concepts