A count read off the leading zeros

How many distinct keys went past? The exact answer needs a set, and a set needs space proportional to the answer.

The trick that avoids it is a change of question. Hash every key into a uniform 32-bit value. A uniform value starts with $k$ zeros with probability $2^{-k}$, so out of $D$ distinct keys the longest run of leading zeros anybody sees is, in expectation, about $\log_2 D$. Turn that round: watch for the longest run, and report two to its power.

The hash is doing two things at once and both are essential. It turns arbitrary keys into something with a known distribution, so a statement about surprise is possible at all. And it is a function, so the same key hashes the same way and cannot advance the record twice — which is exactly what makes the estimate about distinct keys rather than about items.

One register is worthless, and it is worth seeing why #

Take a single register holding the maximum rank $R$ over all $D$ distinct keys, and estimate $2^{R}$.

The estimator can only ever return a power of two. Its answer for $D = 1{,}000$ and $D = 1{,}400$ is identical, because both are overwhelmingly likely to produce the same maximum rank, and its answer jumps by a factor of two when it moves at all. There is no parameter to turn: the resolution of the estimate is the granularity of the register, and the register is counting doublings.

That is the same defect Morris’s counter has and it arrives for the same reason. Counting past what the register holds has the structure at base 2 with a relative error of 71% because the last increment is worth as much as everything before it; here the last leading zero is worth as much as everything before it. The two structures are the same idea with the coin replaced by the hash.

The fix in Morris’s case was to lower the base, which finds intermediate values by making the increments smaller. That is not available here, because the increments are not chosen — they are the bits of a hash, and there is no fractional leading zero. So the fix has to come from somewhere else.

Stochastic averaging #

Split the hash. Use its first $p$ bits to choose one of $m = 2^p$ registers, and the remaining bits to compute a rank that goes into that register.

Each register now sees about $D/m$ distinct keys and holds its own maximum. The estimate is built from all $m$ of them, and because the register assignment is itself a hash, the keys are split evenly without anybody counting them. Averaging $m$ estimators divides the variance by $m$, so the relative error falls as $1/\sqrt{m}$, and the constant works out to about $1.04$.

The name of the trick is the interesting part. The obvious way to get $m$ independent estimates is $m$ hash functions, which costs $m$ hash computations per item — for a thousand registers, a thousand hashes for every key in the stream. Stochastic averaging uses one hash and lets its own bits do the splitting, so the per-item cost is one hash however many registers there are.

That is a genuine asymmetry and it is why these structures are cheap enough to run in front of a firehose. Count-Min pays $d$ hashes per item because its rows must be independent draws from a family; a cardinality estimator pays one, because its registers are not required to be independent of each other in that sense — they are disjoint slices of one uniform value.

The estimate does not move when repeats go past #

The property that distinguishes this from every other counting structure on the site is easiest to see as a trace.

This is why the structure is idempotent, and idempotence is the reason it is deployed where it is. A stream delivered twice, or a shard processed twice after a failure, produces the same summary as one processed once — a property no counter has and no sample has, and one that removes an entire class of correctness problem from a distributed pipeline.

Where the estimate comes from #

There are three ways to turn $m$ register values into one number, and the differences between them are the subject of the next essay. Naming them here fixes the vocabulary.

Probabilistic counting, Flajolet and Martin’s original, uses a bitmap per register rather than a maximum and reads the position where the bitmap stops being solid. It is accurate and it costs a word per register rather than five bits.

LogLog takes the arithmetic mean of the register values and exponentiates: $\alpha m \cdot 2^{\bar{M}}$. Five bits per register, and its accuracy is measurably worse than it needs to be.

HyperLogLog takes the harmonic mean of $2^{M_j}$ instead. The same registers, the same bits, the same updates, a different arithmetic — and about 30% less error. The correction that makes it work is where that gap is measured and where the corrections that make the estimator usable at both ends of its range are set out.

How wide a register has to be #

Five bits is the number that gets quoted and it is worth deriving, because it is where the structure’s efficiency actually comes from.

A register holds the position of the leftmost 1 in the bits left over after the register index, which for a 32-bit hash and $p$ index bits is $32 - p$ bits. So the largest rank possible is $33 - p$, and for any $p$ of four or more that fits in five bits with room to spare. The structure asserts this rather than assuming it: a rank that will not fit throws, so a future change to the hash width cannot silently truncate.

