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

Linear counting — where it appears

A cardinality estimate read off the empty cells of a bitmap, accurate while the bitmap is sparse and undefined once every bit is set. It is the cheapest estimator while the bitmap is sparse and returns infinity once it saturates, which is a hard limit rather than a degradation.

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

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 queries answered yesabsent key, the AND0.190%absent key, built on the intersection0.025%in one set only, the AND1.800%in one set only, built on it0.000%bits set: A 6,351, B 6,294, AND 3,232, direct 1,859no common key is ever denied

The intersection two filters cannot report

Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.

randomness · Randomness

Named alongside it

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

CardinalityEstimatorRelative errorSketchHarmonic meanHash functionHyperLogLogLeading zerosMergeable summaryStochastic averagingApproximate membershipBloom filter

All concepts