Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was published in 2010, yet I've seen the traditional analysis of Bloom filters continued to be taught in various algorithms and data structures courses.

Is the traditional analysis of Bloom filters indeed incorrect?

Thanks!

share|improve this question

2 Answers 2

up vote 35 down vote accepted

The traditional analysis is fine. The "traditional" analysis is, if it is explained correctly, an approximation; it's based on calculating the expected number of cells that are 0/1 when you hash the keys into the filter, and then analyzing as though that was the actual number. The point is that the number of cells that are 0 (or 1) are tightly concentrated around their expectation, so it's a fine approximation. This was well known, and can be found, I think, even back in my survey article with Andrei Broder.

This paper says that really the performance of a Bloom filter is a random variable (corresponding to the actual fraction of 0/1 entries), and if you want to calculate that performance exactly for some reason, you need to do the combinatorics. For smaller filters, you'll see an arguably non-trivial difference.

I've talked with the authors of this paper. Their analysis is all well and good (though I'd argue that it isn't deep or new); their motivation that the "traditional analysis is wrong" was, I think, exaggerated.

share|improve this answer
14  
Order has now been restored to the universe :). And welcome to cstheory, Michael. –  Suresh Venkat Apr 10 at 21:26

Let me add to Michael's answer that for split Bloom filters, where the hash functions have disjoint ranges, the traditional analysis is indeed correct without approximation or any concentration bounds. This is because the error probabilities for different hash functions become independent rather than correlated. The space/error trade-off for split Bloom filters is essentially the same as for traditional Bloom filters, so I think this is a good variant for teaching.

share|improve this answer
2  
That seems like the same idea as the count-min sketch, except with Bloom filters. –  templatetypedef Apr 11 at 17:19
    
Thanks Rasmus -- great point! –  Michael Mitzenmacher Apr 11 at 23:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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