3 ms·

"Valid" configurations do not exist, there are only optimal/suboptimal and saturated/unsaturated ones. The classic FPR makes no assumptions about this (indeed o

"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.

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.