4 ms·

Strange coincidence, just this morning I was reading a paper [0] from 2008 about Bloom filters. Specifically, their false positive rate is higher than what is u

Strange coincidence, just this morning I was reading a paper [0] from 2008 about Bloom filters. Specifically, their false positive rate is higher than what is usually advertised - even on Wikipedia. Edit: also as is written in the document, Cuckoo Filters and Bloom filters are not adapted to unbounded streams. Better options may include, for instance, Stable Bloom Filter[1] and block-Decaying Bloom Filter[2] [0]: http://cglab.ca/~morin/publications/ds/bloom-submitted.pdf http://cglab.ca/~morin/publications/ds/bloom-submitted.pdf [1]: http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDetExt.pdf http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDetExt.pdf [2]: https://link.springer.com/article/10.1007/s11390-008-9192-1 https://link.springer.com/article/10.1007/s11390-008-9192-1

Recursing 9y ago
> even on Wikipedia Did you edit Wikipedia / add a reference to the paper?
FreakLegion 9y ago
I've only glanced at [0] but I'm skeptical on the face of it. Everything about Bloom filters falls right out of the binomial distribution, provided you follow the assumptions for optimal number of bits and hash functions. Given those, n = 1, k = 2, m = 2 from the top of page 2 isn't even a valid configuration. Among other things, filters in which more than half the bits are set (within some tolerance) should be rejected. In this example a third of the filter's possible states are completely saturated and have to be tossed out. Otherwise you have a 100% false positive rate for that filter. I.e. if a saturated filter were acceptable, there are 3 states: 01, 10, 11. These have, respectively, a 1 in 3, 1 in 3, and 3 in 3 false positive chance, for a total of 5 in 9 (I assume the 5 in 8 from the paper is a typo). But actually there are only 2 valid states: 01, 10. The valid inputs are still 01, 10, 11, though, so the real false positive chance is 1 in 3. Maybe I'm missing something.
- plopilop 9y ago
  "Valid" configurations do not exist, there are only optimal/suboptimal and saturated/unsaturated ones. The classic FPR makes no assumptions about this (indeed optimality is derived from FPR minimum), and as such should apply as well to suboptimal saturated configuration, were it correct. However looking at theorem 3 in [0] I think the difference between "classic" and "real" FPR is small, especially for larger n and m. At the end of [0] is mentioned a study in which the authors could not reach the classic FPR in their simulations, but attributed this result to bad pseudorandomness of elements. [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure). The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1). Same for the second element, which yields 16 different cases. Out of these 16 cases 10 will lead to a false positive.
  - FreakLegion 9y ago
    > The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1) Thanks, that makes sense. I was thinking of states the filter could be in and ignored the different paths to get there. Now that I've had a chance to look at [0], it's interesting, but doesn't seem to matter for Bloom filters used in the normal way. > "Valid" configurations do not exist Sure, you can use any numbers you want, even negative ones. I take a more practical view, since Bloom filters make assumptions about choice (or derivation) of parameters. Given those assumptions, the formula criticized in [0] seems to work. Specifically: > [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure). We know the FPR of any Bloom filter that actually exists. For a load factor l and number of hash functions k, it's l^k. The problem is that the FPR for the expected load factor of a set of parameters is lower than the expected FPR for those parameters, iff the expected load factor is greater than half. But the whole point of a Bloom filter is to have half the bits set; that's the magic that minimizes size and FPR. In practice you won't often have an expected load factor of exactly half, due to rounding. Depending on how you handle that, and whether you use asymptotics or an exact calculation, some drift in FPR makes sense. It'll be negligible as long as you're targeting half, though. n = 1, k = 2, m = 2 is noticeably off because at 3/4 it has a much higher expected load factor.

Recursing 9y ago

> even on Wikipedia Did you edit Wikipedia / add a reference to the paper?

FreakLegion 9y ago

I've only glanced at [0] but I'm skeptical on the face of it. Everything about Bloom filters falls right out of the binomial distribution, provided you follow the assumptions for optimal number of bits and hash functions. Given those, n = 1, k = 2, m = 2 from the top of page 2 isn't even a valid configuration. Among other things, filters in which more than half the bits are set (within some tolerance) should be rejected. In this example a third of the filter's possible states are completely saturated and have to be tossed out. Otherwise you have a 100% false positive rate for that filter. I.e. if a saturated filter were acceptable, there are 3 states: 01, 10, 11. These have, respectively, a 1 in 3, 1 in 3, and 3 in 3 false positive chance, for a total of 5 in 9 (I assume the 5 in 8 from the paper is a typo). But actually there are only 2 valid states: 01, 10. The valid inputs are still 01, 10, 11, though, so the real false positive chance is 1 in 3. Maybe I'm missing something.

plopilop 9y ago
"Valid" configurations do not exist, there are only optimal/suboptimal and saturated/unsaturated ones. The classic FPR makes no assumptions about this (indeed optimality is derived from FPR minimum), and as such should apply as well to suboptimal saturated configuration, were it correct. However looking at theorem 3 in [0] I think the difference between "classic" and "real" FPR is small, especially for larger n and m. At the end of [0] is mentioned a study in which the authors could not reach the classic FPR in their simulations, but attributed this result to bad pseudorandomness of elements. [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure). The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1). Same for the second element, which yields 16 different cases. Out of these 16 cases 10 will lead to a false positive.
- FreakLegion 9y ago
  > The 5/8 probability mentioned is indeed correct. First element has four equiprobable possible outputs for its two hashes: (0,0), (0,1), (1,0) and (1,1) Thanks, that makes sense. I was thinking of states the filter could be in and ignored the different paths to get there. Now that I've had a chance to look at [0], it's interesting, but doesn't seem to matter for Bloom filters used in the normal way. > "Valid" configurations do not exist Sure, you can use any numbers you want, even negative ones. I take a more practical view, since Bloom filters make assumptions about choice (or derivation) of parameters. Given those assumptions, the formula criticized in [0] seems to work. Specifically: > [0]'s author claim that the difference may instead come from the real FPR value (which is actually very hard to compute, so it's hard to be sure). We know the FPR of any Bloom filter that actually exists. For a load factor l and number of hash functions k, it's l^k. The problem is that the FPR for the expected load factor of a set of parameters is lower than the expected FPR for those parameters, iff the expected load factor is greater than half. But the whole point of a Bloom filter is to have half the bits set; that's the magic that minimizes size and FPR. In practice you won't often have an expected load factor of exactly half, due to rounding. Depending on how you handle that, and whether you use asymptotics or an exact calculation, some drift in FPR makes sense. It'll be negligible as long as you're targeting half, though. n = 1, k = 2, m = 2 is noticeably off because at 3/4 it has a much higher expected load factor.