· Development

HyperLogLog: How the Harmonic Mean Estimates Distinct Counts, and What 1.04/√m Assumes

How HyperLogLog, per the 2007 Flajolet et al. paper, estimates distinct counts with register index j and ρ, why it uses a harmonic mean, its range corrections, and what 1.04/√m assumes.

algorithmsdata-structureshyperloglogcardinality-estimation

The number of distinct elements in a collection with repeats is called its cardinality. One example the paper gives is network traffic: how many different source–destination address pairs appeared in packet headers during a time slice. Counting that exactly means remembering every value already seen, so the storage needed grows roughly in proportion to the number of elements.

The 2007 paper “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm” by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier (AofA 2007, DMTCS Proceedings vol. AH, pp. 127–146) presents an algorithm that estimates cardinality in a single pass using m small registers, and shows that its relative error (standard error) is typically about 1.04/√m. This post follows the PDF of that paper published on Flajolet’s INRIA page. It covers how the register index j and the value ρ are computed, why the registers are combined with a harmonic mean, which assumptions sit behind the number 1.04/√m, and which conclusions the estimate does not support. Later variants such as HyperLogLog++ and database-specific implementations are out of scope.

One observable: ρ

Treat a hash value as a string of bits and define ρ(s) as the position of the leftmost 1-bit in s, counting from 1. So ρ(1…) = 1 and ρ(0001…) = 4; ρ is one plus the number of leading zeros.

The paper assumes the bits of hashed values are independent and each is 1 with probability 1/2. Then the probability that ρ ≥ k is 2^(1−k) (Section 2.1). Seeing a value that starts with 0^(ρ−1)1 suggests that there are roughly 2^ρ or more distinct values, and the paper itself only calls this “more or less a likely indication.” Equal values have equal hashes and therefore equal ρ, so the maximum ρ does not depend on how often any value repeats. That is what makes it usable for counting distinct elements.

A single observable varies too much. Running m experiments with m different hash functions would bring the standard deviation of the mean down to σ/√m, but the paper points out two problems: every element would need m hash computations, and no construction is known for a large set of independent hash functions. Instead it uses stochastic averaging, introduced with the Probabilistic Counting algorithm of Flajolet and Martin. The first b bits of a single hash value pick one of m = 2^b substreams, and a separate observable is kept per substream. Each element is hashed once.

For background on hash functions themselves, see the post on hash functions.

Register index j and ρ(w): where the +1s come from

Figure 2 of the paper specifies the algorithm:

  1. Let m = 2^b with b a positive integer, and initialize registers M[1], …, M[m] to −∞.
  2. For each element v, compute x = h(v).
  3. j = 1 + ⟨x₁x₂…x_b⟩₂. The register index is the first b bits of x read as a binary number, plus one.
  4. w = x_{b+1}x_{b+2}…. Take what remains after removing the first b bits, compute ρ(w), and set M[j] = max(M[j], ρ(w)).
  5. After all elements have been read, compute Z and E (next section).

There are two separate +1s, which is where implementations tend to slip. The +1 in j is there because the paper numbers registers from 1; with a zero-based array, use the value of the first b bits directly as the index. The +1 in ρ is part of ρ’s definition and stays regardless of how you index the array. Also, ρ is taken over w, not over the whole of x, because the first b bits have already been used to choose the register.

Here is an example constructed for this post. Take a 32-bit hash, b = 4 (m = 16), and x = 0x502C0000.

Item Value
x (binary) 0101 0000 0010 1100 0000 0000 0000 0000
First 4 bits 0101 = 5
Paper’s j (from 1) 6
Zero-based array index 5
w (remaining 28 bits) 0000 0010 1100 0000 0000 0000 0000
Leading zeros in w 6
ρ(w) 7

With a finite hash, w can be all zeros. Figure 3, which assumes a 32-bit hash, defines ρ(0^K) = K + 1, so in that case ρ(w) = 32 − b + 1. Register values therefore lie between 0 and L + 1 − log₂m, where L is the number of hash bits, and the paper notes that with 32-bit hashes 5 bits per register (“short bytes”) are enough.

Combining with a harmonic mean