That is the whole of the space argument. A register does not hold a count, or a key, or a hash — it holds the logarithm of a count, and a logarithm of anything a stream can contain fits in five bits. Which is why the state of a HyperLogLog is $m \cdot 5$ bits and not $m \cdot 32$, and why bottom-$k$, which keeps hashes rather than logarithms of hashes, costs six times as much per slot.

With a 64-bit hash the largest rank rises above 32 and six bits are needed, which is what production implementations use, and the extra bit buys headroom rather than accuracy.

The register count is the dial, and both ends of it are visible #

Everything above is one setting of one parameter. The register count $m = 2^p$ decides the accuracy and the space together, and the whole structure is small enough that the dial can simply be drawn at four settings on the same stream.

Four times the registers is half the error, which is the $1/\sqrt m$ the whole design rests on. It is worth seeing that it keeps working in the direction of more registers as well as fewer.

And the other axis the register count has to survive is the number of distinct keys, because a register that saturates is a register that has stopped counting.

The two ends where the law stops #

$1.04/\sqrt m$ is an asymptotic statement and it has a floor and a ceiling, both of which are visible in measurements taken across a wide enough range.

At the low end most registers are still empty. With $m = 1{,}024$ registers and four hundred distinct keys, six hundred registers have seen nothing at all, and the harmonic mean of $2^{-M}$ over a set dominated by zeros is not an estimate of anything — the raw estimator comes out 137% high. The repair is to stop using it and count the empty registers instead, which is a different estimator entirely and is the subject of the next essay.

At the high end two things bite. A 32-bit hash has about four billion values, so once the cardinality approaches that, distinct keys start sharing hashes and the structure stops being able to tell them apart — the birthday problem arriving as a hard ceiling on what any hash-based estimator can count. And well before that, the law itself softens: at $m = 16{,}384$ registers and fifty thousand distinct keys there are only three keys per register, and a measured relative error of 1.4% against a predicted 0.8% is the estimator being read outside the regime its analysis describes.

That second one is a measurement worth keeping, because it is a case of a formula being correct and being applied where it does not hold. The remedy is not a better formula but a better reading of the one there is: $1.04/\sqrt m$ describes a structure whose registers each see many keys, and buying more registers than the stream has keys to fill buys nothing.

The hash is the whole assumption #

Everything above rests on the hash producing something indistinguishable from uniform bits. If it does not, the estimator does not degrade gracefully — it collapses.

The demonstration uses the most ordinary key set there is: the integers 0 to 49,999, in order, with the hash replaced by the identity. No adversary, no construction, just consecutive integers hashed by taking their bits. The estimate comes out wrong by 99.998%.

The reason is immediate once stated. Consecutive integers have no long runs of leading zeros in their low bits at all — the low bits cycle — so almost every register sees rank 1 or 2 and the structure concludes that it saw almost nothing. A hash’s job here is not to avoid collisions, it is to manufacture the surprise the estimator is measuring, and a hash that fails to do so produces a confident answer of the wrong order of magnitude.

The gate carries the collapse as a rejection rather than as a measurement. The body of the check asserts what a reader might reasonably assume — that the low-bits hash is about as good as a real one on ordinary keys — and requires that assertion to fail. Written the other way round it would be an assertion that a broken thing is broken, which passes whether or not anything is working.

What it cannot tell anybody #

The registers hold ranks. They do not hold keys, and there is no operation that recovers one.

So a HyperLogLog can say how many distinct keys there were and cannot produce a single one of them, cannot say whether a particular key was among them, and cannot say how often any of them occurred. Those are three different questions needing three different structures — a filter allowed to be wrong for the second, a count that is never under for the third — and the fact that all four structures are built out of hashes and small integers makes them easy to confuse with one another.

There is a cardinality estimator that does keep keys, and it is worth naming because it makes the trade explicit. Bottom-$k$ keeps the $k$ smallest hash values seen, estimates $D$ as $(k-1)$ divided by the largest of them, and the $k$ keys behind those hashes are a uniform random sample of the distinct keys. The same state answers “how many” and “show me some”. It costs 32 bits per slot against HyperLogLog’s five per register, and the plates above show what that costs in accuracy at equal bits.

The union is exact and the intersection is not #

