A page has been visited all day. Redis has a key called visitors:home:today. Each visit runs PFADD with the visitor's ID, and PFCOUNT gives an approximate number of different visitors. Redis's documented dense counter uses 12,288 bytes of register data, whether the day has a few thousand visitors or millions. How can a counter answer without keeping their IDs?
The PF at the front of those commands is there in honour of Philippe Flajolet, the paper's first author. The answer is to remember a property of each ID's hash, not the ID itself. A rare bit pattern suggests how many different hashes have passed by. HyperLogLog repeats that small experiment across many registers and combines their guesses carefully.
This paper is hosted by its original publisher.
Read on dmtcs.episciences.orgThe Problem in 2007
Flajolet, Fusy, Gandouet, and Meunier wrote for the 2007 Conference on Analysis of Algorithms. Their example is network traffic: a packet header has a source and destination address, and the number of different address pairs in a time slice helps reveal active flows. The same pair may appear many times. Cardinality means the number of distinct pairs, not the number of packets.
An exact set must remember each different item, so its memory grows with the answer. Their target is a massive stream read once, where a small, known estimation error is acceptable. They analyze a counter that updates one tiny part of its state per item and needs no stored IDs.
