What if, by trading 1% correctness, you could count billions of items all within kilobytes worth of space? Well that's HyperLogLog, and as a non-bit-enlightened Rubyist it was a trip figuring out how it worked and how to explain it.
baweaver.com/writing/2026...
Counting distinct values exactly means remembering all of them. HyperLogLog does it in 16 kilobytes. This post builds from coin flips to bitmaps to the algorithm Redis uses behind PFCOUNT.
