<p>Let me add to Michael's answer that for <strong>split</strong> 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.</p>

CC BY-SA 3.0
2014-04-11T17:19:34.973Z
That seems like the same idea as the count-min sketch, except with Bloom filters.
templatetypedef
CC BY-SA 3.0
2014-04-11T12:59:38.083Z
2014-04-11T12:59:38.083Z
Rasmus Pagh
<p>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.</p>

<p>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.  </p>

<p>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.  </p>

CC BY-SA 3.0
2014-04-10T21:26:49.217Z
Order has now been restored to the universe :). And welcome to cstheory, Michael.
Suresh Venkat
CC BY-SA 3.0
2014-04-10T21:15:43.687Z
2014-04-10T21:15:43.687Z
Michael Mitzenmacher
<p><a href="http://www.csee.usf.edu/~christen/energy/ipl10.pdf">This paper</a> 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.</p>

<p>Is the traditional analysis of Bloom filters indeed incorrect?</p>

<p>Thanks!</p>

<ds.data-structures>
Is the traditional analysis of Bloom filters wrong?
templatetypedef
# Is the traditional analysis of Bloom filters wrong?

(Asked by: username_0 on 2014-04-10)

[This paper](http://www.csee.usf.edu/~christen/energy/ipl10.pdf) 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!

**Tags:** ds.data-structures


---

## 2 answers

### Answer by username_2 on 2014-04-10. Score: 37 | Accepted answer

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.

> **Comments:**
> **username_3**: Order has now been restored to the universe :). And welcome to cstheory, Michael.  

---

### Answer by username_1 on 2014-04-11. Score: 12

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.

> **Comments:**
> **username_0**: That seems like the same idea as the count-min sketch, except with Bloom filters.  

---

