4 ms·

> The article doesn't say that the original proof was incorrect Apologies if my wording did not make this clear: the original proof by Bloom is logically incor

> The article doesn't say that the original proof was incorrect Apologies if my wording did not make this clear: the original proof by Bloom is logically incorrect Bloom derives his expression by performing a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. It just so happens that even if he had explicitly included this assumption, it would not have been justified. So in that sense, the debunking part is correct - we disprove Bloom's original bound by proving the true bound under the same assumptions that he explicitly makes.

ThePhysicist 6y ago
That's neat! Is the deviation between Bloom's equation and the correct one relevant in pratice? Typical Bloom filters have millions or even billions of bits and a few to a few dozen hash functions, so I think the probability that an entry gets hashed to the same bit more than once should be vanishingly small? Really cool otherwise, I should really look into Coq more for my own work.
- gopiandcode 6y ago
  For most practical applications, the sizes involved are such that you're probably dealing with the asymptotic behaviors, so the differences will be negligible and either bound can be used. In that sense, this work is really more theoretical than practical, but still, I think, a nice result.
  - deleted 6y ago
    [deleted]
tom_mellior 6y ago
> Bloom derives his expression by performing a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. I see, thanks for this clarification. I read your post as saying that the assumption was explicit. I agree that reasoning from an implicit assumption is a logical error. Still, the real problem was not the assumption being implicit/explicit but rather that one doesn't want to rely on it at all. Which again is an extra-logical issue. > So in that sense, the debunking part is correct - we disprove Bloom's original bound by proving the true bound under the same assumptions that he explicitly makes. OK. I don't think that recapitulating something that has been known with more or less certainty for 12 years counts as "debunking". For me "debunking" has a connotation of being original, maybe for you it doesn't. But I especially think that "the formula was only asymptotically correct" is too weak a statement to count as a "debunking". For me "debunking" an algorithm or a data structure would have to be something much bigger, like "Quicksort doesn't always sort" or "binary search trees can lose data" or "Bloom filters can sometimes have false negatives". Not "the behavior we have been seeing for the last 50 years matches the original formula well, but strictly speaking it matches the new formula a bit better". Your mileage obviously varies. EDIT: Let me stress again that I'm not pooping on your work. The work appears sound and important, since this was so tricky to get right in the past. But I am pooping on the title.
- gopiandcode 6y ago
  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.
a1369209993 6y ago
> a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. Am I misunderstanding what you and/or the article means by "independent"? The fact that indexes derived from (non-overlapping) parts of a hash function output are uniformly ((preferably crypographically-secure-)psuedo-)random (and thus uncorrelated with each other and with indexes from other hash invocations) is what the phrase "hash function" means ("avalanche effect" if I remember my terminology correctly).

ThePhysicist 6y ago

That's neat! Is the deviation between Bloom's equation and the correct one relevant in pratice? Typical Bloom filters have millions or even billions of bits and a few to a few dozen hash functions, so I think the probability that an entry gets hashed to the same bit more than once should be vanishingly small? Really cool otherwise, I should really look into Coq more for my own work.

gopiandcode 6y ago
For most practical applications, the sizes involved are such that you're probably dealing with the asymptotic behaviors, so the differences will be negligible and either bound can be used. In that sense, this work is really more theoretical than practical, but still, I think, a nice result.
- deleted 6y ago
  [deleted]

tom_mellior 6y ago

> Bloom derives his expression by performing a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. I see, thanks for this clarification. I read your post as saying that the assumption was explicit. I agree that reasoning from an implicit assumption is a logical error. Still, the real problem was not the assumption being implicit/explicit but rather that one doesn't want to rely on it at all. Which again is an extra-logical issue. > So in that sense, the debunking part is correct - we disprove Bloom's original bound by proving the true bound under the same assumptions that he explicitly makes. OK. I don't think that recapitulating something that has been known with more or less certainty for 12 years counts as "debunking". For me "debunking" has a connotation of being original, maybe for you it doesn't. But I especially think that "the formula was only asymptotically correct" is too weak a statement to count as a "debunking". For me "debunking" an algorithm or a data structure would have to be something much bigger, like "Quicksort doesn't always sort" or "binary search trees can lose data" or "Bloom filters can sometimes have false negatives". Not "the behavior we have been seeing for the last 50 years matches the original formula well, but strictly speaking it matches the new formula a bit better". Your mileage obviously varies. EDIT: Let me stress again that I'm not pooping on your work. The work appears sound and important, since this was so tricky to get right in the past. But I am pooping on the title.

gopiandcode 6y ago
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.

a1369209993 6y ago

> a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. Am I misunderstanding what you and/or the article means by "independent"? The fact that indexes derived from (non-overlapping) parts of a hash function output are uniformly ((preferably crypographically-secure-)psuedo-)random (and thus uncorrelated with each other and with indexes from other hash invocations) is what the phrase "hash function" means ("avalanche effect" if I remember my terminology correctly).