filter

Bloom filters

As promised in my previous post, I spent some time today understanding Bloom filters. While the wiki page intimidated me a bit when I first looked at it, it’s actually pretty simple once you sit down and patiently read through the whole thing. Bloom filters are a lot like hash maps, except that they save a lot on the space occupied for maintaining an index of your data at the cost of a minor chance of false positives.