2
$\begingroup$

If the false positive error rate is greater than 0.5 then a Bloom filter is no different from coin flip, right?

Still, if one does implement this data structure with, say, P=0.55 then it would still work.

Should the constructor method of a Bloom filter implementation forbid values of P greater than 0.5?

$\endgroup$

2 Answers 2

5
$\begingroup$

A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential performance issue, but not a correctness issue.

One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify this a bit, to see what I mean.

Suppose that you are trying to represent some subset of a universe of $S \subseteq U$. We'll further assume that you are testing elements of $U$ for membership in $S$ with equal probability.

  • Let $p$ be the proportion of elements that are in the set (i.e. $p = \frac{|S|}{|U|}$).

  • Let $c_p$ be the cost of a precise test (measured in time, cycles, disk accesses, or whatever seems appropriate).

  • Let $c_b$ be the cost of a Bloom filter test, and we hope that $c_b < c_p$.

  • Let $q$ be the false positive rate of the Bloom filter.

If we only performed precise tests, the cost of each test is $c_p$.

If we perform a Bloom filter test first, the cost of each test is $c_b$ plus $c_p$ times probability that we need to perform a precise test, whether due to true positives or false positives.

By the inclusion-exclusion principle, the average cost of this test is:

$$c_b + c_p(p + q - pq)$$

As long as $c_p > c_b + c_p(p + q - pq)$, the Bloom filter test gives you a net performance gain.

As you can see, the false positive rate $q$ is not the only important number here; Bloom filters with higher $q$ may, for example, have smaller $c_b$ because physically smaller data structures are more cache-friendly.

For completeness, I will note that having a backup precise test isn't the only use case for Bloom filters. There are other situations where false positives are tolerable.

Consider a network protocol where two systems on different machines need to be kept in sync. You would like to only transmit the changes, to save bandwidth. But occasionally transmitting some data that you don't need to transmit is not as bad as failing to transmit data that needs to be transmitted. It may be wasteful to over-transmit, but it's not incorrect to do so.

$\endgroup$
1
$\begingroup$

In the same way that 0.5 is the error of a coin flip, 0.166666 is the error of a die throw. There's nothing sacred in the probability 0.5.

A Bloom filter gives you a guarantee that a coin flip cannot – it has no false negatives. Even if its false positive rate is 0.9, it still gives you some information.

Whether or not a high false positive rate is helpful or not depends on the application. A false positive rate of 0.5 still means that you filter half of the elements outside your set.

$\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.