HyperLogLog: Counting Billions of Unique Items in a Few Kilobytes

Why Exact Counting Falls Apart at Scale

The obvious way to count distinct items is to remember every item you have already seen, typically in a hash set, and check new items against it. This works perfectly for small datasets, but it scales terribly. To count a billion unique user IDs exactly, you need to store roughly a billion entries in memory, which can easily mean many gigabytes of RAM. Multiply that across thousands of metrics, such as unique visitors per page, per day, per country, and exact counting becomes financially and operationally impossible. The core problem is that exact cardinality counting requires memory proportional to the number of distinct items, no matter how cleverly you store them. Real-world systems like analytics platforms, ad networks, and databases often need to track distinct counts for millions of separate keys simultaneously, each potentially containing billions of elements. Storing a full set for each one simply does not fit in memory or budget. This is the gap that probabilistic cardinality estimators were built to fill. By accepting a small, statistically bounded amount of error, typically a couple of percent, algorithms like HyperLogLog reduce memory requirements from gigabytes to kilobytes, a reduction of several orders of magnitude. That tradeoff, tiny error for massive memory savings, is what makes counting at internet scale practical at all.

The Core Insight: Leading Zeros as a Clue

HyperLogLog's foundational idea starts with hashing. Every item you count gets run through a hash function that produces a seemingly random string of bits. Because a good hash function spreads outputs uniformly, each bit in that string is equally likely to be 0 or 1, independent of the others. Now consider the run of leading zeros at the start of a hash, meaning how many 0 bits appear before the first 1. The probability that a single random hash starts with exactly one leading zero is one half. The probability it starts with two leading zeros is one quarter, since both the first and second bits must be zero. A run of k leading zeros has probability one over two to the power k. This means seeing a long run of leading zeros in any single hash is rare. But if you hash many distinct items and track the longest run of leading zeros observed across all of them, that maximum grows as you add more distinct items. Intuitively, if the longest run you have seen so far is 10 leading zeros, that is a one in 1024 event, so you probably needed to try roughly a thousand distinct hashes before stumbling on it. This single number, the maximum leading-zero run length, becomes a rough but real statistical estimator of how many distinct items were hashed.

Splitting Into Buckets: Why One Counter Is Not Enough

A single maximum leading-zero-run counter is a noisy estimator. One lucky or unlucky hash can throw the whole estimate off by a large factor, since the estimate grows exponentially with the run length. Real HyperLogLog fixes this by splitting the incoming hash space into many independent buckets, often called registers, commonly somewhere between a few hundred and a few thousand of them. A small number of bits from each hash, say the first few bits, determines which bucket that item's hash is routed into, and the remaining bits are used to compute the leading-zero-run length within that bucket. Each bucket then independently tracks only its own maximum run length. Instead of relying on one noisy number, you now have hundreds or thousands of independent noisy estimates. Averaging across many independent noisy signals dramatically reduces variance, which is a general and powerful statistical principle. HyperLogLog specifically uses a harmonic mean rather than a simple arithmetic mean to combine the per-bucket estimates, because harmonic means are far less sensitive to occasional large outlier values, which matter a lot here since run-length estimates grow exponentially. The final cardinality estimate is derived from this harmonically averaged value, multiplied by a bias-correction constant tuned for the number of buckets used.

Accuracy Versus Memory: The Remarkable Tradeoff

The practical payoff of the bucket-and-harmonic-mean approach is striking. With just a few thousand registers, each needing only a handful of bits to store a small run-length value, HyperLogLog can estimate the cardinality of a set with a standard error of roughly 2 percent, regardless of whether the true count is a thousand or a billion. Total memory usage for such accuracy typically lands around 1.5 kilobytes, sometimes stated as needing roughly m times 6 bits where m is the number of registers, for example 16384 registers using about 12 kilobytes for very high precision configurations. Compare that to exact counting, where tracking a billion unique 64-bit identifiers with a hash set could require many gigabytes once you account for hash table overhead. That is a memory reduction of several orders of magnitude for a small, predictable, and mathematically bounded error rate. Crucially, this error does not grow as the dataset grows. The standard error stays roughly constant as cardinality increases, which is what makes HyperLogLog uniquely suited to tracking huge, ever-growing datasets. You can tune the tradeoff by choosing more or fewer registers: more registers means lower error but more memory, following a well-understood mathematical relationship between register count and expected standard error.

Real-World Uses: From Redis to Web Analytics

HyperLogLog is not just an academic curiosity, it is embedded in production systems handling enormous scale every day. Redis, the popular in-memory data store, offers native HyperLogLog support through commands like PFADD to add items and PFCOUNT to retrieve the cardinality estimate, all backed by a data structure that Redis caps at roughly 12 kilobytes regardless of how many billions of items have been added. Engineering teams use this to count unique visitors to a website, unique search queries submitted to a search engine, unique IP addresses hitting an API, or unique products viewed in an e-commerce catalog, all without the memory explosion that exact counting would require. Large-scale analytics platforms and databases, including systems built by major search engines and social networks, use HyperLogLog or close variants internally for exactly this reason: approximate answers delivered instantly and cheaply are often far more valuable than exact answers that are too slow or too expensive to compute. Another convenient property is that HyperLogLog structures from different shards or time windows can be merged together, letting you compute distinct counts across combined datasets without re-scanning the original data, which fits naturally into distributed and streaming architectures.

Frequently asked questions

Try it live

Everything above runs in your browser — open HyperLogLog: Counting Billions of Unique Items in a Few Kilobytes and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.