HyperLogLog

HyperLogLog (HLL) is a sublinear probabilistic streaming algorithm and data sketch in computation and algorithms that estimates the cardinality n = |S| (the number of distinct elements, or the zeroth frequency moment F₀) of a massive multiset or data stream in a single pass using O(ε⁻² log log N_max) bits of memory. Formulated by French computer scientist Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier in 2007—culminating a quarter-century progression from the Flajolet–Martin Probabilistic Counting algorithm (1985) and Durand–Flajolet LogLog (2003)—HyperLogLog can count up to N_max > 10⁹ (or 2⁶⁴ in 64-bit HLL++) distinct items with a standard error of ≈ 1.04 / √m using only m = 2^p small 5-bit or 6-bit integer registers.

Whereas computing distinct counts (COUNT DISTINCT) requires storing every unique key seen so far in a hash table or balanced search tree using Ω(n log n) bits of memory—which consumes gigabytes of RAM when tracking billions of unique IP addresses, web search queries, or genomic k-mers—a standard HyperLogLog sketch with p = 14 (m = 16,384 registers of 6 bits each) occupies just 12 KB of memory (or 1.5 KB at p = 11) and estimates cardinalities across any scale with a relative standard error below 0.81%. Alongside companion streaming structures such as the Bloom filter, Count–Min sketch, and MinHash, HyperLogLog is built directly into Redis (PFADD/PFCOUNT), Google BigQuery (APPROX-COUNT-DISTINCT), Amazon Redshift, Apache Spark, Presto/Trino, ClickHouse, and bioinformatics genome-distance estimators (Dashing).

Binary Prefix Rarity as a Cardinality Estimator

HyperLogLog relies on a fundamental statistical property of a uniform hash function h : U → {0, 1}^L (typically L = 64 bits): if h maps distinct input elements independently to uniformly distributed binary strings, then in the hashed stream:

• Every 2nd distinct element (with probability 1/2) begins with bit pattern 1... (run of 0 leading zeros, ρ = 1).
• Every 4th distinct element (probability 1/4) begins with 01... (1 leading zero, ρ = 2).
• Every 2^k-th distinct element (probability 2^−k) begins with k − 1 leading zeros followed by a 1 (0^(k-1) 1..., position of leftmost 1-bit ρ = k).

Therefore, if the maximum position of the leftmost 1-bit observed across all distinct elements in a stream is M = max_x∈S ρ(h(x)), then 2^M provides an order-of-magnitude estimate of the distinct cardinality n. However, a single maximum estimator 2^M is discrete (jumping only by powers of 2) and suffers from infinite asymptotic variance.

Substream Bucketing (Stochastic Averaging) and Register Updates

To suppress variance without evaluating multiple hash functions per element, Flajolet and Martin introduced stochastic averaging, which partitions the single 64-bit hash value y = h(x) of each incoming element x into two fields using a precision parameter p ∈ [4, 18]:

1. Bucket Index (j): The first p bits of y select one of m = 2^p independent substream registers M[0 .. m − 1] (initialized to 0).
2. Leading-Zero Rank (ρ(w)): In the remaining L − p = 64 − p bits w, let ρ(w) ∈ {1, 2, ..., 65 − p} denote the 1-based position of the first 1-bit (or number of leading zeros plus 1).
3. Register Update: Update register j via the idempotent maximum operation:

Because ρ(w) ≤ 64 − p + 1 ≤ 61, each register M[j] requires only 6 bits of storage (5 bits for 32-bit hashes). Each substream receives on average n / m distinct elements in O(1) time per element.

From Arithmetic Mean (LogLog) to Harmonic Mean (HyperLogLog)

In the earlier LogLog algorithm (Durand & Flajolet, 2003), the m register values were combined via the geometric mean (arithmetic mean of M[j] in the exponent): 2^{(1/m) ∑ M[j]}, achieving standard error ≈ 1.30 / √m. In HyperLogLog (2007), Flajolet et al. replaced the geometric mean with the harmonic mean of 2^M[j] across all m substreams:

Because the harmonic mean strongly damps upward outliers caused by rare long runs of leading zeros in a single bucket, it reduces the asymptotic relative standard error (RSE) from 1.30 / √m down to β_∞ / √m = √(3 ln 2 − 1) / √m ≈ 1.03896 / √m—close to the information-theoretic efficiency limit for register sketches. The bias-correction constant α_m is given analytically by:

(with α₁₆ = 0.673, α₃₂ = 0.697, and α₆₄ = 0.709).

