Symptom

Product wants the daily unique-visitor count. You have a firehose of events.

The obvious implementation is a set. Add each visitor ID, report the size. At a billion distinct IDs, eight bytes each, that is 8 GB before any hash table overhead, and in practice a HashSet will cost you two to three times that. Per day. Per dimension you want to slice by. Multiply by country, by platform, by campaign, and the memory bill is absurd for a number nobody looks at past two significant figures.

So you try to be clever, and you fail, repeatedly, in a way that feels like it should be solvable. Then somebody tells you it is not solvable, and hands you a 12 KiB structure that answers the question to within 1%.

Both halves of that are theorems, and the pair of them is the most useful trade in applied algorithms.

Statement

The lower bound. Computing the number of distinct elements $F_0$ exactly in one pass requires $\Omega(n)$ bits of space, where $n$ is the universe size. The same holds for exact frequency queries and for exact median. Randomization and approximation separately do not help; you need both.

The upper bound. With a $(1 \pm \epsilon)$ approximation and failure probability $\delta$, distinct counting is solvable in $O(\epsilon^{-2}\log\log n + \log n)$ bits. HyperLogLog achieves a standard error of $1.04/\sqrt{m}$ using $m$ registers of about 6 bits each.

The trade, in numbers. At $m = 2^{14} = 16384$ registers, HyperLogLog uses 12 KiB and has 0.81% standard error, at any cardinality up to billions. Against 8 GB minimum for the exact set, that is a factor of roughly 700,000 in space for one significant figure of loss.

Count-Min sketch does the analogous thing for frequencies: a $d \times w$ table of counters gives $\hat{f}_x \le f_x + \epsilon N$ with probability $1 - \delta$ using $w = \lceil e/\epsilon \rceil$ and $d = \lceil \ln(1/\delta) \rceil$. At $\epsilon = \delta = 0.001$ that is $2719 \times 7 = 19{,}033$ counters — under 80 KB to track every frequency in a stream of any length to within 0.1% of its total.

Argument

The lower bound, by reduction from communication complexity. This is where the information-theoretic argument of T004 reappears in a new setting.

Alice holds $x \in {0,1}^n$, Bob holds $y \in {0,1}^n$, and they must decide whether $x = y$ (EQUALITY) or whether they share a 1 (DISJOINTNESS). The known result: deterministic EQUALITY requires $n$ bits of communication, and randomized DISJOINTNESS requires $\Omega(n)$.

Now suppose a streaming algorithm computes $F_0$ exactly in $s$ bits. Alice feeds her set as a stream, sends the algorithm’s $s$-bit state to Bob, and Bob continues with his own elements. From the final $F_0$ Bob learns $|A \cup B|$, and knowing $|A|$ and $|B|$ gives $|A \cap B|$, which decides DISJOINTNESS. So $s = \Omega(n)$.

The state of the algorithm is a message, and anything the message cannot carry, the algorithm cannot compute. Once you see streaming as one-way communication, lower bounds follow from a well-developed theory rather than from ad-hoc arguments.

Why approximation escapes. The reduction needs an exact answer to recover $|A \cap B|$. A $(1 \pm \epsilon)$ estimate does not distinguish intersection size 0 from 1 when the sets are large, so the reduction breaks and the bound does not apply. Both approximation and randomization are load-bearing.

HyperLogLog, from first principles. Hash each element to a uniform bit string. For a truly random hash, the probability that a value begins with $k$ zeros is $2^{-k}$. So among $N$ distinct values, the maximum leading-zero count is about $\log_2 N$. Track that maximum, report $2^{\max}$.

Duplicates are free: rehashing the same element gives the same bit string and cannot raise the maximum. That is why the structure counts distinct elements rather than elements, and it needs nothing but the hash’s determinism.

The single-estimator variance is terrible — each additional zero doubles the estimate. The fix is stochastic averaging: use the first $b$ bits to pick one of $m = 2^b$ registers, keep a per-register maximum, and combine with the harmonic mean, which suppresses the influence of the occasional huge register. The analysis gives standard error $1.04/\sqrt{m}$. Each register holds a count up to about 64, so 6 bits suffices, and 16384 registers is 12 KiB.

Registers hold $\log\log n$ bits, which is where the $O(\epsilon^{-2}\log\log n)$ comes from. This is provably near-optimal.

Count-Min, and why the error is one-sided. Keep $d$ rows of $w$ counters, each row with its own hash from a pairwise-independent family (T104). On update $x$, increment cell $(i, h_i(x))$ in every row. To query, report the minimum across rows.

