2
$\begingroup$

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?

$\endgroup$

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.