HyperLogLog Estimator & Corrections

From Leading Zeros to Cardinality

Imagine repeatedly flipping a fair coin until the first head. Seeing one tail is ordinary; seeing ten consecutive tails is rare. If the rarest run observed is very long, many trials probably occurred. HyperLogLog applies this idea to uniformly distributed hash bits: a long prefix of zeros is evidence that many distinct values have been seen.

One maximum is far too noisy, so HLL uses stochastic averaging. A hash is split into a register index and a remaining suffix. The index sends each distinct key to one of $m=2^p$ registers. In that register, HLL stores the maximum observed rank $\rho$, where $\rho$ is one plus the number of leading zeros in the suffix. Duplicate keys repeat the same hash and cannot increase the state after their first occurrence.

This deep dive builds on the prerequisite chapter about distinct elements and cardinality sketches. That chapter explains the problem and the max-leading-zero intuition. The gap here is the complete estimator: why register maxima are combined through a harmonic-like mean, how bias and boundary regimes are corrected, what the familiar $1.04/\sqrt m$ error means, and why distributed merging is a component-wise maximum rather than arithmetic addition.

Take $p=2$, so $m=4$. Suppose four hashed values have index/suffix pairs:

• register 0, suffix 001..., rank 3;
• register 2, suffix 1..., rank 1;
• register 0, suffix 0001..., rank 4;
• register 3, suffix 01..., rank 2.

Starting from $[0,0,0,0]$, the registers become $[3,0,1,2]$. The second update to register 0 replaces 3 with 4 because registers retain maxima. Register 1 remains zero, which is valuable evidence that the cardinality is still small relative to the register count.

The principal terms are now concrete. Register maxima are the compressed observations. The harmonic mean language refers to aggregating $2^{M_j}$ through reciprocals $2^{-M_j}$, preventing one extreme register from dominating as an arithmetic mean would. Bias is systematic deviation of the raw estimator under finite $m$. Linear counting uses the number of zero registers in the small range. Saturation occurs when hash suffixes or register widths cannot represent a larger rank. Relative standard error describes run-to-run dispersion relative to true cardinality under the hash model.

Registers, Harmonic Means and Raw Estimates

Let a uniform $L$-bit hash be split into a $p$-bit prefix and a $q=L-p$ bit suffix. The prefix chooses $j\in\{0,\ldots,m-1\}$ with $m=2^p$. Define $\rho(w)$ as one plus the number of leading zeros in suffix $w$, capped according to the implementation. For each canonical key $x$,

$$ M_j\leftarrow\max(M_j,\rho(w)). $$

If the same key appears again, it maps to the same $j,w$, so the update is idempotent. This is why HLL estimates distinct keys rather than event count.

Within one register, a rank at least $r$ occurs with probability $2^{-(r-1)}$. A maximum near $r$ therefore suggests a substream cardinality on the scale of $2^r$. Directly averaging these exponentials is unstable: rare large registers dominate. HLL instead uses

$$ Z=\sum_{j=0}^{m-1}2^{-M_j}, \qquad E_{\mathrm{raw}}=\alpha_m\frac{m^2}{Z}. $$

This is proportional to the harmonic mean of the per-register scales $2^{M_j}$. The constant $\alpha_m$ corrects systematic behavior of the idealized register distribution. A traditional implementation uses $0.673,0.697,0.709$ for $m=16,32,64$, and approximately

$$ \alpha_m=\frac{0.7213}{1+1.079/m} $$

for larger $m$. Modern variants may use empirically calibrated bias tables or different estimators; constants and correction rules must travel with the serialized algorithm version.

The asymptotic relative standard error of classical HLL is about

$$ \operatorname{RSE}\approx\frac{1.04}{\sqrt m}. $$

Thus $p=14$ gives $m=16{,}384$ registers and approximate RSE $0.8125\%$. Doubling precision requires roughly four times as many registers. If registers use 6 bits, the dense payload is $98{,}304$ bits or 12 KiB, before headers and alignment.

The derivation requires near-uniform independent-looking hashes across both prefix and suffix, a correctly defined zero-count rank, enough hash width, and unsaturated registers. Using low-quality low bits for the index while the remaining bits are correlated is a counterexample: register load and ranks cease to follow the model even if the raw hash values look varied.

