most recent 30 from http://mathoverflow.net 2013-06-20T05:52:33Z http://mathoverflow.net/feeds/question/84115 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84115/distribution-of-error-with-bloom-filters Gordon Worley 2011-12-22T19:40:18Z 2011-12-22T19:40:18Z

<p>Let $S_1$ and $S_2$ be sets. Given a <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">Bloom Filter</a> $BF$ for fixed $m$ and $k$, then <a href="http://www.cs.utexas.edu/~yzhang/Teaching/cs386m-f9/Readings/im2005b.pdf" rel="nofollow">it's known</a> that $\left|S_1 \cap S_2\right|$ can be estimated as</p> <p>$\frac{\left|S_1\right|k\log\left(1-\frac{1}{m}\right)+\left|S_2\right|k\log\left(1-\frac{1}{m}\right)-\log\left(\left(1-\frac{1}{m}\right)^{\left|S_1\right|k}+\left(1-\frac{1}{m}\right)^{\left|S_2\right|k}+\frac{\text{BF}\left(S_1\right)\cdot\text{BF}\left(S_2\right)}{m}-1\right)}{k\log\left(1-\frac{1}{m}\right)}$</p> <p>I'm trying to figure out how to calculate the error of this estimate. I'm having some trouble getting started since probability and statistics was never really my area of study. What do I need to figure out? How do I go about finding it?</p>