Merging two summaries by taking the larger of each pair of registers gives exactly the summary the concatenated streams would have produced. That is stated above as a property of the maximum and it is worth following one step further, because the step is where a great many deployments come unstuck.

Having unions, the obvious next thing to want is intersections, and inclusion–exclusion appears to supply them:

$$|A \cap B| \;=\; |A| + |B| - |A \cup B|$$

with all three terms available from sketches. It is arithmetically correct and it is close to useless, and the reason is the one this collection keeps arriving at: the error is relative to the quantities estimated, and the answer is a difference between them.

Take two sets of a million keys sharing a thousand. Each of the three terms is estimated to within about 1%, which is ±10,000 on each. The intersection is a thousand, and it is being computed as a difference of three numbers whose individual uncertainties are ten times larger than the result. The answer is a thousand plus or minus thirty thousand — which is to say the structure has reported nothing at all, in a form that looks like a number.

The general statement is that the relative error on an intersection is the relative error on the union multiplied by the ratio of the union to the intersection, and that ratio is exactly what makes an intersection interesting to ask about. Small intersections between large sets are the case anybody cares about and the case the arithmetic cannot supply.

This is a different failure from every other one in this field. Nothing is biased, no model is violated, no hash is weak, and the three sketches are each performing exactly as advertised. The estimate is destroyed by an operation performed on the answers, and the structure has no way to know it happened.

The remedy is to use a summary whose statistic supports the operation directly. Bottom-$k$ does: the $k$ smallest hashes of $A \cup B$ are recoverable from the two sketches, and the fraction of them belonging to both sets is an unbiased estimate of the Jaccard similarity, with an error that depends on $k$ rather than on the ratio of the sets. The right structure is chosen by the operations, not by the accuracy at equal bits — which reverses the comparison the plates above draw, and is why the more expensive structure survives.

The maximum is not the most informative statistic #

The closing observation above is that the maximum is monotone, order-independent, and combines under union. It is worth adding the other half of that trade, because the two together explain the design rather than just praising it.

A register holds the largest rank it has seen and discards every other rank it saw. That is a great deal of thrown-away evidence: a register that has seen ranks 1, 1, 2, 1, 3, 1 and 5 reports 5, and the six other observations — which are themselves samples from a known distribution and do carry information about how many keys arrived — are gone.

An estimator that used the whole histogram of register values, rather than a summary of it, would be more accurate on the same bits, and that is what the maximum-likelihood estimators in the later literature do. They fit the cardinality that makes the observed distribution of register values most probable, they need no piecewise switch and no scale factor, and they are measurably better across the whole range.

So why is the maximum the statistic the field was built on? Because a maximum composes and a likelihood does not. The union property, the idempotence, the validity at every prefix and the exact mergeability across shards are all consequences of the update rule being take the larger, and every one of them is an engineering property worth more in a distributed system than a few per cent of accuracy.

That is the trade stated plainly: the structure keeps a statistic that is not the most informative one available, in exchange for algebraic properties that make it deployable. It is the same trade a deterministic quantile summary refuses and pays for in mergeability, run in the opposite direction — and having both cases makes it clear that neither choice is the right one in general.

The shape of the answer #

It is worth stepping back to what has happened to the question.

“How many distinct keys” was a question about a set, and answering it exactly requires holding one. Hashing turns it into a question about an extreme value — how surprising was the most surprising hash — and an extreme value is summarised by a single small integer. That is the compression, and it is not a compression of the data: nothing about the keys is retained, and the structure could not tell a stream of a million keys from a different stream of a million keys.

What makes it work is that the question being asked has an answer of about twenty bits, and the structure was built to answer that question and no other. Every structure in this field has that shape. The bits are spent on a statistic chosen in advance, the choice is the design, and the answer to any question that was not chosen is unavailable at any price.

There is one more thing the change of question bought, and it is the reason this particular statistic was the one chosen out of the many that would have worked. A maximum is monotone: it can only go up, it does not depend on the order things arrived in, and the maximum over a union is the maximum of the maxima. Every one of those properties turns into an engineering property later — the estimate is valid at every prefix, two summaries of two shards combine exactly, and a shard delivered twice changes nothing. The summaries that add is where they are collected, and they are not incidental benefits of a clever estimator. They are what makes a statistic worth building a structure around.