HyperLogLog

HyperLogLog (HLL) is a one-pass, mergeable estimator for the number of distinct values. It replaces a set of all values with m = 2^p small registers.

Update rule

1. Serialize the logical value canonically and hash it with a stable, well-distributed hash.
2. Use p hash bits to select register j.
3. Let rho be the position of the first 1 bit in the remaining suffix.
4. Update M[j] = max(M[j], rho).

A duplicate produces the same register and rank, so the update is idempotent. HLL is still an estimate: finite hash width can collide and the estimator has statistical error.

Estimate and error

The classic raw estimator is:

E = alpha_m * m^2 / sum(j=1..m, 2^(-M[j]))

For the original HLL analysis, the asymptotic relative standard error is about 1.04 / sqrt(m). That is a standard error under the paper's hash model, not a hard bound for every answer. Small- and large-range corrections, sparse encodings, and empirical bias correction are variant-specific; record the implementation and estimator version instead of mixing formulas.

Distributed merge contract

The union of compatible sketches is the register-wise maximum. It is associative, commutative, and idempotent, so retrying a merge is safe.

Fail closed unless both sketches have the same:

• precision and register count;
• hash function, seed, and hash width;
• value normalization and namespace;
• estimator/encoding contract;
• time-window semantics.

Register-wise maximum estimates union. It cannot recover exact set difference or intersection, and overlapping sliding windows need an explicit windowed design.

Operational guardrails

Persist precision, hash/version, namespace, and window beside the registers. Monitor saturation and compare sampled exact counts. Use an exact source of truth for billing, authorization, quota enforcement, or deduplication that must never admit a duplicate.

Diagram scenarios

The animation covers a register update, duplicate idempotence, compatible distributed merge, incompatible-merge rejection, and correct interpretation of statistical error.

Related concept

Interactive scenarios