distinct-elements estimation (HyperLogLog)
/ HYPER-log-log /
How many UNIQUE visitors came to a website today, when the same person may appear thousands of times and there are billions of hits? Counting distinct things exactly means remembering everything you have already seen — a giant set — which is exactly what we cannot afford in a stream. Distinct-elements estimation answers 'how many different items?' using a sketch thousands of times smaller than the true set, by exploiting a simple statistical fact about random hashing. HyperLogLog is the famous, practical algorithm that does this.
The core intuition is a coin-flip game. Hash each item to a uniformly random bit string; duplicates of the same item hash to the same string, so they are automatically ignored, and what matters is the set of DISTINCT hash values. Now watch the longest run of leading zeros you ever see across those hashes. A hash starting with k zeros happens with probability 1/2^k, so seeing a run of k leading zeros is evidence you have hashed roughly 2^k distinct items — rare events appear only once you have drawn many samples. The naive estimate 2^(max leading zeros) is wildly noisy, so HyperLogLog refines it: split items into m buckets by their first few hash bits, track the max leading-zero count in each bucket, and combine the m buckets with a harmonic mean. Averaging many buckets crushes the variance, yielding a relative error of about 1.04/sqrt(m). With m = 16384 buckets — a few kilobytes — you estimate billions of distinct items to within roughly 1%.
This matters because count-distinct is one of the most demanded analytics in the world: unique users, unique search terms, distinct IPs in an attack, distinct values in a database column for query planning. HyperLogLog gives near-exact answers in fixed tiny memory, merges trivially across machines (take the per-bucket max), and runs in O(1) per item — which is why databases and analytics systems ship it. The honest caveats: the answer is an estimate with a known error band, not an exact count; accuracy is set in advance by m (more buckets, less error, more memory); and small cardinalities need a correction, since the raw estimator is biased when few items have been seen.
Hash items to random bit strings. Among the distinct hashes you see one beginning 0001... (3 leading zeros). A run of 3 zeros has probability 1/8, so it hints you have seen on the order of 2^3 = 8 distinct items. One such observation is noisy; HyperLogLog instead spreads items over 16384 buckets, keeps each bucket's max leading-zero count, and harmonic-means them — turning that crude signal into a roughly 1%-accurate count of billions.
Longest run of leading zeros hints log2(distinct); many buckets + harmonic mean give ~1% error.
HyperLogLog estimates the COUNT of distinct items, not which items they are — you cannot ask 'was x seen?' from it. Its error is fixed by the bucket count m (~1.04/sqrt(m)); small cardinalities need a bias correction. Sketches merge by taking per-bucket maxima, which makes it ideal for distributed counting.