Once all elements have been read, the algorithm computes (equations (2) and (3) in the paper):

Z   = ( Σ_{j=1..m} 2^(−M[j]) )^(−1)
E   = α_m · m² · Z
α_m = ( m · ∫₀^∞ ( log₂((2 + u)/(1 + u)) )^m du )^(−1)

m·Z is the harmonic mean of the m values 2^M[j]. The paper’s intuition goes like this. With n distinct values, each substream receives about n/m of them, so M[j] should be close to log₂(n/m) and the harmonic mean of the 2^M[j] should be on the order of n/m. Multiplying by m once more, m²Z is on the order of n, and α_m corrects the systematic multiplicative bias left in m²Z.

On the choice of the harmonic mean, the paper says the following. Its predecessor LOGLOG, which uses the same observable, combines registers with what amounts to a geometric mean. Harmonic means tame probability distributions with slowly decaying right tails, so here they act as a variance-reduction device; the paper credits the idea to a note by Chassaing and Gérin that it cites. As this post’s own explanation: when one register happens to receive a large ρ, 2^M[j] becomes very large, but in the harmonic mean its reciprocal 2^(−M[j]) just moves toward zero, so it has little effect on the total.

Figure 1 of the paper lists LOGLOG’s accuracy as 1.30/√m and HyperLogLog’s as 1.04/√m, and the paper says HyperLogLog matches LOGLOG’s accuracy with 64% of the memory. Since the error scales as 1/√m, the m needed for the same error is (1.04/1.30)² = 0.64 times as large, which agrees (this post’s check).

What Theorem 1 says, and what it assumes

The analysis in Sections 2 and 3 assumes that the collection of hashed values is an “ideal multiset.” By Definition 1, that is a sequence obtained by arbitrary replications and permutations applied to n independent, uniformly distributed random variables on [0, 1]. The paper describes this as a natural way to model the output of well-designed hash functions. It treats hash values as infinite bit strings, and adds that in practice hashing on 32 bits suffices to estimate cardinalities above 10⁹.

Under this model, for the estimate E produced with m ≥ 3 registers, Theorem 1 states:

  • (i) Bias: as n → ∞, E_n(E)/n = 1 + δ₁(n) + o(1), with |δ₁(n)| < 5·10⁻⁵ once m ≥ 16.
  • (ii) Standard error: as n → ∞, √V_n(E)/n = β_m/√m + δ₂(n) + o(1), with |δ₂(n)| < 5·10⁻⁴ once m ≥ 16. The constants are β₁₆ ≈ 1.106, β₃₂ ≈ 1.070, β₆₄ ≈ 1.054, β₁₂₈ ≈ 1.046, with limit β_∞ = √(3 log 2 − 1) ≈ 1.03896.

Three points matter when reading this. Both results are asymptotic in n → ∞. The standard error is, in the paper’s words, the typical relative error “in a mean quadratic sense,” not a bound that each estimate stays within. And δ₁ and δ₂ are oscillating functions of tiny amplitude that the paper says can be neglected for practical purposes. The figure 1.04/√m comes from β_m approaching about 1.039 as m grows. The same analysis gives α_m → 1/(2 log 2) ≈ 0.72134 (equation (29), with log the natural logarithm).

The proof first lets the number of elements follow a Poisson law (poissonization), derives asymptotics with Mellin transforms, and then returns to fixed n by analytic depoissonization. The variance analysis follows the same lines and is only sketched.

The raw estimate and two corrections

Figure 2 is the algorithm as analysed; Figure 3 is the program meant for practical use. Figure 3 is dimensioned for 32-bit hashes, cardinalities up to 10⁹, and m = 2⁴ to 2¹⁶ (b ∈ [4..16]). Compared with Figure 2 it changes the initialization and adds two final corrections. It uses these constants for α_m:

α_16 = 0.673,  α_32 = 0.697,  α_64 = 0.709,  α_m = 0.7213 / (1 + 1.079/m)  (m ≥ 128)

initialize registers to 0 and update them as in Figure 2, then
E = α_m · m² · ( Σ_{j=1..m} 2^(−M[j]) )^(−1)          raw estimate

