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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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