How many different people visited your website today? It sounds easy. Keep a list of visitor IDs, and count the entries. But for a site with a billion visitors, that list takes gigabytes, and you may need that number for every page, every hour, every country. Exact counting does not scale.
HyperLogLog, described by Philippe Flajolet and colleagues in 2007, estimates the number of distinct items in a huge stream using a few kilobytes. The paper's headline: it can estimate cardinalities well beyond a billion with a typical accuracy of 2 percent using only 1.5 kilobytes of memory.
Hash every item. Track the longest run of leading zeros you have seen, since rare patterns mean many items. Use many small registers to smooth out luck, then combine them. Memory stays tiny, and the error shrinks as 1 over the square root of the number of registers.
The coin-flip insight
Imagine each item turned into a random string of bits by a good hash function. Half of all strings start with a 1. A quarter start with 01. One in eight starts with 001, and so on. A string with k leading zeros appears about 1 time in 2k.
So if you scan a stream and the best you ever see is 3 leading zeros, the stream was probably short, a few dozen items at most. If you see 20 leading zeros, you have probably seen about a million different items. You only have to remember one small number: the maximum.
Duplicates cause no trouble. The same item hashes to the same string, so seeing it again cannot increase the maximum. That is why this counts distinct items.
