HyperLogLog and Cardinality Estimation
HyperLogLog estimates distinct element count with small memory by combining hashed observations into registers.
HyperLogLog and Cardinality Estimation
HyperLogLog estimates distinct element count with small memory by combining hashed observations into registers. Hash each input uniformly. A prefix selects one of m registers; remaining bits determine a leading-zero statistic. Each register stores the maximum observed statistic. A harmonic-mean estimator combines registers, with practical corrections. Compatible sketches merge register-wise. Classic relative standard error is approximately 1.04/√m.
Mechanism and worked example
A web analytics service estimates daily unique visitors per region without storing every visitor ID. HyperLogLog cannot reveal which visitors appeared or answer exact membership. Merge daily sketches to estimate a union; do not sum daily unique counts because the same visitor may appear on multiple days.
| Question | Structure | Limitation |
|---|---|---|
| Distinct count | HyperLogLog | No identity retrieval |
| Frequency | Count-Min Sketch | Collision overestimation |
| Membership | Bloom/Cuckoo | Positive can be false |
| Quantiles | KLL/t-digest family | Rank/value error |
Failure modes and operations
Poor hash quality biases estimates. Incompatible hash functions, precision or encodings make merges invalid. Small-cardinality corrections matter and implementations vary. A sketch cannot enforce uniqueness or provide an exact billable count.
Trade-offs and design boundary
HyperLogLog is compact and mergeable for cardinality but loses identities. Exact sets cost memory proportional to distinct identities. Count-Min estimates frequency; quantile sketches estimate rank/value distributions.
Interview transfer exercise
How do you estimate monthly active users from daily sketches? Merge compatible registers to estimate the union; do not add daily counts.
Read the diagram
Hash each event identity → Select register from hash prefix → Record leading-zero statistic → Merge compatible registers for union estimate