if E ≤ (5/2)·m
    V = number of registers equal to 0
    if V ≠ 0 then E* = m · log(m/V) else E* = E      small range correction
if E ≤ (1/30)·2³² then E* = E                       intermediate range, no correction
if E > (1/30)·2³² then E* = −2³² · log(1 − E/2³²)    large range correction

Initialization. With registers initialized to −∞ as in Figure 2, a single empty register makes 2^(−M[j]) infinite and E = 0. Citing the coupon collector problem, the paper says one should expect E = 0 when n ≪ m log m, so the algorithm errs badly for small cardinalities. Figure 3 initializes registers to 0 instead. The paper explains that the conclusions of Theorem 1 still apply, because once n ≫ m log m all substreams are nonempty with overwhelming probability.

Small range correction. Initializing to 0 still leaves a problem when n is small. According to the paper, extensive simulations show that for m ≥ 16 the asymptotic regime is practically reached at n = (5/2)m, while below that nonlinear distortions appear. In the extreme case n = 0, the raw estimate is α_m·m ≈ 0.7m. So when E is small relative to m, the program uses the number of empty registers. Throwing n balls at random into m bins leaves about m·e^(−n/m) bins empty, so observing V empty bins suggests n ≈ m log(m/V). The paper relates this to the same random-allocation property used by the Hit Counting algorithm of Whang et al. Because the formula comes from e^(−n/m), log here is the natural logarithm (this post’s reading). The threshold (5/2)m comes from simulations, not from the theorem.

Large range correction. With an L-bit hash there are only 2^L distinct hash values, so as n approaches 2^L, hash collisions become more frequent. The paper explains that E then estimates the number of distinct hashed values, which with high probability is about 2^L(1 − e^(−n/2^L)). Solving for n gives n = −2^L log(1 − E/2^L), which Figure 3 uses with L = 32. The text gives no separate derivation for the threshold (1/30)·2³². By this post’s calculation, the argument of the log is zero or negative when E ≥ 2³², so the formula is undefined there; Figure 3 was dimensioned for cardinalities up to 10⁹ in the first place.

Figure 3’s pseudocode writes the three conditions as separate if statements. Executed literally in order, the second if would overwrite the small range result with E whenever E ≤ (5/2)m. Since the comments split the cases into “small range,” “intermediate range,” and “large range,” this post reads the three conditions as mutually exclusive ranges, and the code below does the same.

Memory and error in numbers

The following table is this post’s calculation. The error column is 1.04/√m, and the memory column is the size of the register array at 5 bits per register. For small m, such as m = 16, the β₁₆ = 1.106 from Theorem 1 gives a more accurate 1.106/√16 ≈ 27.7%.

b m 1.04/√m Register array (5 bits × m)
4 16 26% 10 bytes
8 256 6.5% 160 bytes
10 1,024 3.25% 640 bytes
11 2,048 about 2.3% 1,280 bytes
16 65,536 about 0.41% 40,960 bytes

The abstract and introduction say that with m = 2048, 32-bit hashing, and 5-bit registers, cardinalities well beyond 10⁹ can be estimated with a typical accuracy of 2% using 1.5 kB. By the calculation above, 1.04/√2048 ≈ 2.3% and the register array is 1,280 bytes, so the paper’s 2% and 1.5 kB are best read as rounded figures. The simulation plots in Figure 4 likewise mark the predicted standard error as ±7% for m = 256, ±3% for m = 1024, and ±0.5% for m = 65536.

Section 4 explains the “near-optimal” in the title with two facts. One is a lower bound: maintaining ε-approximate counts up to N requires Ω(log log N) bits. According to the introduction, each HyperLogLog register needs at most log₂log₂N + O(1) bits, which is of the same order. The other fact is a result of Chassaing and Gérin, cited by the paper, that for a wide class of algorithms based on order statistics the best achievable accuracy is bounded below by a quantity close to 1/√m. On that basis the paper puts HyperLogLog about 4% off that bound. This post did not open the Chassaing–Gérin paper, so it only reports that the HyperLogLog paper cites it this way.

A Python translation

