HyperLogLog: Counting Distinct Items in Kilobytes

A Bloom filter answers whether an item is present. It cannot say how many distinct items it holds, because it never counted them.

Cardinality is a harder problem than membership in one specific way: the naive solution requires recognising repeats, and recognising a repeat means having kept the earlier occurrence. That is why a hash set works and why it costs space proportional to the answer.

The way out is to stop trying to recognise repeats at all, and instead to measure something about the hashes that is insensitive to duplicates.

Hash an item and you get a fixed pattern of bits. Hash the same item again and you get the identical pattern. So any property computed from the set of hash values seen is automatically unaffected by how many times each item arrived. Duplicates become free, without anything being stored.

The question is which property of a set of random-looking bit patterns reveals how many distinct patterns produced it.

Here is the idea the whole structure rests on.

A good hash produces bits that behave like independent coin flips. So for any single hash value, the probability that it begins with exactly one zero is one half, with two zeros is one quarter, with r zeros is one over two to the r.

Now invert that. If you have observed a hash value beginning with ten zeros, an event with probability about one in a thousand, then you have probably examined on the order of a thousand distinct values. Seeing something that rare is evidence about how many chances it had to occur.

So track a single number: the largest count of leading zeros seen so far, call it R. Then 2 to the power R is a crude estimate of the number of distinct items.

This is remarkable in principle. R for a billion items is around thirty, so it fits in a handful of bits, and the estimate is untouched by duplicates because a repeated item produces a hash that was already counted.

It is also, on its own, badly unreliable.

The single-counter version has a fatal property: its estimate can only ever be a power of two.

R increments by one, so the estimate jumps from 1024 to 2048 to 4096. There is no way for it to report 1500, and the granularity is the same size as the answer.

Worse, R is driven entirely by the single luckiest hash observed. One item that happens to hash to an unusually long run of zeros permanently doubles or quadruples the estimate, and nothing subsequent corrects it. The estimator has enormous variance because it depends on an extreme value rather than an average.

The standard fix for high variance is averaging over many independent trials, but running the whole thing several times with different hash functions would multiply the hashing cost.

Stochastic averaging gets the same effect for free. Use the first p bits of each hash to select one of m equals 2 to the p registers, and use the remaining bits to compute leading zeros for that register only. Each item updates exactly one register, so the cost is unchanged, and the items are partitioned into m independent sub-experiments.

Splitting one hash into a selector and a payload is what makes the cost per item constant regardless of how many registers there are.

Each register holds the maximum leading-zero count among the items that landed on it, so each is an independent small experiment estimating the cardinality of its own share of the data.

Combining them is the step where HyperLogLog differs from its predecessors. The registers are not averaged arithmetically. Because each holds a maximum, its estimate is skewed by large values, and an arithmetic mean inherits that skew. The harmonic mean is used instead, which is dominated by the smaller values and therefore resistant to a single register that got lucky.

That substitution is the specific contribution the algorithm is named for, and it is what pushed the accuracy of this family to near optimal.

Philippe Flajolet, Fusy, Gandouet and Meunier presented the analysis in "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", at the Analysis of Algorithms conference in 2007, pages 127 to 146. Their headline result is a relative standard error of about 1.04 / sqrt(m), and they noted it matched the accuracy of the previous best estimator while using 64% of its memory.

The practical consequence is a table worth memorising, because it makes the trade obvious.

import math
for p in (10, 12, 14, 16):
    m = 2 ** p
    err = 1.04 / math.sqrt(m)
    print(f"p={p}  m={m:>6}  error={err*100:.3f}%  memory={m*6//8//1024 or m*6//8}")
# p=10  m=  1024  error=3.250%  memory=768   (bytes)
# p=12  m=  4096  error=1.625%  memory=3     (KB)
# p=14  m= 16384  error=0.812%  memory=12    (KB)
# p=16  m= 65536  error=0.406%  memory=48    (KB)

Six bits per register is enough, because the leading-zero count of a 64-bit hash cannot exceed about 64 and therefore fits.

The row that matters is p equals 14: under 1% error in 12 kilobytes, and that figure is the same whether the true cardinality is a thousand or ten billion. Memory is constant in the answer, which is the property no exact method can have.

The raw estimator is biased at the extremes, and production implementations correct for it.

Small cardinalities. When the count is well below m, many registers are still zero and the harmonic mean misbehaves. The standard fix is to detect this case and switch to linear counting, which estimates from the proportion of empty registers instead, and is accurate precisely where the main estimator is not.

Large cardinalities. With a 32-bit hash, values start to collide as the count approaches the hash space, and the estimate saturates. Using a 64-bit hash pushes that boundary far beyond any realistic input, and modern implementations do exactly that rather than applying a correction.

Empirical bias. Google's engineering paper on the algorithm added measured bias corrections across the mid-range, plus a sparse representation that stores an exact list of touched registers while the count is small. That last one matters more than it sounds: it means a sketch tracking a handful of items costs bytes rather than the full twelve kilobytes, which is what makes it practical to keep millions of separate sketches.

The general lesson: the elegant estimator is the core, and roughly half of a real implementation is handling where it is known to be wrong.

The property that made HyperLogLog ubiquitous is not its accuracy. It is that two sketches can be combined.

Each register holds a maximum. The union of two sets therefore has, in each register, the maximum of the two sketches' values. So merging is an element-wise maximum over m registers, and the result is exactly the sketch you would have built by processing both streams together. No approximation is added by merging.

def merge(a, b):
    return [max(x, y) for x, y in zip(a, b)]   # exact union of the two sketches

That single line is why the structure fits distributed systems. Each machine sketches its own shard independently, with no coordination, and the shards combine at the end. Daily sketches merge into a weekly one, so unique visitors over any period is a merge of stored daily sketches rather than a re-scan.

Intersection does not work this way. There is no element-wise operation for it, and the usual workaround, estimating the intersection from the two cardinalities and their union, subtracts two large approximate numbers. When the intersection is small relative to the sets, the errors in the inputs dwarf the answer.

So: unions are exact and cheap, intersections are unreliable. A system built on merging is sound; one built on intersecting will produce nonsense on exactly the queries where the answer is most interesting.

The third row is the one to internalise, and it differs from the Bloom filter's guarantee. The error is relative, so a reported 1,000,000 with 0.8% error means roughly plus or minus 8,000. It is not a bound, either: 0.8% is a standard error, so individual estimates land outside it regularly.

That makes HyperLogLog wrong for anything requiring an exact count, and specifically wrong for comparing two nearly equal cardinalities. If two sketches report 1,000,000 and 1,004,000, the difference is inside the noise and means nothing.

What it is right for is the question it was designed for: how many distinct things, roughly, at a scale where exact is impossible and 1% does not change any decision.

Membership and cardinality are now covered. The remaining question, how often a specific item occurred, needs counters rather than bits, and it is where the last structure comes in.