Sweaty Imposter

HyperLogLog

TechniqueApproximationSeniorStaffUpdated
Estimate cardinality (unique count) of a massive set using a few KB of memory and a small error margin.

When to Use HyperLogLog

Counting unique visitors, distinct query terms, or unique IPs across billions of events. Exact counts require O(n) memory; HyperLogLog (HLL) gets you within ~1% in O(log log n).

In Practice

Redis's PFADD / PFCOUNT commands. Used by ad networks for daily unique reach, by BigQuery for APPROX_COUNT_DISTINCT.

How HyperLogLog Comes Up in Interviews

Scenario

An ad network needs daily unique-reach counts across billions of impression events. Exact counts would blow memory. They want ~1% error and a few KB of state per metric. Which technique?

HyperLogLog estimates cardinality (distinct count) in O(log log n) memory with a tunable error around 1%. Bloom filters do membership, not cardinality; count-min does frequency.

HyperLogLog is doing something genuinely magical: estimating distinct count in O(log log n) space using the position of the leftmost 1-bit across hashed values. The intuition is that if you've seen a value whose hash starts with k leading zeros, you've probably seen on the order of 2^k distinct values, HLL just averages this across many independent registers to control variance. Redis's PFADD/PFCOUNT use 12KB of state per key for ~0.8% standard error; BigQuery's APPROX_COUNT_DISTINCT and Presto's approx_distinct are HLL under the hood. Critically, HLLs union without losing precision, so you can compute daily uniques by merging per-shard sketches, exact distinct counts can't do that.