Counting Distinct Elements with HyperLogLog Registers

Counting distinct elements exactly requires memory proportional to the number of distinct values, as the counting argument in the streaming model shows. HyperLogLog gives up exactness and returns a value whose relative error is around one percent while using a few kilobytes, independent of how many elements arrive. The construction rests on one observation about hashing and one about averaging, and both are worth seeing in detail because the failure modes follow directly from them.

One hash, split into two fields

Every element is hashed to a bit string of length $L$, conventionally 64 bits. The first $p$ bits select one of $m = 2^p$ registers. The remaining $L - p$ bits are examined for the position of their leftmost 1 bit, counted from 1. That position is the rank $\rho$, and the selected register keeps the maximum rank it has seen.

The distribution of $\rho$ over random hashes is geometric: for a random bit string, the probability that the first $k-1$ bits are zero and the $k$-th is one is $2^{-k}$, so a register that has absorbed $t$ elements holds a rank around $\log_2 t$. With $n$ elements spread over $m$ registers, each register absorbs about $n/m$ of them, so the stored ranks sit around $\log_2(n/m)$ plus a small offset — the quantity the estimator has to invert. Each register therefore needs only enough bits to hold a rank up to $L - p + 1$; with 64-bit hashes and $p = 14$, six bits per register suffice, giving $2^{14} \times 6 / 8 = 12{,}288$ bytes.

The rank is capped. A register that would need to store a value larger than the field width saturates instead, which introduces a small bias for enormous cardinalities and is one reason implementations choose 64-bit hashes: at $2^{64}$ distinct elements the stream is beyond any realistic scale, so the cap never binds in practice.

Why the estimator is not an average of ranks

The naive estimator takes the arithmetic mean of the register values and exponentiates. That estimator has a serious variance problem: a single register that happens to see a run of many leading zeros pulls the mean up, and exponentiating amplifies the error. HyperLogLog instead computes

$$ E = \alpha_m , m^2 \Big/ \sum_{j=1}^{m} 2^{-M_j} $$

where $M_j$ is the value in register $j$ and $\alpha_m$ is a constant near 0.7213, adjusted slightly for small $m$ (the paper’s form is $0.7213/(1 + 1.079/m)$ for $m \geq 128$).

The denominator is a harmonic mean of $2^{-M_j}$, and harmonic means are dominated by their smallest terms. That is the desired behaviour: a register with a large rank contributes $2^{-M_j}$ close to zero and is effectively ignored, while registers with small ranks dominate. A single outlier register cannot inflate the estimate the way it inflates an arithmetic mean. This is the same reason the harmonic mean is the right average for rates: it tolerates large values without being dragged by them.

The relative standard error of the estimator is approximately $1.04/\sqrt{m}$. With $m = 4096$ registers ($p = 12$) that is about 1.6 percent; with $m = 16384$ ($p = 14$) about 0.8 percent. The constant 1.04 is a property of the rank distribution, not of any implementation.

The two corrections that make it usable at the edges

The formula above is asymptotically correct and wrong at both ends of the range.

When the cardinality is small relative to $m$, many registers are still zero, and the harmonic-mean formula overestimates. The fix is linear counting: let $V$ be the number of registers equal to zero. If the stream contained $n$ distinct elements, the expected number of empty registers is $m(1 - 1/m)^n \approx m e^{-n/m}$, so $n \approx m \ln(m/V)$. HyperLogLog switches to this estimate when the raw estimate is below about $2.5m$ and $V > 0$, because below that point the expected number of empty registers is large enough for the linear-counting variance to beat the raw estimator’s bias. Linear counting is exact in the limit of tiny streams — a single distinct element always leaves $m-1$ registers empty — and its variance grows as $n$ approaches $m$.

When the cardinality approaches the hash space, the raw estimate saturates. With 32-bit hashes the original algorithm applies a correction of $-2^{32}\ln(1 - E/2^{32})$, which diverges as $E$ approaches $2^{32}$; the estimator simply cannot distinguish $2^{32}$ from $2^{32} + 1$ distinct values. Sixty-four-bit hashes push this boundary far enough that the correction is unnecessary.

