3 ms·

I guess we'll have to agree to disagree here. Given the history of the proofs of the Bloomfilter, I'd argue that the bound was not really "known with more or l

I guess we'll have to agree to disagree here. Given the history of the proofs of the Bloomfilter, I'd argue that the bound was not really "known with more or less certainty" - if so many corrections had to be made, why should we believe that this latest paper was truly correct? it does not seem to be unreasonable to believe that there might be other errors that had been been similarly overlooked. Our research tackles this problem - it provides a guarantee that there are no further hidden errors. > "the formula was only asymptotically correct" I have no issues with the behaviors of a data structure being characterized in an asymptotic sense, but I do think that giving a bound that you claim to hold exactly, but then having it turn out to only hold asymptotically is incorrect and worthy of debunking. Furthermore, most citations of Bloom's bound do not claim it is an asymptotic bound, but use it as an exact one, which is clearly incorrect.

aflag 6y ago
I think from an engineering perspective it doesn't feel like a debunking. Nothing we assume about the bloom filter has been fundamentally changed. I think that might be the perspective of most people in here.
- gopiandcode 6y ago
  Yes, I think that's an accurate take on the work. At the end of the day, this is primarily a formal result with few direct implications on practical usage. As I mentioned in another post, I tried to make it more relatable to an engineering audience, but it's possible that I may have buried the lede somewhat. However, I still stand by the statement that the title is not incorrect, at least if only from a mathematical perspective.
  - deleted 6y ago
    [deleted]
- CydeWeys 6y ago
  Good point. The main Bloom filter I use at work is 8 million bits in size, and at that scale, it does seem completely negligible whether you account for bits being selected by multiple hash functions since the odds of that happening are so small. We could add a few bits to the 8 million to correct for the error, but that's not meaningfully changing anything; it's just a drop in the bucket.
