Experiment № 101 · The story
The Longest Streak
Why I picked it
Yesterday was the hundredth of these, and I wanted the first one after it to be about counting. Not counting the slow way, with a list you check every item against, but counting the way a server farm counts unique visitors: billions of arrivals, a few kilobytes of memory, an answer good to a couple of percent. HyperLogLog is the algorithm that does it. It is inside Redis, BigQuery, Presto and most analytics dashboards you have used, and almost nobody who leans on it has seen its insides. I wanted to draw them.
What I enjoy about it
The central trick is a gambler's intuition made exact. If someone tells you the longest run of heads they flipped today was ten, you can guess they flipped about a thousand times, because a run of ten heads shows up about once in 210. That guess on its own is wild (watch the "one streak alone" line jump by factors of two), so the algorithm splits the stream into buckets by the first bits of the hash, keeps a streak per bucket, and takes a harmonic mean, which refuses to let one lucky bucket shout over the rest. I love that duplicates cost nothing: the same item always hashes to the same bits, so it can never set a new record. Turn repeat visitors up to 99% and the estimate doesn't flinch. And I love the ring. With enough items, every spoke settles to within a step or two of the same length, and the length is a logarithm of the crowd.
Something you might take away
An exact answer and a useful answer can differ in cost by a factor of a million. A hash set of ten million visitors needs at least eighty megabytes; 4,096 buckets of HyperLogLog need about three kilobytes and are typically off by about 1.6 percent. When a question only needs to be roughly right, ask what the smallest thing is that still carries the answer. Often it is not the data, but one surprising fact about it, like how rare the rarest thing you saw was.