Small-Range Linear Counting and HLL++ 64-Bit Enhancements

When the true cardinality n is small relative to m (n ≤ (5/2)m), many registers remain equal to 0 (V = |{j : M[j] = 0}| > 0), and the asymptotic harmonic-mean formula exhibits upward bias. Whenever E ≤ (5/2)m and V > 0, HyperLogLog switches automatically to Whang's Linear Counting estimator (occupancy problem on V empty buckets):

In 2013, Stefan Heule, Marc Nunkesser, and Alexander Hall at Google introduced HyperLogLog++ (HLL++), which upgraded the hash width from 32 bits to 64 bits (eliminating hash-collision saturation above 2³² ≈ 4.29 × 10⁹ items), replaced Linear Counting bias jumps with empirical polynomial bias-correction tables for n < 5m, and introduced a sparse representation that stores only non-zero (j, ρ) pairs in a compressed list when n ≪ m.

A pivotal algebraic property of HyperLogLog in distributed MapReduce and OLAP databases is lossless commutative and associative mergeability: given two HyperLogLog sketches M_A and M_B constructed over sets A and B using the same precision p and hash function h, the sketch of their union A ∪ B is obtained by taking the elementwise maximum across all m registers in O(m) time:

The merged sketch M_A∪B is bit-for-bit identical to the sketch that would have been produced by streaming all elements of A ∪ B into a single estimator, with zero degradation in accuracy regardless of how many thousands of shards or daily partitions are merged. In bioinformatics, tools such as Dashing (Baker & Langmead, 2019) use SIMD-vectorized HyperLogLog sketches of canonical DNA k-mers with Ertl's maximum-likelihood estimator to compute genomic MinHash-like Jaccard similarities and Mash distances across > 100,000 microbial assemblies faster and in less memory than bottom-k sketches.

Why does HyperLogLog use the harmonic mean instead of the arithmetic or geometric mean of 2^M[j]?

The distribution of 2^M[j] has a heavy right tail: with probability 2^−k, a single lucky element hashes to k leading zeros and contributes 2^k. Under an arithmetic mean, a single outlier dominates the entire sum and gives infinite variance; the geometric mean (used in LogLog) tames the variance to 1.30 / √m; the harmonic mean (m / ∑ 2^−M[j]) weights each register by 2^−M[j], nearly nullifying large outliers and lowering the standard error to 1.04 / √m.

How can HyperLogLog estimate the intersection |A ∩ B| of two sets?

Unlike unions (M_A∪B[j] = max(M_A[j], M_B[j])), there is no exact register-level operation for set intersection. Instead, |A ∩ B| is estimated via the inclusion-exclusion principle |A ∩ B| ≈ |A| + |B| − |A ∪ B| (or via Otmar Ertl's joint Poisson maximum-likelihood estimator on register comparisons M_A[j] < M_B[j], M_A[j] = M_B[j], and M_A[j] > M_B[j]). Note that when |A ∩ B| is a tiny fraction of |A ∪ B|, inclusion-exclusion error scales with |A ∪ B|, so MinHash or Theta sketches are preferred for small-overlap intersections.

Can elements be deleted from a standard HyperLogLog sketch?

No. Because each register M[j] records only the maximum leading-zero rank ρ(w) observed so far without storing the count or history of lower-rank items in bucket j, deleting an item that achieved the maximum cannot restore the previous second-highest rank (requiring a sliding-window HyperLogLog that stores a small monotonically decreasing timestamped list of (t, ρ) pairs per bucket, at most O(log log n) entries per register).

1. Flajolet, P., & Martin, G. N. (1985). "Probabilistic counting algorithms for data base applications." Journal of Computer and System Sciences, 31(2), 182–209. https://doi.org/10.1016/0022-0000(85)90041-890041-8)
2. Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm." 2007 Conference on Analysis of Algorithms (AofA 07), Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, AH, 127–146. https://doi.org/10.46298/dmtcs.3545
3. Heule, S., Nunkesser, M., & Hall, A. (2013). "HyperLogLog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm." Proceedings of the 16th International Conference on Extending Database Technology (EDBT '13), 683–692. https://doi.org/10.1145/2452376.2452456
4. Ertl, O. (2017). "New cardinality estimation algorithms for HyperLogLog sketches." arXiv preprint arXiv:1702.01284. https://doi.org/10.48550/arXiv.1702.01284
5. Baker, D. N., & Langmead, B. (2019). "Dashing: fast and accurate genomic distances with HyperLogLog." Genome Biology, 20(1), 265. https://doi.org/10.1186/s13059-019-1875-0