3 ms·

> 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 Erro

> 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.
- gopiandcode 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 Good point, You are right that our correction does not address errors in Bloom's original definition, but rather in the definition of the Bloom filter that is typically used - I'll add a note to address this. > 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. Yes, you are right, that's probably too strong a claim, my aim was to emphasize that there is more certainty in the proof, making it unlikely that there are no further hidden errors, but that was not clear.

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.

gopiandcode 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 Good point, You are right that our correction does not address errors in Bloom's original definition, but rather in the definition of the Bloom filter that is typically used - I'll add a note to address this. > 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. Yes, you are right, that's probably too strong a claim, my aim was to emphasize that there is more certainty in the proof, making it unlikely that there are no further hidden errors, but that was not clear.