HyperLogLog, in depth: why the estimator works, choosing precision, validating an implementation and querying stored sketches

From coin flips to registers

Start with coin flips. Hash an item to a uniform bit string and look at the position of the first 1 bit, counting from the left and starting at 1. That position is the item's rank. Half of all hashes have rank 1, a quarter rank 2, and in general the probability that a rank is at least k is 2^-(k-1). Duplicates hash to the same bits, so they produce the same rank and change nothing. That is where distinctness comes from: the sketch reacts only to new values.

If you have seen n distinct items, the largest rank among them is around log2(n), because you need roughly 2^k tries to see a run of k - 1 leading zeros. So 2^max(rank) is a cardinality estimate. It is also a very noisy one, because a single lucky hash can double or quadruple it. Flajolet-Martin (1985) and LogLog (2003) both reduce that noise with stochastic averaging. Use a few hash bits to split the stream into m buckets, keep one maximum rank per bucket, and average the m estimates, each of which describes about n/m items.

HyperLogLog, from Flajolet, Fusy, Gandouet and Meunier in 2007, changed the average. LogLog used a geometric mean of the per-bucket estimates. HLL uses a harmonic mean, which damps the outliers that dominate the others: one bucket with an unusually high register pulls a harmonic mean up far less than it pulls up an arithmetic or geometric one. The result is a relative standard error of about 1.04 divided by the square root of m, against roughly 1.30 for LogLog with the same memory.

From coin flips to registers

Start with coin flips. Hash an item to a uniform bit string and look at the position of the first 1 bit, counting from the left and starting at 1. That position is the item's rank. Half of all hashes have rank 1, a quarter rank 2, and in general the probability that a rank is at least k is 2^-(k-1). Duplicates hash to the same bits, so they produce the same rank and change nothing. That is where distinctness comes from: the sketch reacts only to new values.

If you have seen n distinct items, the largest rank among them is around log2(n), because you need roughly 2^k tries to see a run of k - 1 leading zeros. So 2^max(rank) is a cardinality estimate. It is also a very noisy one, because a single lucky hash can double or quadruple it. Flajolet-Martin (1985) and LogLog (2003) both reduce that noise with stochastic averaging. Use a few hash bits to split the stream into m buckets, keep one maximum rank per bucket, and average the m estimates, each of which describes about n/m items.

HyperLogLog, from Flajolet, Fusy, Gandouet and Meunier in 2007, changed the average. LogLog used a geometric mean of the per-bucket estimates. HLL uses a harmonic mean, which damps the outliers that dominate the others: one bucket with an unusually high register pulls a harmonic mean up far less than it pulls up an arithmetic or geometric one. The result is a relative standard error of about 1.04 divided by the square root of m, against roughly 1.30 for LogLog with the same memory.

The estimator and its corrections

With m = 2^p registers R[0] to R[m-1], the raw estimate is E = alpha_m * m^2 / sum(2^-R[j]). The constant alpha_m corrects a systematic multiplicative bias; the paper gives 0.673 for m = 16, 0.697 for m = 32, 0.709 for m = 64 and 0.7213 / (1 + 1.079/m) for m of 128 or more.

The raw estimate is biased when most registers are still zero. The original algorithm therefore switches to linear counting, m * ln(m / V) where V is the number of empty registers, whenever E is at most 2.5m and V is non-zero. Linear counting is very accurate when the table is sparsely filled and poor once it fills, which is why it is only a small-range fallback. The original paper also has a large-range correction for when E approaches 2^32, because it used a 32-bit hash and hash collisions start to hide distinct items. With a 64-bit hash that correction is unnecessary at any cardinality you will meet.

Google's HyperLogLog++ paper (Heule, Nunkesser and Hall, 2013) made three production changes: a 64-bit hash, an empirically measured bias-correction table used for raw estimates up to about 5m, with a per-precision threshold for the switch to linear counting, and a sparse representation for small sketches. Otmar Ertl later published estimators (2017) that remove the bias without lookup tables, including an improved raw estimator and a maximum-likelihood one. Which estimator a given library uses is a property of that library and version, so read its source or documentation rather than assuming.

Choosing precision from an error budget

Precision is the only real tuning parameter. Memory grows with m and error shrinks with the square root of m, so every extra bit of precision doubles memory and cuts error by about 29 percent. Dense register sizes below assume 6 bits per register, enough to hold ranks up to 63 with a 64-bit hash.