Between the two thresholds, the raw estimator is biased by a few tenths of a percent for some values of $m$, which the original paper handled with empirical constants tabulated for several register counts. Later work replaces the table with a bias correction computed from the actual register histogram, or with a maximum-likelihood estimator over the observed register values. The mechanism is unchanged; only the mapping from register contents to a number changes.

Maximum, not sum, is what makes merging work

The reason HyperLogLog is used in distributed systems rather than as a local trick is that the merge operation is trivial. Given two sketches over the same hash function with the same $p$, the sketch of the union is the register-wise maximum:

import hashlib

def h64(item: bytes) -> int:
    return int.from_bytes(hashlib.blake2b(item, digest_size=8).digest(), 'big')

def add(registers, item, p):
    h = h64(item)
    idx = h >> (64 - p)              # top p bits select the register
    rest = (h << p) & 0xFFFF_FFFF_FFFF_FFFF   # drop the index bits
    rank = 65 - rest.bit_length() if rest else 64 - p + 1
    registers[idx] = max(registers[idx], min(rank, 64 - p + 1))

def merge(a, b):
    assert len(a) == len(b)
    return [max(x, y) for x, y in zip(a, b)]

The correctness argument is one line: the value of register $j$ for a set $S$ is $\max_{x \in S} \rho_j(x)$, and the maximum over $S \cup T$ is the maximum of the two maxima. No element identities are needed, no counts are added, and the merge is $O(m)$ regardless of how many elements each side saw. Sums would not work here; the estimator is not linear in the data.

The union property has a limit that is often discovered late. Intersections can be estimated by inclusion-exclusion, $|A \cap B| = |A| + |B| - |A \cup B|$, but each term carries about one percent error, and when the intersection is a small fraction of the union the subtraction amplifies those errors into nonsense. Two sets of a million elements each with a thousand in common will produce an intersection estimate with an error larger than the answer. For set similarity, minwise hashing is the appropriate tool, not cardinality sketches combined arithmetically.

Where the guarantee breaks

Four assumptions underlie the error bound, and each fails in a recognisable way.

The hash must behave randomly. The $1.04/\sqrt{m}$ bound assumes each element’s hash bits are independent and uniform. A weak hash, or a hash seeded from an attacker-controlled value, lets an adversary construct inputs whose ranks are all identical, which collapses the estimate toward $m$ regardless of the true cardinality. Implementations use a keyed hash and treat the key as part of the sketch’s identity.

The registers must be shared, not concatenated. Merging sketches with different $p$ values, or different hash functions, produces a register array whose contents are not maxima over a common hash. The result is not merely imprecise; it is meaningless. The precision and the hash function are part of the sketch’s schema and must match across producers.

Cardinality is not frequency. HyperLogLog counts how many distinct values appeared, and discards multiplicity entirely. A stream of one value repeated a billion times and a stream of one value once produce identical sketches. When the question involves frequencies rather than presence, frequency moment sketches or heavy hitter summaries are the right structures, and no amount of post-processing recovers frequency information from registers.

Small streams waste the structure. For a stream of a few hundred distinct values, an exact hash set costs a few kilobytes and is correct. HyperLogLog’s advantage only appears when the distinct count exceeds roughly $m$, and its memory is fixed whether the stream holds a thousand values or a trillion. Choosing $p$ by the expected cardinality, not the maximum possible one, is the only tuning knob that matters.

The space-time trade is unusually clean here: $m$ registers of six bits give error $1.04/\sqrt{m}$, so quadrupling memory halves the error. That square-root relation is the same one that governs every averaging estimator in this cluster, and it is the reason cardinality sketches converge on a few kilobytes rather than a few hundred bytes: below that, the error is larger than most applications tolerate.

Optimal algorithms for the problem do better in theory. The Kane–Nelson–Porat construction achieves $O(1/\varepsilon^2 + \log n)$ space, which removes the $\log\log n$ factor that HyperLogLog’s estimator carries, but the improvement is asymptotic and the constants are not competitive at practical sizes. HyperLogLog remains the reference point because its per-element cost is a single hash and a register update, and its merge is a maximum.