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

Morris's counter — where it appears

An approximate counter incrementing with probability a to the minus c, so a register holding log log n bits estimates a count of n unbiasedly. Its base is an accuracy dial: a base nearer one costs more bits and gives a tighter estimate, and the error is a distribution rather than a bracket.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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

Named alongside it

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

EstimatorEstimator biasRelative errorSketchUnbiased estimatorCardinalityClosed formHarmonic meanHyperLogLogLeading zerosLinear countingRandom bits

All concepts