3 ms·
There are variants of the Bloomfilter that do try and do this - one way is to have each hash function map to a separate distinct subsequence of the bitvector.
by gopiandcode 6y ago
There are variants of the Bloomfilter that do try and do this - one way is to have each hash function map to a separate distinct subsequence of the bitvector.
It does indeed reduce the false positive rate, but comes at the cost of increased space usage. As always, utility of this modification would depend on where you wanted to balance space-vs-accuracy constraints.
- anonymoushn 6y agoI would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash, and 1 out of the remaining N-2 from the third, and so on.
- gopiandcode 6y agoThat would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed. Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan. I think it might be interesting to look into though.
- anonymoushn 6y agoYou can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.
- xpe 6y agoIt is two words: “Bloom filter”.
- xpe 6y agoThe original article used "Bloomfilter" instead of "Bloom filter". As of 2020-08-02, some of those mistakes have been corrected. Two mistakes remain.