Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is the correct tradeoff between space ($m$) and false positive rate ($\epsilon$) for $k = 1,2,3$? To get a false positive rate of $1\%$, what size array do you need for $k = 1,2,3$?

I'm not sure how to answer the first question (tradeoff between space/false positive rate). For the second question, I'm confused because even if I solve the equation $m = n\log (\frac{1}{\epsilon})\ln 2$ for $\epsilon$, it still doesn't take into consider what $k$ is. For a certain $k$, how do you calculate the false positive probability?


Your Answer

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

Browse other questions tagged or ask your own question.