HyperLogLog, Theta and KMV

Why can HyperLogLog not intersect?

HyperLogLog

HyperLogLog (HLL) estimates the number of distinct items in a stream.

The derivation is short, and it explains the "log log". Hash each item to a uniform random bit string. The probability that a hash starts with ρ leading zeros is 2^(−ρ). (Like flipping a coin: the chance of ρ heads in a row at the start is 2^(−ρ).) So if the longest run of leading zeros seen across n distinct items is ρ_max, then n ≈ 2^(ρ_max). One register, one estimate. But the variance is terrible: a single lucky hash swings the answer by a factor of two.

The fix is the standard variance-reduction move. Use the first log₂m bits of the hash as a bucket index, keep a maximum per bucket (in a register), and average across buckets. Use the harmonic mean of 2^ρ (it suppresses the influence of one large outlier; the arithmetic mean does not) and correct the remaining bias with a constant α_m. The standard error is

RelationshipError falls as one over the square root →

1.04/ m

m (registers): $m$ — independent observations: registers, retained hashes, ring positions
1.04: $c$ — set by the estimator (1.04 for HyperLogLog, about 1 for k minimum values and for virtual nodes)

Stated in 6 places →Trade-off: Exactness vs. approximation →

The headline number. m = 16,384 registers at 6 bits each is about 12 KB, and gives 1.04 / 128 ≈ 0.81% error on cardinalities up to billions. Exact distinct counting of 10⁹ keys takes gigabytes. The compression ratio is around 10⁶, the most dramatic space-accuracy trade in the field. This is the Approximation law at work: the error 1.04/√m needs 4 times the registers to halve.

Union is exact. Intersection is a trap. Merging two HLLs is element-wise maximum. The maximum of the maxima is the maximum of the union, so a merged HLL is identical to the HLL you would have built from the combined stream. It is not an approximation of it.

Intersection has no such operation. You must use inclusion-exclusion:

|A ∩ B| = |A| + |B| − |A ∪ B|

and the absolute errors of three large numbers add up, while the answer you want may be small. Worked example: two sets of 10⁹ each, with a 1% overlap (10⁷ shared). Each estimate has about 0.8% error, which is ±8 × 10⁶ on each large number. The errors on three numbers add to something like ±2 × 10⁷, which is bigger than the 10⁷ quantity being estimated. This is the most common way HLL fails in production, because audience overlap, funnel analysis and cohort retention are all intersections, and they are exactly what analytics teams use HLL to answer.

Production HLL is not paper HLL. Raw HLL is badly biased at low cardinality. HLL++ uses a sparse representation plus linear counting (an estimate from the fraction of empty buckets) below a threshold, and an empirical bias correction above it. When you compare implementations, that difference dominates.

Theta sketch and KMV

KMV ("k minimum values") and the Theta sketch estimate distinct counts in a different way.

The mechanism. Hash each item to a number in [0, 1). Keep only the k smallest hash values seen. If the k-th smallest is θ, then the k retained values fill a θ-fraction of the hash space, so the estimate is n̂ = (k − 1) / θ. The standard error is about 1/√k.

Per bit of memory, it loses to HLL. It stores k 64-bit values where HLL stores m 6-bit registers for comparable error. So space is not why it exists.

It exists because it is closed under set operations, and HLL is not. Every sketch built with the same hash function retains "all items whose hash is below θ". So the retained sets are coordinated samples of their inputs. Lower two sketches to the smaller θ, and the intersection of the retained sets is a valid sample of the intersection of the original sets. Union, intersection and difference all work with unbiased estimates and bounded error, computed on the sketches alone. This is a compositional-algebra property, not an accuracy property. It is why Apache DataSketches and Druid use Theta for anything involving overlap.

The compression worth taking away. KMV, Theta and bottom-k MinHash are the same structure: keep the k smallest hashes. They serve three different questions:

cardinality comes from the threshold θ;
set operations come from the coordination;
similarity comes from the overlap of the retained sets.

Same mechanism, three uses. When one structure answers three questions, the structure is more fundamental than any of them.