Blog

Probabilistic Data Structures: Bloom Filter, Count-Min Sketch and HyperLogLog

Probabilistic data structures cut memory by orders of magnitude in exchange for a small, controlled error: a Bloom filter says "definitely not / probably yes", Count-Min Sketch estimates frequencies by over-counting, HyperLogLog counts uniques with constant memory. We write all three in C# and measure a 1.01 percent false positive rate with 1.14 MB for a million e-mails, and unique visitors within 0.8 percent using 16 KB.