The code below translates Figure 3 into Python. It differs from the paper in these ways. Register indices are zero-based, so no 1 is added to j. The three ranges are treated as mutually exclusive, as discussed above. The hash is the first 32 bits of a SHA-1 digest. The paper mentions sha1 as one example of practical methods that support its hashing assumption; the code follows that mention for illustration and claims nothing about speed or any other property.

import hashlib
import math


def hll_estimate(items, b=11):
    """Translation of the HyperLogLog program in Figure 3. items is an iterable of strings."""
    if not 4 <= b <= 16:
        raise ValueError("Figure 3 covers b in 4..16")
    m = 1 << b
    alpha = {16: 0.673, 32: 0.697, 64: 0.709}.get(m, 0.7213 / (1 + 1.079 / m))
    registers = [0] * m  # Figure 3: initialized to 0, not −∞
    for v in items:
        x = int.from_bytes(hashlib.sha1(v.encode("utf-8")).digest()[:4], "big")  # 32 bits
        j = x >> (32 - b)                 # first b bits; the paper's j is this + 1
        w = x & ((1 << (32 - b)) - 1)     # remaining 32 − b bits
        rho = (32 - b) - w.bit_length() + 1  # position of leftmost 1; 32 − b + 1 if w == 0
        registers[j] = max(registers[j], rho)
    e = alpha * m * m / sum(2.0 ** -r for r in registers)  # raw estimate
    if e <= 2.5 * m:
        v = registers.count(0)
        return m * math.log(m / v) if v else e  # small range correction
    if e <= 2**32 / 30:
        return e  # intermediate range, no correction
    return -(2**32) * math.log(1 - e / 2**32)  # large range correction


print(round(hll_estimate(f"item-{i}" for i in range(100_000))))

The printed value is one estimate determined by the hash and the input, and nothing guarantees that it equals 100,000. With b = 11 the typical relative error from Theorem 1 is about 2.3%, but as discussed above that is not a limit on any single run. The code also does not handle E ≥ 2³² separately.

What the estimate does not tell you

  • That the error is a deterministic bound. 1.04/√m is a standard error. The paper expects estimates to be approximately Gaussian (and says the simulations in Figure 4 support this), and with σ ≈ 1.04/√m it expects estimates to fall within σ, 2σ, and 3σ of the exact count in 65%, 95%, and 99% of cases respectively. Put the other way, estimates beyond 3σ are within what the paper expects.
  • That Theorem 1 covers small n. Theorem 1 is an asymptotic result for n → ∞. The small range correction and its threshold (5/2)m rest on simulations.
  • That the numbers hold without the hashing assumption. The analysis assumes independent, uniform hash bits. The paper does not analyse hash functions that fail this assumption, or inputs chosen deliberately by someone who knows the hash.
  • That it works past the hash space. With 32-bit hashing, as n approaches 2³², E starts estimating the number of distinct hash values, which Figure 3 handles with the large range correction. Figure 3’s dimensions and constants are for cardinalities up to 10⁹ and m = 2⁴ to 2¹⁶.
  • That the experiments generalize. The paper’s experiments date from 2007. Figure 4 shows simulations on ideal multisets made from random uniform data (its histograms use 500 and 250 runs), and Figure 5 shows results with m = 2048 on 458 chunks of about 40,000 lines each, taken from octal dumps of the PostScript source of a book. The remark that running time is dominated by hashing, making the program only three to four times slower than a plain scan with wc -l, is likewise an observation from that time.
  • That it supports operations it does not define. The paper says that for an arbitrary partition of a file into subfiles, it suffices to collect the register values and take the componentwise max (footnote 4). Figures 2 and 3, however, only ever raise registers with max, so there is no operation for deleting an element (this post’s reading). The paper also does not cover estimating the size of an intersection.
  • That it answers the same question as a Bloom filter. A Bloom filter answers membership queries, whether a value was inserted before; HyperLogLog estimates how many distinct values there are. They answer different questions.
  • That later variants share this paper’s properties. HyperLogLog++ and other later variants, as well as database-specific implementations, are outside the scope of this post; the constants and thresholds here refer to Figure 3 of the 2007 paper.

Sources

Both pages were checked on 2026-10-20. No source on later variants or database implementations was used.

Back to the blog