4 ms·
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
by 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 agoFor 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]