2.11 HyperLogLog

Counting unique visitors exactly means remembering every visitor already seen, so that nobody is counted twice. With a set, 100 million visitors cost several gigabytes. With HyperLogLog, the same question costs at most about 12 KB, whether you have seen a thousand visitors or a billion, and the answer is typically within 0.81 percent of the true count.

You give up exactness and the ability to list or check members. In return, memory stops growing with the data. This lesson follows one example: a site that counts unique visitors to its home page each day, with one key per day such as