3 ms·
What if a distinct bit vector is used for each hash function? Then isn't the original false positive rate correct? Can you use less storage by having distinct
by phkahler 6y ago
What if a distinct bit vector is used for each hash function? Then isn't the original false positive rate correct?
Can you use less storage by having distinct bit vectors of each hash? This seems like a natural question once we know the false positive rates are different.
Maybe Bloom was misinterpreted and right all along?
- gopiandcode 6y agoGood point, You are right that our correction does not address errors in Bloom's original definition of a Bloom filter - which uses distinct bit vectors, but rather in the definition of the Bloom filter that is typically used (and referenced) in practice (Knuth's version) and in the literature, which functions in the way described in the article. This version is easier to implement as the hash functions are independent, but which does use incorrect reasoning in it's correctness proof. It's wrong to attribute this to Bloom, so I've added a note to address this.