HyperLogLog
Count the distinct stars in a galaxy using a few hundred bytes of memory. Sweep the net through the stream; every star is hashed, and only the longest run of leading zeros is kept.
How many distinct stars have you caught so far?
The numbers
The probabilistic trio
HyperLogLog answers "how many different stars?". Two cousins answer the other questions with the same trade, a little certainty for a lot of memory: a Bloom filter for "have we seen this star before?" and a count-min sketch for "how often?". Every star the net catches feeds all three. Open the full Bloom filter page for ghost stars, the k slider and the formulas.
How it works
Every star is hashed to 32 random-looking bits. The first p bits pick one of m = 2p registers. In the remaining bits, count the zeros before the first 1: a run of k zeros turns up about once in 2k+1 stars, so a long run means many distinct stars went by.
Each register keeps only its longest run. A repeat star hashes the same way, so it can never change anything: duplicates are free. One register would be wildly noisy, so the sketch takes a harmonic mean across all of them and scales it.
Two sketches merge by taking the larger value in each register, which gives exactly the sketch of the combined stream. That is how big systems count unique visitors across many machines.
a few hundred bytes count millions of distinct things to within a few percent, and repeats cost nothing.