flowchart TD
    A[Canonical distinct key] --> B[Uniform L-bit hash]
    B --> C[Prefix chooses one of m registers]
    B --> D[Suffix gives leading-zero rank rho]
    C --> E[Update register by maximum]
    D --> E
    E --> F[Compute Z as sum of 2 to minus M]
    F --> G[Raw estimate alpha m times m squared over Z]
    G --> H[Expected RSE about 1.04 over square root m]
    B --> X{Uniform split enough width compatible version?}
    X -->|no| Y[Bias merge or saturation guarantee fails]
    X -->|yes| C
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,D navy;
    class E,F purple;
    class G,H teal;
    class X,Y crimson;

Small-Range and Large-Range Corrections

The raw estimator behaves poorly when many registers are still zero. In the classical small range, let $V$ be the number of zero registers. Occupancy reasoning gives the linear-counting estimate

$$ E_{\mathrm{small}}=m\ln\left(\frac mV\right), $$

provided $V\gt0$. A traditional switching rule uses linear counting when the raw estimate is at most about $2.5m$ and zero registers remain. This threshold is historical and implementation-specific; HLL++-style systems may use sparse representations and empirically learned bias correction instead.

At the opposite extreme, a finite $L$-bit hash space has only $2^L$ possible values. Hash collisions then suppress observed distinctness. A classical large-range correction is

$$ E_{\mathrm{large}}=-2^L\ln\left(1-\frac{E_{\mathrm{raw}}}{2^L}\right), $$

often associated with a threshold near $2^L/30$. It is valid only while the logarithm's argument is positive and under its occupancy approximation. With 64-bit hashes, cardinalities approaching this regime require careful collision, numeric, and security analysis rather than blind formula use.

Register saturation is another large-range limit. With $q$ suffix bits, the largest observable zero run is finite. A packed register of width $r$ bits also caps the stored rank at $2^r-1$. The effective maximum is the smaller of the hash-derived and encoding-derived limits. Silent clipping causes downward bias.

from hashlib import blake2b
from math import log, sqrt

def alpha_m(m):
    if m == 16: return 0.673
    if m == 32: return 0.697
    if m == 64: return 0.709
    return 0.7213 / (1.0 + 1.079 / m)

class HyperLogLog:
    def __init__(self, p=10, hash_bits=64):
        if not 4 <= p < hash_bits:
            raise ValueError("require 4 <= p < hash_bits")
        if hash_bits != 64:
            raise ValueError("this reference implementation uses 64-bit hashes")
        self.p = p
        self.m = 1 << p
        self.hash_bits = hash_bits
        self.registers = [0] * self.m

    def add(self, value):
        digest = blake2b(str(value).encode(), digest_size=8,
                         person=b"hll-demo").digest()
        hashed = int.from_bytes(digest, "big")
        index = hashed >> (self.hash_bits - self.p)
        suffix_bits = self.hash_bits - self.p
        suffix = hashed & ((1 << suffix_bits) - 1)
        rank = suffix_bits + 1 if suffix == 0 else suffix_bits - suffix.bit_length() + 1
        self.registers[index] = max(self.registers[index], rank)

    def raw_estimate(self):
        z = sum(2.0 ** (-register) for register in self.registers)
        return alpha_m(self.m) * self.m * self.m / z

    def estimate(self):
        raw = self.raw_estimate()
        zeros = self.registers.count(0)
        if raw <= 2.5 * self.m and zeros > 0:
            return self.m * log(self.m / zeros), "linear-counting"
        hash_space = float(1 << self.hash_bits)
        if raw > hash_space / 30.0:
            if raw >= hash_space:
                raise OverflowError("estimate exceeds finite hash space")
            return -hash_space * log(1.0 - raw / hash_space), "large-range"
        return raw, "raw"

    def merge(self, other):
        if (self.p, self.hash_bits) != (other.p, other.hash_bits):
            raise ValueError("incompatible HLL precision or hash width")
        self.registers = [max(a, b) for a, b in
                          zip(self.registers, other.registers)]

#Normal deterministic cardinality and duplicate test.
hll = HyperLogLog(p=10)
for value in range(50_000):
    hll.add(value)
