HyperLogLog Cardinality Estimator

Pour items into a HyperLogLog sketch and watch 2^p registers track the longest run of leading zeros each one has seen. With a few KB of state, HLL estimates the count of distinct items in a stream that may be billions long — at a typical ±2 % standard error for p=14.

Precision p:

True unique count

tracked by an in-browser Set

HLL estimate

empty

Relative error

—

target σ for this p

Items inserted (raw)

duplicates included

Sketch size

0 B

6-bit registers

vs. Set memory

—

naive set: ~36 B / item

Register histogram

Each bar is one of the 2ᵖ registers; the height is the register's stored value — the longest run of leading zeros seen by any item that hashed into that bucket. Empty registers stay at 0.

Estimate vs. true count over time

How it works

h(x) = 64-bit hash
j = first p bits of h(x) → bucket index
M[j] ← max(M[j], rank of first 1 in remaining bits)
Z = (Σ 2^(-M[j]))⁻¹
E = α_m · m² · Z with α_m ≈ 0.7213 / (1 + 1.079 / m)
if E ≤ 2.5 m and there are V empty registers → use LinearCounting: m · ln(m / V)

HLL trades exactness for memory. A p=14 sketch is 12 KB and estimates billions of distinct items with about ±0.8 % standard error. The same job with a plain hash set would need megabytes for thousands of items, and gigabytes once you reach the billions. HLL sketches are mergeable: HLL(A ∪ B) = elementwise-max(HLL(A), HLL(B)), which is why Redis, BigQuery, Snowflake, and ClickHouse all use HLL (or HLL++) under the hood for COUNT DISTINCT approximations.