1
$\begingroup$

Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives .

How it works : Assume there are 10000 bits , 3 hash functions and an object Foo is to be inserted into the Bloom Filter .

Insertions : Foo will be hashed by the 1st hash function and the 3405 bit index is set to 1 , Foo is hashed by the second hash function and the 1001 bit index is set to 1 , Foo is hashed by the third hash function and the 5555 bit index is set to 1 .

Check exist : Foo will be hashed to the three different hash function and if all the bits at the respective index is set to 1 , the object is said to exist with a small chance of false positive else the object cant be found .

My question is : Why do we use more than 1 (in this case 3 bits ) to determine if a objects exist in the Bloom Filter , doesnt it increase the chances of collision with other objects which may also set the same bit to 1 . To me , it seems best to use a single hash function as it saves the most space (1 bit only) and least chances of collision with other objects in the Bloom Filter

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ the probability that 2 objects will hash to the same bit is less than the probability that they will hash to 3 or more bits, right? Hence, the more bits (hash functions) you use, the lower the probability of a false positive. $\endgroup$
    – EggHead
    Mar 14, 2014 at 14:23
  • 1
    $\begingroup$ The number of bits you should choose for each element is based both on the size of the table and the number of insertions you plan to do. See my answer here: cs.stackexchange.com/questions/12834/why-do-bloom-filters-work/… (which in turn links to the Wikipedia page on Bloom filters which describes how to minimize false positives.) $\endgroup$
    – Wandering Logic
    Mar 14, 2014 at 18:29

1 Answer 1

Reset to default
1
$\begingroup$

Consider Bloom filters in which $k$ hash functions are used. If we look up a value which is in the filter, then we always conclude that it is indeed in the filter. Things are more complicated when we look up a value which is not in the table; we could erroneously conclude that it were in the table.

Suppose the filter is of size $n$, and $m$ values were put into the table. So roughly $km$ positions are set to $1$. If we look up a value which was not put in the filter, then assuming that the hash locations corresponding to it are random, the probability that we erroneously conclude that it is in the filter is $$ \left(\frac{km}{n}\right)^k. $$ The correct value of $k$ thus depends on the expected $m/n$. Suppose that $m = n/10$. Then we have the following error probabilities: $$ \begin{array}{c|l} k & \text{error probability} \\\hline 1 & 0.1 \\ 2 & 0.04 \\ 3 & 0.027 \\ 4 & 0.0256 \\ 5 & 0.03125 \end{array} $$ So in this setting the error probability is minimized for $k = 4$. Since $k$ also effects the running time, we might as well choose $k = 3$ for these parameters, for which the error probability is almost as good.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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