3 ms·

There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). So this approach falls under "c

There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). So this approach falls under "compute a probable value" as there is a non-zero probability that some filters have > 4, or even higher. So you will have fpr > 1%. When you count, you have the assurance of fpr < 1.0% at the cost of 4 additional bits / array element. For this design, it's just a step or two away from venturing into 3.5 or 7% error rates. And if you simulate it, you'll see a gaussian distribution with mean at theoretical capacity (len x 4) and some standard deviation. By capping bits, we cut a lot of possible cases that exceed the mean, but will not eliminate them. It's pretty straightforward to simulate this and get empirical data to see if their impact (of fp) is acceptable.

a1369209993 5y ago
> There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). > there is a non-zero probability that some filters have > 4, or even higher. Overlapped bits don't contribute to false positive rate. As a unlikely-but-simple example, consider a filter with 3 items, marking 15 distinct indexes, and a new 'fourth' item whose 5 indexes all align with one of the existing 15 indexes. Adding this new item does not change the filter at all, and so cannot change the false positive rate. In general the false positive rate (assuming our hash function is good, ie H(X) is independently uniformly random for each X) is the chance that a uniformly random hash passes the filter. For a N bit filter with P bits marked, and K bits per element, that's (P/N)^K (select K random indexes, and check if they're all marked, which they will be with probability P out of N each). Since N and K are fixed, the FPR only depends on the popcount P. A straightforward bloom filter can't depend on the number of items inserted (seperately from the number of marked bits), because that information isn't even present.

a1369209993 5y ago

> There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). > there is a non-zero probability that some filters have > 4, or even higher. Overlapped bits don't contribute to false positive rate. As a unlikely-but-simple example, consider a filter with 3 items, marking 15 distinct indexes, and a new 'fourth' item whose 5 indexes all align with one of the existing 15 indexes. Adding this new item does not change the filter at all, and so cannot change the false positive rate. In general the false positive rate (assuming our hash function is good, ie H(X) is independently uniformly random for each X) is the chance that a uniformly random hash passes the filter. For a N bit filter with P bits marked, and K bits per element, that's (P/N)^K (select K random indexes, and check if they're all marked, which they will be with probability P out of N each). Since N and K are fixed, the FPR only depends on the popcount P. A straightforward bloom filter can't depend on the number of items inserted (seperately from the number of marked bits), because that information isn't even present.