HyperLogLog Cardinality Estimation

A tick database wants to know how many distinct order IDs or client IDs passed through today — potentially billions of events — without storing every unique value it has seen, which would need gigabytes of memory. HyperLogLog solves this by exploiting a simple probabilistic fact: if you hash each item to a uniform random binary string, the length of the longest run of leading zeros you observe across many hashes tells you roughly how many distinct items you've hashed, since seeing a run of $k$ leading zeros happens with probability $2^{-k}$, and you'd expect to need about $2^k$ distinct hashes before one shows up.

The algorithm splits incoming hashes into many small buckets (say 1,024) by their last few bits, and in each bucket tracks only the longest leading-zero run seen so far — a single small number per bucket. Averaging (harmonically) the estimates across all buckets and correcting for known biases gives a cardinality estimate accurate to roughly 1-2% using only a few kilobytes total, regardless of whether the true count is in the thousands or the billions.

The trade-off is that HyperLogLog only estimates how many distinct items there are, not which ones, and its accuracy is approximate rather than exact — acceptable for dashboards and monitoring (distinct symbols traded today, distinct IP addresses hitting an API) but not for anything requiring an exact count or the ability to list the items.