3
$\begingroup$

I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements inserted.

For a Bloom Filter, I created ${k}$ Hash functions, and set the value in the filter for each Hash Index returned. Here's a graph of the results I obtained from my tests:

enter image description here

The problem from the graph is clear, I am getting False Positive rates that are better than the Theoretical value. The theoretical value is based on the assumption that each Hash Index is equally likely, which is:

$ Pr(H(a) = 1)^k = 1 - Pr(H(a) = 0)\\ = (1 - (1 - 1/n)^{km})^{k}\\ = (1 - e^{-k/c})^{k} $

Using $k = c \ln(2)$

$ Pr(H(a) = 1)^{k} = (1 - e^{-\ln(2)})^{k}\\ = (1/2)^{c \ln(2)}\\ = 0.6185^{c} $

All my tests are based on the optimal value of $k = c \ln(2)$, and the theoretical line is a plot of $0.6185^{c}$. My concern is that my False Positive rates are consistently better than the theoretical. Does this mean that my implementation is incorrect, or is it a likely possibility given the large sizes of the Bloom Filters and the efficiency of the hashing algorithm?

I appreciate any guidance on this.

$\endgroup$
0
$\begingroup$

The approximation of probability you are calculating is used to give estimated optimal number of hash function used (which is then rounded, $c*ln(2)$ does not look like integer).

There are many factors that should be considered: the choice of hash functions, data set provided for tests, approximation skew, rounding of approximation and fact that given theoretical bound is asymptotic value, so works better for bigger n and m.

I would like to propose paper false-positive rate of Bloom filters, showing how given approximation is incorrect.
Another good resource Thomas Gerbet, Amrit Kumar, C´edric Lauradoux. The Power of Evil Choices in Bloom Filters. (Research Report) RR-8627, INRIA Grenoble. 2014 shows how saturation of filter changes with given data.

$\endgroup$
  • $\begingroup$ Are you sure that independent hash bits is a worst-case bound? Won't independent data produce fewer false positives than dependent data, but more false positives than negatively dependent data? $\endgroup$ – jbapple Mar 29 '16 at 15:18
  • $\begingroup$ @jbapple I revoke it, both versions were flawed (with heavy unclearity on top), and the problem is in different place, so I just rewrote the answer. $\endgroup$ – Evil Mar 30 '16 at 4:32
2
$\begingroup$

Your question includes the equation

$$ (1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k} $$

But that is not actually an equation; it is only an approximation.

$\endgroup$

Your Answer

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

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