Treat the standard error as one sigma of a roughly normal distribution. At p = 14, about two thirds of estimates land within 0.81 percent of the truth, about 95 percent within 1.6 percent, and about 99.7 percent within 2.4 percent.

Pick precision from the smallest group you will report on and the decision it drives, not from the largest. A growth dashboard showing week-over-week changes of 3 percent needs error well below 3 percent, so p = 12 is marginal and p = 14 is comfortable. A fraud signal that only cares about tenfold jumps can live with p = 10.

A reference implementation

A reference implementation fits on a screen. It is slow in pure Python, but it is the version to test faster code against, and it makes each rule above concrete.

import hashlib, math

def hash64(item: bytes) -> int:
    # Any well-mixed 64-bit hash works; it must be identical on every writer.
    return int.from_bytes(hashlib.blake2b(item, digest_size=8).digest(), "big")

class HLL:
    def __init__(self, p=14):
        if not 4 <= p <= 18:
            raise ValueError("precision out of range")
        self.p, self.m = p, 1 << p
        self.reg = bytearray(self.m)          # one byte per register for clarity

    def add(self, item: bytes) -> None:
        x = hash64(item)
        idx = x >> (64 - self.p)              # top p bits pick the register
        w = x & ((1 << (64 - self.p)) - 1)    # remaining 64 - p bits
        rank = (64 - self.p) - w.bit_length() + 1   # leading zeros + 1
        if rank > self.reg[idx]:
            self.reg[idx] = rank

    def alpha(self) -> float:
        return {16: 0.673, 32: 0.697, 64: 0.709}.get(self.m, 0.7213 / (1 + 1.079 / self.m))

    def estimate(self) -> float:
        z = sum(2.0 ** -r for r in self.reg)
        e = self.alpha() * self.m * self.m / z
        empty = self.reg.count(0)
        if e <= 2.5 * self.m and empty:
            return self.m * math.log(self.m / empty)   # linear counting
        return e

    def merge(self, other: "HLL") -> None:
        if other.p != self.p:
            raise ValueError("precision mismatch: fold the larger sketch down first")
        self.reg = bytearray(max(a, b) for a, b in zip(self.reg, other.reg))

Three details matter. The rank is computed over the 64 - p bits left after the index, so the index bits never leak into the rank. A remainder of all zeros gets the maximum rank 64 - p + 1 rather than crashing. Merge refuses to combine different precisions, because a register-wise maximum over different index spaces is meaningless.

Validating an implementation

Unit tests that check add-then-count on ten items prove almost nothing, because a broken estimator can still return 10 for 10. Test the distribution of errors across cardinalities instead. The harness below inserts distinct synthetic keys, repeats with different key ranges, and compares the observed bias and spread to theory.

import math, statistics

def trial(n, p, seed):
    h = HLL(p)
    base = seed * 10**9
    for i in range(n):
        h.add(str(base + i).encode())
    return (h.estimate() - n) / n

def validate(p=10, sizes=(100, 1000, 2500, 4000, 20000, 100000), trials=50):
    expected = 1.04 / math.sqrt(1 << p)
    for n in sizes:
        errs = [trial(n, p, s) for s in range(trials)]
        print(f"n={n:>7}  bias={statistics.mean(errs):+.4f}  "
              f"sd={statistics.pstdev(errs):.4f}  theory_sd={expected:.4f}")

Use a small precision such as p = 10 so the whole range runs in minutes, and read the output against three expectations. Well above 5m, the spread should sit close to 1.04/sqrt(m) and the bias near zero. Far below 2.5m, linear counting should be much better than theory. Between roughly 2.5m and 5m, the simple estimator above usually shows a positive bias, the gap HLL++ and Ertl's estimators close. If your production library shows that bump, it is not applying the correction you thought it was. If the spread is far above theory everywhere, suspect the hash: a weak or identity hash on integer keys is the classic cause.

Worked example: daily, monthly and overlapping uniques

A mobile app has about 2 million daily active devices. The product team wants daily uniques, a rolling 30-day unique count, and the number of devices active on both the first and last day of the month.

