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

Harmonic mean — where it appears

The reciprocal of the mean of reciprocals, which bounds the influence of a large outlier and is what separates HyperLogLog from LogLog. Replacing a geometric mean with it is the whole difference between two published estimators, and it is worth a measurable factor rather than a constant nobody notices.

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

Also named here as leading zeros, stochastic averaging — the same set of essays touches all of them, so they are one junction rather than several.

01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50%

A count read off the leading zeros

Hash every key and watch for the longest run of leading zeros. Seeing k of them is evidence of about two to the k distinct keys — an estimator with a variance so large it is worthless, and the two devices that fix it are the whole of what a cardinality sketch is.

streaming · Cardinality 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.

CardinalityEstimatorHyperLogLogLeading zerosLinear countingRelative errorSketchStochastic averagingClosed formEstimator biasHash functionIdempotence

All concepts