<p>Michael Mitzenmacher has a <a href="http://www.cs.utexas.edu/~yzhang/teaching/cs386m-f9/Readings/im2005b.pdf">nice survey on Bloom filters</a> where he outlines many applications. Maybe some of these might help. </p>

CC BY-SA 3.0
2011-12-05T05:27:14.327Z
2011-12-05T05:27:14.327Z
Suresh Venkat
<p>Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter?  In other words, the damage done by the Bloom filter's false positive rate requires an interesting trick to accommodate. </p>

CC BY-SA 3.0
2011-12-05T02:16:43.327Z
What counts as nontrivial ? One classic example is proxy caches, where you just have to fetch the URL explicitly if you get fooled by the bloom filter
Suresh Venkat
CC BY-SA 3.0
2011-12-05T02:59:11.197Z
Bloom filters are "obviously a perfect fit" for GoogleFS, proxy caches, etc.  I'm merely curious about less natural applications, like some graph algorithm that needs a big set.  There must be some such algorithms in networking problems I suppose, i.e. you publish some Bloom filter for all nodes to use.
Jeff Burdges
CC BY-SA 3.0
2011-12-05T03:58:53.613Z
Have you seen Michael Mitzenmacher's survey ? (moving to an answer)
Suresh Venkat
CC BY-SA 3.0
2011-12-05T04:43:53.243Z
No, but that's great! thank you!
Jeff Burdges
<ds.data-structures>
Non-trivial applications of Bloom filters
Jeff Burdges
# Non-trivial applications of Bloom filters

(Asked by: username_0 on 2011-12-04)

Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter? In other words, the damage done by the Bloom filter's false positive rate requires an interesting trick to accommodate.

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: What counts as nontrivial ? One classic example is proxy caches, where you just have to fetch the URL explicitly if you get fooled by the bloom filter  
> **username_0**: Bloom filters are "obviously a perfect fit" for GoogleFS, proxy caches, etc.  I'm merely curious about less natural applications, like some graph algorithm that needs a big set.  There must be some such algorithms in networking problems I suppose, i.e. you publish some Bloom filter for all nodes to use.  
> **username_1**: Have you seen Michael Mitzenmacher's survey ? (moving to an answer)  
> **username_0**: No, but that's great! thank you!  

---

## 1 answers

### Answer by username_1 on 2011-12-05. Score: 9 | Accepted answer

Michael Mitzenmacher has a [nice survey on Bloom filters](http://www.cs.utexas.edu/~yzhang/teaching/cs386m-f9/Readings/im2005b.pdf) where he outlines many applications. Maybe some of these might help.


---

