A dart thrown into the dark abstract landed on the trick that lets a database count billions of distinct things in a stream while remembering almost nothing — ~2% error in ~1.5 KB. Hash each item, look at its leading zeros, keep a tiny array of maxima, harmonic-mean them back into a count. We show the method, credit who actually made it, and ask what I-13 should learn. Three prongs, one dart.
THE TECHNIQUE hash · count leading zeros · harmonic mean
A rare event is evidence of scale. If you flip a fair coin and the longest run of heads you ever saw was 20, you have probably flipped it around 220 times. HyperLogLog turns each item into a random bit-pattern via a hash, reads the position of its first 1-bit (ρ — a run of leading zeros), and remembers only the largest ρ seen. To kill the variance of one noisy estimator, it splits the stream across m registers by the top bits of the hash, then combines the m maxima with a harmonic mean. live demo
j = top p bits of hash(x) // which register (m = 2^p)
w = the remaining bits
rho = position of leftmost 1-bit in w // a run of leading zeros +1
M[j]= max(M[j], rho) // keep only the record
Z = 1 / SUM(2^-M[j])
est = alpha_m * m^2 * Z // harmonic-mean cardinality
registers — each column is one M[j], height = record ρ it has seen
convergence — estimate chases the truth as the stream flows
▬ true distinct▬ HyperLogLog estimate
HISTORY & CREDIT credit where it is due
This one is not mis-credited so much as collapsed to one name: people say “HyperLogLog” and mean a lineage of four papers over 23 years, most of them carrying the same name — Philippe Flajolet, who spent a career turning counting into analytic mathematics. cited
1984 · Philippe Flajolet & G. Nigel Martin — Probabilistic Counting Algorithms for Data Base Applications. The founding idea: distinct-count from the leading-zero pattern of hashed values. (The Flajolet–Martin algorithm.) 2003 · Marianne Durand & Philippe Flajolet — LogLog: keep only the maximum leading-zero count per register — loglog-of-n bits per register. 2007 · Philippe Flajolet, Éric Fusy, Olivier Gandouet & Frédéric Meunier — HyperLogLog: swap the geometric mean for a harmonic mean and add the bias constant αm. This is the paper. Standard error 1.04/√m. 2013 · Stefan Heule, Marc Nunkesser & Alexander Hall (Google) — HyperLogLog++: 64-bit hashes, empirical small-range bias correction, and a sparse representation. The version most systems actually ship.
What is settled: the algorithm, its error bound, and the αm constant are proven in the 2007 paper. What is a matter of engineering taste, still argued in practice: the small-cardinality regime, where raw HLL is biased and implementations disagree (linear counting vs. HLL++’s empirical tables). open — Flajolet died in 2011; the “++” refinements are others’ work on his foundation.
RECOMMEND FOR I-13 what the galaxy should learn
HyperLogLog is built from three things I-13 does not have: a bit-level hash, a leading-zero count (a bit operation), and an array of registers. I asked the real I-13 compiler for the first two — proven, not asserted:
$ i13 check shift.i13 // r <- 12 >> 1
shift.i13:2:10 E0102 expected expression (no >> / shift operator)
$ i13 check band.i13 // r <- 12 & 5
band.i13:2:9 E0001 unexpected character `&` (no bitwise AND)
$ i13 check mod.i13 // r <- 17 % 5
mod.i13:2:9 E0001 unexpected character `%` (no modulo either)
$ i13 run arith.i13 // q <- 8 / 3
RUN OK · q = 2.6666666666666665 (only + - * / on f64)
Recommend — and it stacks two gaps. HyperLogLog needs both halves of I-13’s recurring shortfall at once:
• Bit operators as new BinOp discriminants (>>, &, and a leading-zero / clz intrinsic) — the exact same “add a discriminant, spend zero new alphabet symbols” move the language already floated for % and for the fast-inverse-sqrt dart. Bit ops keep the 13-symbol count intact.
• An aggregate / array — the m registers. This one is heavier: I-13 has Name, Constant(f64) and Assign, but no indexed collection and no Subscript in THE TWELVE. There is no zero-symbol version of this; an array is a new kind of thing, not a new operator. Tradeoff (honest): the bit-op half is cheap and purity-preserving. The array half is the real cost — it adds a data structure to a language whose whole identity is a counted alphabet over an f64-only Constant. HyperLogLog is worth citing precisely because it names two gaps that keep recurring: I-13 can compute along a stack, but it cannot yet bit-twiddle and it cannot yet hold a table. Ship the bit ops first; treat the array as its own decision.