Every counter is at least $f_x$, since $x$’s own increments are always there — the estimate can only overshoot, never undershoot. Overshoot in row $i$ is the total from other items colliding with $x$ there. By pairwise independence and linearity of expectation (T007), the expected collision mass is $N/w$. Markov’s inequality gives $\Pr[\text{overshoot} > eN/w] \le 1/e$, and $d$ independent rows all failing has probability $e^{-d}$. Set $w = e/\epsilon$ and $d = \ln(1/\delta)$ and you are done.

Both structures are mergeable: a union of HLLs is a per-register maximum, a union of Count-Mins is a cellwise sum. Distributed aggregation becomes associative and commutative, which is why every analytics system in production uses them — Redis PFCOUNT, Presto, BigQuery’s APPROX_COUNT_DISTINCT, Druid and ClickHouse.

What the constants mean at a chosen size. The $\epsilon^{-2}$ dependence is worth pricing before you pick registers. At $m = 2^{12} = 4096$, HyperLogLog costs 3 KiB with 1.62% standard error; at $m = 2^{14}$ it is 12 KiB and 0.81%; at $m = 2^{16}$ it is 48 KiB and 0.41%. Four times the memory for half the error, every time, which is the theorem’s exponent showing up directly in a capacity-planning spreadsheet. Redis chose $m = 2^{14}$ for exactly this reason: 12 KiB per counter and under 1% error is the point where both numbers stop mattering to most applications.

Forbids

Exact distinct counting in sublinear space. Not an implementation limitation. Any exact one-pass algorithm needs space proportional to the universe.

Exact heavy hitters in small space. Same reduction. You get approximate counts with bounded error or you get linear space.

Exact quantiles in one pass in sublinear space. Medians need $\Omega(n)$ exactly, which is why every latency dashboard reports approximate percentiles whether it admits it or not.

Arbitrarily small error for free. The $\epsilon^{-2}$ dependence is tight: halving the error quadruples the space. Going from 1% to 0.1% costs 100×, and that is a theorem rather than a tuning problem.

Does not forbid

It does not stop exact counting when the set is small or bounded. If you have a million users, a bitmap is 125 KB and exact. Roaring bitmaps do exact distinct counts on compressed integer sets at enormous scale and are the right choice when IDs are dense. The lower bound is about the universe, and if your universe is small it does not bite.

It does not mean sketches are always the right answer. They cannot be decremented reliably (Count-Min undercounts badly with deletions; use Count-Sketch or a counting Bloom filter), you cannot enumerate members, and you cannot compute exact set differences. Debugging “which user is missing” is impossible with an HLL, and that is a real operational cost people discover late.

It does not mean the error is uniform. HyperLogLog’s raw estimator is biased at small cardinalities, which is why the original paper adds linear counting below $2.5m$ and Google’s HLL++ replaces that with an empirical bias-correction table and a sparse representation. Naive implementations are visibly wrong under a few thousand elements, and this is the single most common HLL bug.

It does not require perfect hash functions. The analysis assumes idealized uniform hashing, but Count-Min needs only pairwise independence, and HLL works fine with a good 64-bit non-cryptographic hash such as xxHash or MurmurHash. The theory is tighter than practice needs, which is fortunate.

It does not mean multi-pass algorithms are stuck. The lower bound is for one pass. With two passes or with sorted input, exact distinct counting is easy — sort and scan. Batch systems with data on disk are not in the streaming model at all, so applying streaming bounds to a Spark job is a category error.

Boundary

  • The AMS sketch and higher moments. $F_2$ — the sum of squared frequencies, used for self-join size estimation — is estimable in $O(\epsilon^{-2}\log n)$ space by Alon, Matias and Szegedy, using 4-wise independent $\pm1$ hashes. $F_k$ for $k > 2$ genuinely needs polynomial space, which is a sharp threshold.
  • Sliding windows. Exponential histograms give $F_0$ over the last $W$ elements at $O(\epsilon^{-1}\log^2 W)$ space. Recency costs a factor, and it is the usual production requirement.
  • Quantile sketches. t-digest and KLL give approximate percentiles with strong accuracy at the tails, which is exactly what latency monitoring needs and what a naive equal-width histogram fails at.
  • Turnstile versus cash-register. Insert-only streams are much easier than streams with deletions. Knowing which model you are in determines which sketches are even applicable, and it is the first question to ask.
  • The bigger pattern. These are all the same trade the Bloom filter makes: accept a bounded, one-sided, quantified error and pay a fraction of the space. What makes it engineering rather than gambling is that the error is bounded and computable in advance, so you can decide whether 0.81% is acceptable before shipping.