Search tools and guides ⌘K
IV · Probabilistic structures

HyperLogLog

Count distinct, in 12 KB.

2007 · Flajolet, Fusy, Gandouet, Meunier · INRIA
The story

Counting unique elements in a stream of billions with sub-percent error in 12 KB of memory. The trick: hash each element; for each, count the leading zeros in the hash. The maximum leading-zero count seen is a stochastic estimator of the cardinality.

How it works

Partition the hash output into m buckets. For each bucket, track the maximum leading-zero count of all hashes that landed in it. The harmonic mean of 2^count across buckets, with bias correction, estimates the cardinality. Standard error ≈ 1.04/√m.

Where it lives

Redis (PFCOUNT, PFADD). BigQuery APPROX_COUNT_DISTINCT. Druid uniques. Snowflake APPROX_COUNT_DISTINCT. Every "unique users" metric at internet scale.

The key insight

Mergeable: HLL of region A union HLL of region B = HLL of A∪B, with no recomputation. That property is why HLLs power dashboards across sharded data — each shard returns its sketch, the gateway merges.

More in Probabilistic structures
Bloom filter A set, in a thousandth of the space. Count-Min sketch Approximate frequencies, in tiny memory. MinHash Set similarity, in a few hashes. t-digest Quantiles, fairly accurate, fully streaming.
Across the cabinet
V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours. VI Disjoint Set / Union-Find Track connected components, in a forest. VI Merkle tree Hash of hashes; tamper-evident. VI LSM-tree Append-only, merged in the background.
← All data structures