Each day's batch job builds one p = 14 sketch per day and stores it: 12 KB dense, against roughly 16 MB just for 2 million raw 8-byte IDs, before any hash-set overhead. The 30-day figure is a merge of 30 daily sketches: 30 times 16,384 byte comparisons, which takes microseconds in compiled code. Merging loses nothing: the merged registers are exactly what one sketch fed all 30 days would contain, so the 30-day estimate of, say, 6.1 million also carries 0.81 percent standard error, about plus or minus 99,000 at two sigma.

The overlap question is where sketches bite. HyperLogLog cannot intersect, so people reach for inclusion-exclusion: |A and B| = |A| + |B| - |A or B|. Suppose each day has 2.0 million devices, the union is 3.8 million, so the true overlap is 200,000. The three estimates carry standard errors of about 16,200, 16,200 and 30,800. Treating them as independent, which is rough but indicative, the error of the difference is the square root of the sum of squares, about 38,000: a 19 percent standard error on a number whose inputs were each accurate to under 1 percent. The smaller the overlap relative to the union, the worse this gets. If overlap is a product requirement, store a sketch built for set operations, such as a theta or KMV sketch, or compute that one metric exactly.

Stored sketches in distributed queries

In warehouses and stream processors, HyperLogLog works as partial aggregation: each worker builds sketches for its slice, ships kilobytes instead of IDs, and a final stage merges and estimates. The bigger win is storing the sketches. Keep a table of (day, dimension values, sketch) and any coarser rollup, any date range and any union of segments becomes a merge, with no rescan of raw events. Systems expose this directly: BigQuery has HLL_COUNT.INIT, HLL_COUNT.MERGE_PARTIAL and HLL_COUNT.EXTRACT; Trino has approx_set, merge and cardinality; Redis has PFADD, PFMERGE and PFCOUNT.

Four rules keep stored sketches sound. First, sketches are only mergeable with sketches built by the same hash, seed, canonicalisation and precision. A BigQuery sketch, a Redis string and a Druid column are not interchangeable, so record the producer and parameters next to every stored sketch. Second, fix precision at the highest you will ever need, because you can fold a sketch down to fewer registers but never recover precision. Third, sliding windows come from merging fixed buckets, such as one sketch per hour merged over the trailing 24, because a sketch cannot forget. Fourth, deletes are impossible: a GDPR erasure request cannot be applied to a sketch, so keep raw data long enough to rebuild affected sketches, or document why rebuilding is unnecessary.

Failure modes

• Inconsistent canonicalisation. One service hashes User@Example.com and another hashes user@example.com; the merged sketch counts one person twice. Normalise case, whitespace, encoding and type (the integer 42 against the string "42") before hashing.
• Weak hash. Language runtime hashes are often not uniform and may be the identity on small integers, which piles items into a few registers. Use a mixing hash such as xxHash, MurmurHash3 or a truncated cryptographic hash.
• Precision mismatch. Merging sketches of different p without folding fails loudly at best and silently corrupts at worst. Store p with the sketch.
• Inclusion-exclusion presented as fact. A dashboard shows a small intersection to three significant figures. Show the error band or do not show the number.
• Estimator regime confusion. An implementation without bias correction produces a visible kink near 2.5m; on a chart it looks like a real step in traffic.
• Idempotence hides duplicates. Merging the same partition's sketch twice changes nothing, so a pipeline that double-processes data shows correct uniques while additive metrics beside it, such as event totals, silently double. Reconcile both kinds of metric.

Trade-offs

Choose an exact count when the number is small, legally significant or billed. Choose HyperLogLog when groups are many, cardinalities are large, and you need unions across time or dimensions: it is the most memory-efficient mergeable distinct counter in common use. Choose theta or KMV sketches when you need intersections and differences with known error, at a larger size for the same accuracy. Use a Bloom filter when the question is membership, not count, and a Count-Min sketch when you need per-key frequencies rather than the number of keys.

What to do next

1. List every place you compute distinct counts and record which hash, precision and estimator each uses.
2. Pick precision from the smallest group and the decision it drives; write the 95 percent band beside it.
3. Run the validation harness against each library you depend on, including sketches you deserialize.
4. Store daily or hourly sketches with producer, hash and precision metadata, and serve rollups by merging.
5. Remove any inclusion-exclusion intersections from dashboards, or label them with their computed error.
6. Write down how erasure requests and late-arriving data rebuild the affected sketches.