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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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 $\endgroup$– Suresh VenkatDec 5, 2011 at 2:16
-
$\begingroup$ 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. $\endgroup$– Jeff BurdgesDec 5, 2011 at 2:59
-
$\begingroup$ Have you seen Michael Mitzenmacher's survey ? (moving to an answer) $\endgroup$– Suresh VenkatDec 5, 2011 at 3:58
-
$\begingroup$ No, but that's great! thank you! $\endgroup$– Jeff BurdgesDec 5, 2011 at 4:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Michael Mitzenmacher has a nice survey on Bloom filters where he outlines many applications. Maybe some of these might help.
answered Dec 5, 2011 at 5:27