Thank you for the write up here. I was going to post something similar, but instead use the example of a lawyer wanting to perform name searches on the list of

Thank you for the write up here. I was going to post something similar, but instead use the example of a lawyer wanting to perform name searches on the list of people the NSA has information on. One point I do want to make, though, for anyone that can't tell the last paragraph might be a bit of a joke: while a Bloom filter never has false negatives, it will always have a certain amount (controllable by adjusting the size of the filter) of false POSITIVES. Think of it this way: a Bloom filter lets you determine with 100% accuracy if someone is a member of Group A (the set you build the filter with) but less than 100% accuracy if they're instead only a member of Group Not-A. In the example above, if Group A is the Evil Terrorists (which you build the Bloom filter with), then there's a non-zero chance that a Good American member of Group Not-A may end up falsely identified as a terrorist. If Group A is instead made up of every Good American, you flip the problem and now have the non-zero possibility of falsely identifying a Evil Terrorist (from group Not-A) as a benign Good American. If you attempt to use them to solve a problem like this, you have to have a mechanism in place to deal with the very real case of a false positive (or decide which group to build the filter with - which one is less damaging to have show up as a false positive). Bloom filters are cool, but they're a tradeoff of speed and memory for accuracy. They are not a perfect index if you're trying to determine A vs. Not-A-ness. The best concept is a cache lookup - if it's not a member of the Bloom filter, you DEINITELY don't have it cached, but if there's a hit then you very very very likely have it cached (and if you don't, then at least you're only redirecting a vanishingly small number of false positives back to the live server). Google actually uses this for determining attack sites in Chrome without giving out an index of all the attack sites they know of. They give out a Bloom filter instead with the web client. When you visit a site, if it's a miss on the Bloom filter, it is currently not known by Google to be an attack site. However, if you get a hit, it first calls home to a Google server to re-verify that the site is not a false positive and confirm it is indeed an attack site. In this way, since the vast majority of the web is not malicious, they only impose a bandwidth cost when they think you may have stumbled upon a bad site (member of the Bloom filter) - but they get a chance to weed out the false positives before telling you.