HyperLogLog: Estimating Cardinality from a Register Array

Counting distinct values in a stream without storing them is a different problem from membership, which the bit-array filters answer with a one-sided error. There is no key to look up and no asymmetry to exploit; the answer is a number, and the error is symmetric. The classical solution, probabilistic counting, observes that the pattern of leading zeros in the hash of each element carries information about how many distinct elements were seen: among $n$ uniform random hashes, the longest run of leading zeros is about $\log_2 n$. One such observation is useless, since its variance is enormous, but averaging many independent observations reduces the variance predictably. HyperLogLog is the construction that does this averaging in a fixed array of six-bit registers, and its error is a function of nothing but the array size.

Registers and the rank of a hash

The state is $m$ registers, each holding a small integer. A key is hashed to a 64-bit value; the top $p$ bits select one of the $m = 2^p$ registers, and the remaining bits determine the rank: the position of the leftmost 1-bit, counting from the start of the remaining bits.

Register $j$ keeps the maximum rank ever observed among keys that hashed into it. That maximum is the entire content of the structure. For a register that has seen $c$ distinct keys, the stored rank is approximately $\log_2 c$ plus a constant, because the probability that a random bit string starts with $r-1$ zeros followed by a one is $2^{-r}$, so the expected maximum over $c$ samples grows like $\log_2 c$.

The estimator is built on the quantity $2^{-R_j}$, where $R_j$ is the stored rank. If register $j$ has seen $c$ keys, $2^{-R_j} \approx 1/c$, and the harmonic mean of $c$ over the $m$ registers is what the averaging produces. The raw estimate is

$$ E = \alpha_m , m^2 \left( \sum_{j=1}^{m} 2^{-R_j} \right)^{-1} $$

with $\alpha_m$ a constant that depends on $m$ and corrects a systematic bias in the harmonic mean; it approaches $1/(2 \ln 2) \approx 0.7213$ for large $m$. The relative standard error is approximately

$$ \frac{1.04}{\sqrt{m}} $$

which is the headline number. At $m = 16384$ registers — 16 KB at one byte each, or 12 KB at six bits — the error is about 0.81%. At $m = 4096$ it is about 1.6%. Doubling the registers divides the error by $\sqrt{2}$, so each halving of the error costs four times the memory. That is a far better space curve than a Bloom filter’s, which is exponential in the reciprocal error.

Why the harmonic mean rather than the arithmetic mean

The choice of harmonic mean is the technical core, and it is not a matter of taste. The quantity $2^{-R}$ is an estimator of $1/c$ whose distribution has a heavy right tail: a register that happens to see an unusually long run of zeros reports a very small $2^{-R}$, which under an arithmetic mean would drag the average down sharply. The harmonic mean is dominated by small values, which is exactly the regime where the estimator is stable — a single anomalous register contributes at most $2^{-R}$ and cannot dominate a sum of $m$ terms the way it would under an arithmetic mean of $2^{R}$.

Flajolet and colleagues make this precise: the arithmetic mean of $2^{R}$ has infinite variance for the underlying distribution, while the harmonic mean has finite variance and a bounded influence from outliers. The estimator is therefore insensitive to the very events that make a single register uninformative.

The two ends where the formula fails

The raw estimate is valid only in the middle range, and both extremes need separate treatment.

At small cardinalities, the registers are mostly empty and the harmonic-mean estimate is biased high, because the $2^{-R}$ values from empty registers are all exactly 1 and the sum is dominated by them. The standard correction is linear counting: count the number of registers still at zero, call it $V$, and estimate

$$ E_{\text{small}} = m \ln \frac{m}{V} $$

Linear counting is accurate while $V$ is a substantial fraction of $m$, and the switch happens when the raw estimate falls below about $2.5m$. The threshold matters because the two estimators disagree near it; implementations use a fixed cutoff and accept the small discontinuity.

At large cardinalities the 64-bit hash space becomes the limit. A rank cannot exceed 64 minus $p$, and once the true cardinality approaches $2^{64}$ the estimate saturates regardless of the register contents. This is not a practical concern for 64-bit hashes, but it is for 32-bit ones, and it is the reason a sketch built with a truncated hash silently under-reports past a few billion distinct values.

There is a third correction that matters in practice. The original analysis assumed the hash is uniform; real hashes are not, and the deviation shows up as a systematic bias in the middle range. The engineering work behind production implementations replaced the raw estimator with a table of empirical corrections fitted to the observed bias, and the improvement is substantial — the corrected version is accurate to within a fraction of the theoretical error across the whole range rather than drifting by several percent in the middle.

Insertion is a maximum, not a count

The operation that updates a register is a maximum, which gives the structure two properties that counting structures lack. First, insertion is idempotent: seeing the same key twice cannot change the state, so duplicates in the stream cost nothing and no deduplication is required before feeding the sketch. Second, insertion is commutative and associative, so the order of the stream does not matter and the sketches for two disjoint streams combine by taking the register-wise maximum — the basis of the merge semantics that make the structure useful in distributed settings.

Deletion is impossible. A register holds only the maximum rank it has seen, and there is no record of which key produced it, so removing a key cannot lower the register. The estimate is therefore over the whole history of the stream, not over a sliding window. Windows are built by keeping one sketch per time bucket and merging the ones that fall inside the window, at the cost of one sketch per bucket.

import math

class HyperLogLog:
    def __init__(self, p=14):
        self.p = p
        self.m = 1 << p
        self.width = 64 - p
        self.reg = bytearray(self.m)

    def add(self, h: int):
        j = h >> self.width                       # top p bits select the register
        b = h & ((1 << self.width) - 1)           # the other 64 - p bits
        # rank = position of the leftmost 1-bit, counting from 1
        r = self.width - b.bit_length() + 1
        if r > self.reg[j]:
            self.reg[j] = r

    def estimate(self):
        s = sum(2.0 ** -v for v in self.reg)
        e = 0.7213 / (1 + 1.079 / self.m) * self.m * self.m / s
        if e <= 2.5 * self.m:
            v = self.reg.count(0)
            if v:
                return self.m * math.log(self.m / v)   # linear counting
        return e

bit_length of the low word gives the position of its highest set bit, so the rank is the width minus that position plus one. The all-zero case needs no branch here: bit_length of zero is zero, so the rank becomes width + 1, the maximum the field can hold — which is the correct reading of a hash that is entirely zeros.

Register width and the practical array

Six bits per register is the usual packing: a rank beyond 63 is impossible with a 64-bit hash and a 14-bit index, so five bits would almost suffice, but the packing arithmetic is cheaper at six because three registers fit in 18 bits and four fit in 24, and the wasted two bits per register buy simpler shift-and-mask code. The alternative is one byte per register, which wastes a quarter of the space for trivial access.

The array size is the only real design choice, and it is a direct trade against error. At 16 KB the error is under one percent, which is enough for most cardinality questions — is this set a thousand or ten thousand? — and small enough to keep one sketch per key in memory. At 1 MB the error falls to about 0.3%, which is rarely worth the space unless the sketches are few and long-lived.

The structure also has a floor: with $m$ registers it cannot distinguish cardinalities below roughly $m/10$ well, because linear counting’s variance grows as the set empties. A sketch with 16,384 registers is a poor choice for counting sets of a few dozen elements, where an exact bitmap or a plain hash set is both smaller and exact. Sizing the register array to the smallest cardinality of interest, rather than the largest, is the mistake that produces estimates of “1” for sets of ten.