HyperLogLog Explained: Counting Unique Items with Almost No Memory
Counting exact distinct values requires storing every value you have already seen, so a hash set for a billion unique visitors costs gigabytes. HyperLogLog trades a small, bounded amount of error for a data structure that stays a few kilobytes no matter how many items pass through it.
Published July 6, 2026The Problem: Counting Distinct Items at Scale
An analytics pipeline that wants to know how many unique users visited a site today has two options with a plain set: keep every user ID it has seen (memory grows linearly with cardinality) or accept it cannot answer the question incrementally. Neither is attractive at web scale, where cardinalities routinely reach hundreds of millions and the count needs to update in real time as events stream in.
HyperLogLog, introduced by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier, answers a slightly weaker question — an approximate count — in exchange for memory that stays constant regardless of cardinality. A HyperLogLog structure sized for a typical error tolerance fits comfortably in a few kilobytes whether it has counted a thousand items or a trillion.
The Core Trick: Bit Patterns in Random Hashes
Hash every incoming item with a good hash function so the output looks like a uniformly random bit string. Now look at the position of the leftmost 1-bit (equivalently, the number of leading zeros) in each hash. A run of k leading zeros happens with probability 1/2k, so seeing a long run of zeros is evidence that you have hashed a lot of distinct items — because you needed many independent tries before one happened to produce that pattern.
If you track only the single longest run of zeros observed, the estimate is wildly noisy: one lucky hash skews the whole result. HyperLogLog fixes this with stochastic averaging: instead of one observation, it splits the hash space into m buckets using a few bits of the hash as a bucket index, tracks the longest zero-run seen independently in each bucket, and combines all m estimates with a harmonic mean, which is resistant to outliers.
Accuracy and the Memory Trade-off
The original HyperLogLog analysis gives a standard error of approximately 1.04 / sqrt(m) for the cardinality estimate, where m is the number of buckets. With m = 16384 registers, each needing only about 5-6 bits to store a run-length count, the whole structure fits in roughly 10-12 KB and yields a typical error around 0.8%. Doubling m halves neither the error nor the memory cheaply — error improves with the square root of m, so getting twice the precision costs roughly four times the memory.
The structure also supports merging: the HyperLogLog for the union of two sets is simply the bucket-wise maximum of the two structures' registers, with no need to touch the original data. That makes it trivial to combine daily counts into a weekly estimate or shard counting across many machines and merge centrally.
Where HyperLogLog Is Used
- Redis: The
PFADDandPFCOUNTcommands implement HyperLogLog directly, letting you track unique counters (unique visitors, unique search terms) in about 12 KB per key regardless of how many elements are added. - Query engines: Presto, BigQuery, and similar systems expose an approximate
COUNT(DISTINCT ...)built on HyperLogLog for dashboards where an exact count would require an expensive shuffle across the whole dataset. - Network monitoring: Estimating the number of distinct source IPs hitting an endpoint, useful for detecting scanning or distributed traffic patterns without keeping a full IP set per window.
Conclusion
HyperLogLog is a good example of trading an exact answer for one with a known, tunable error bound in exchange for a huge constant-factor win in memory. The insight that a hash's leading-zero run length carries information about how many distinct hashes you have seen is not obvious the first time you encounter it, but it generalizes: several other cardinality estimators (LogLog, HyperLogLog++) build on the same idea with different bias corrections for small and large cardinalities.
The original paper by Flajolet and coauthors, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm," works through the full error derivation if you want the mathematics behind the 1.04/√m constant rather than taking it on faith.