Relative error against bits of state, 50,000 distinct keys

Relative error against bits of state, 50,000 distinct keys

Each point is the root-mean-square relative error of 14 independent runs of one estimator at one state size, against a true cardinality of 50,000 counted exactly by a hash map the estimators never see. Both axes are logarithmic, so a power law is a straight line and its exponent is the slope: HyperLogLog at -0.49, LogLog at -0.44, bottom-k at -0.38. A slope of −½ is the 1/√m law, and it is what a floor of Ω(1/ε²) bits looks like from above. The best point drawn is HyperLogLog at 2.00% for 10,240 bits.

Drawn at 700 × 430, wide on the page. Everything above is what bits-against-error returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

2 essays call bits-against-error. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.