FreakLegion 6y ago
> Our research tackles this problem - it provides a guarantee that there are no further hidden errors Does it? At a glance you seem to have evaluated Bloom's false positive rate against Knuth's version of the filter. I say this because your starting point is Bose, whose result is for Knuth's version. The popular "Bloom filter" is not, in fact, Bloom's filter. Their different constructions lead to different exact false positive rates, so I suspect you've failed to prove anything about Bloom's original paper. Of course Bloom was wrong in any case. Grandi's "On the Analysis of Bloom Filters" (2017) is the paper to read there. It was the first to offer an exact account of the false positive rate for Bloom's construction.
- gopiandcode 6y ago
  > so I suspect you've failed to prove anything about Bloom's original paper In Bloom's original paper "Space/Time Trade-offs in Hash Coding with Allowable Errors", Bloom proposes multiple variants of these filter structures, and it is true that these variants do have different behaviours. However, the expression cited as Bloom's bound (equations 16/17 in the paper) are specifically about a data structure (he refers to it as method 2) that works exactly like the standard definition of a Bloom filter (Knuth's version). In this sense, our result holds for Bloom's bound. For reference, Bloom's description of method 2 is as follows: > Method 2 competely gets away from the conventional concept of organizing the hash area into cells. The hash area is considered as N individual addressable bits, with addresses 0 through N - 1. It is assumed that all bits in the hash area are first set to 0. Next, each message in the set to be stored is hash coded into a number of distinct bit addresses, say al, a2, ..., ad. Finally, all d bits addressed by al through ad are set to 1. > To test a new message a sequence of d bit addresses, say al, a2, .. , ad, is generated in the same manner as for storing a message. If all d bits are 1, the new message is accepted. If any of these bits is zero, the message is rejected. Clearly this method describes the conventional version of the Bloom filter.
  - FreakLegion 6y ago
    This is an easy mistake to make. Note the word distinct: > each message in the set to be stored is hash coded into a number of distinct bit addresses In Knuth's filter, the addresses aren't distinct. Bloom's construction requires that they are, thus the probability of a bit being set to 0 from (16) in Bloom's paper is 1−(1−k/m)^n, different from the 1−(1−1/m)^(kn) in your paper. Cuckoo hashing is commonly simplified in a similar way, indexing into a single table and allowing the hashes to overlap, unlike Pagh's original. Anyway, from your paper: > Bloom then claimed that the probability of a false positive was simply the probability of a single bit being set, raised to the power of k, reasoning that a false positive for an element y ∈ bf only occurs when all the k bits corresponding to the hash outputs are set. > Unfortunately, as was later pointed out by Bose et al.[8], as the bits specified by f_1(x),...,f_k−1(x) may overlap, we cannot guarantee the independence that is required for any simple relation between the probabilities. You're still right that Bloom is off, but it's not due to overlap in f_1(x),...,f_k−1(x), which his construction doesn't allow. My broader point though was about your "guarantee that there are no further hidden errors", because a theorem prover is just a tool, tools are used by people, and people make mistakes.

aflag 6y ago

I think from an engineering perspective it doesn't feel like a debunking. Nothing we assume about the bloom filter has been fundamentally changed. I think that might be the perspective of most people in here.

gopiandcode 6y ago
Yes, I think that's an accurate take on the work. At the end of the day, this is primarily a formal result with few direct implications on practical usage. As I mentioned in another post, I tried to make it more relatable to an engineering audience, but it's possible that I may have buried the lede somewhat. However, I still stand by the statement that the title is not incorrect, at least if only from a mathematical perspective.
- deleted 6y ago
  [deleted]
CydeWeys 6y ago
Good point. The main Bloom filter I use at work is 8 million bits in size, and at that scale, it does seem completely negligible whether you account for bits being selected by multiple hash functions since the odds of that happening are so small. We could add a few bits to the 8 million to correct for the error, but that's not meaningfully changing anything; it's just a drop in the bucket.

FreakLegion 6y ago

> Our research tackles this problem - it provides a guarantee that there are no further hidden errors Does it? At a glance you seem to have evaluated Bloom's false positive rate against Knuth's version of the filter. I say this because your starting point is Bose, whose result is for Knuth's version. The popular "Bloom filter" is not, in fact, Bloom's filter. Their different constructions lead to different exact false positive rates, so I suspect you've failed to prove anything about Bloom's original paper. Of course Bloom was wrong in any case. Grandi's "On the Analysis of Bloom Filters" (2017) is the paper to read there. It was the first to offer an exact account of the false positive rate for Bloom's construction.

gopiandcode 6y ago
> so I suspect you've failed to prove anything about Bloom's original paper In Bloom's original paper "Space/Time Trade-offs in Hash Coding with Allowable Errors", Bloom proposes multiple variants of these filter structures, and it is true that these variants do have different behaviours. However, the expression cited as Bloom's bound (equations 16/17 in the paper) are specifically about a data structure (he refers to it as method 2) that works exactly like the standard definition of a Bloom filter (Knuth's version). In this sense, our result holds for Bloom's bound. For reference, Bloom's description of method 2 is as follows: > Method 2 competely gets away from the conventional concept of organizing the hash area into cells. The hash area is considered as N individual addressable bits, with addresses 0 through N - 1. It is assumed that all bits in the hash area are first set to 0. Next, each message in the set to be stored is hash coded into a number of distinct bit addresses, say al, a2, ..., ad. Finally, all d bits addressed by al through ad are set to 1. > To test a new message a sequence of d bit addresses, say al, a2, .. , ad, is generated in the same manner as for storing a message. If all d bits are 1, the new message is accepted. If any of these bits is zero, the message is rejected. Clearly this method describes the conventional version of the Bloom filter.
- FreakLegion 6y ago
  This is an easy mistake to make. Note the word distinct: > each message in the set to be stored is hash coded into a number of distinct bit addresses In Knuth's filter, the addresses aren't distinct. Bloom's construction requires that they are, thus the probability of a bit being set to 0 from (16) in Bloom's paper is 1−(1−k/m)^n, different from the 1−(1−1/m)^(kn) in your paper. Cuckoo hashing is commonly simplified in a similar way, indexing into a single table and allowing the hashes to overlap, unlike Pagh's original. Anyway, from your paper: > Bloom then claimed that the probability of a false positive was simply the probability of a single bit being set, raised to the power of k, reasoning that a false positive for an element y ∈ bf only occurs when all the k bits corresponding to the hash outputs are set. > Unfortunately, as was later pointed out by Bose et al.[8], as the bits specified by f_1(x),...,f_k−1(x) may overlap, we cannot guarantee the independence that is required for any simple relation between the probabilities. You're still right that Bloom is off, but it's not due to overlap in f_1(x),...,f_k−1(x), which his construction doesn't allow. My broader point though was about your "guarantee that there are no further hidden errors", because a theorem prover is just a tool, tools are used by people, and people make mistakes.