Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



I 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.


That 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.


You 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.


It is two words: “Bloom filter”.


The original article used "Bloomfilter" instead of "Bloom filter". As of 2020-08-02, some of those mistakes have been corrected. Two mistakes remain.




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: