6
$\begingroup$

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.

$\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$ Dec 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$ Dec 5, 2011 at 2:59
  • $\begingroup$ Have you seen Michael Mitzenmacher's survey ? (moving to an answer) $\endgroup$ Dec 5, 2011 at 3:58
  • $\begingroup$ No, but that's great! thank you! $\endgroup$ Dec 5, 2011 at 4:43

1 Answer 1

9
$\begingroup$

Michael Mitzenmacher has a nice survey on Bloom filters where he outlines many applications. Maybe some of these might help.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.