for value in range(10_000):
    hll.add(value)
estimate, regime = hll.estimate()
relative_error = (estimate - 50_000) / 50_000
print("estimate regime relative error RSE:",
      estimate, regime, relative_error, 1.04 / sqrt(hll.m))
assert abs(relative_error) < 0.08

#Merge invariant with overlap: union is 75,000, not sum 100,000.
left, right = HyperLogLog(10), HyperLogLog(10)
for value in range(50_000): left.add(value)
for value in range(25_000, 75_000): right.add(value)
left.merge(right)
merged, _ = left.estimate()
print("merged union estimate:", merged)
assert abs(merged - 75_000) / 75_000 < 0.08

#Small-range and boundary checks.
small = HyperLogLog(10)
for value in range(100): small.add(value)
small_estimate, small_regime = small.estimate()
assert small_regime == "linear-counting"
assert abs(small_estimate - 100) < 20
try:
    left.merge(HyperLogLog(11))
except ValueError as error:
    print("invalid merge passed:", error)

Merging Cardinalities Across Partitions

HLL's merge operation follows directly from its state invariant. For compatible sketches A and B,

$$ M_j^{A\cup B}=\max(M_j^A,M_j^B) $$

for every register. The maximum is associative, commutative, and idempotent, so merge order and duplicate delivery do not change the result. Overlap is handled naturally because a repeated key contributes the same hash observation. Adding estimates is wrong whenever partitions overlap and discards register-level evidence even when they do not.

In a teaching case, two four-register sketches $[3,0,1,2]$ and $[1,4,1,0]$ merge to $[3,4,1,2]$. Neither vector addition nor averaging preserves the maximum-rank interpretation.

At professional scale, daily active-user sketches may be produced by many shards and merged across regions. Every sketch must share precision $p$, hash algorithm and seed, key canonicalization, register/rank convention, correction version, and time-window semantics. Headers should make incompatibility explicit. Downsampling higher precision to lower precision needs a proven conversion; blindly truncating arrays or merging different $m$ values is invalid.

Failure and adversarial cases center on hash trust and semantics. If tenants can choose keys against an exposed weak hash, they may concentrate registers or engineer extreme ranks. If one service hashes UTF-8 normalized IDs and another hashes raw bytes, their “same” users do not deduplicate. Hash-seed rotation prevents direct merging across versions. Window retries are harmless only when the same sketch update is idempotent at the key-hash level; misassigned windows change the target population.

Evidence that invalidates the design includes merge results differing by order, nonzero estimates for empty state, persistent bias versus exact shadow counts, register histograms inconsistent with uniform occupancy, saturation, incompatible header acceptance, or error far outside calibrated confidence bands.

flowchart TD
    A[Define distinct identity and window] --> B[Fix hash seed precision and version]
    B --> C[Build one HLL per partition]
    C --> D[Validate compatibility headers]
    D --> E{All contracts match?}
    E -->|no| F[Reject or perform proven conversion]
    E -->|yes| G[Merge each register by maximum]
    G --> H[Compute raw union estimate]
    H --> I[Apply one documented correction regime]
    I --> J[Compare sampled windows with exact oracle]
    J --> K{Bias RSE and saturation acceptable?}
    K -->|yes| L[Deploy and monitor histograms]
    K -->|no| M[Reject resize or repair hashing]
    L --> N{Drift or version breach?}
    N -->|yes| M
    N -->|no| L
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,D navy;
    class G,H,I purple;
    class J,L teal;
    class E,F,K,M,N crimson;

Implement and Validate HyperLogLog

Implementation quality depends on bit conventions that prose often hides. Specify whether prefix or suffix selects the register, whether $\rho$ starts at 1, how an all-zero suffix is ranked, how registers pack across words, and which correction table/version is used. Golden vectors should verify hashes, indices, ranks, serialized bytes, merges, and estimates across languages.

This bridges backward to distinct counting and maximum-rank sketches, and forward to HLL++, sparse encodings, intersection estimation, set sketches, privacy-preserving telemetry, and distributed sketch governance. HLL estimates unions naturally; intersections obtained by subtracting noisy union estimates can be unstable and require separate analysis.