Re:Bloom Filters by Example (2013)
by Piezoid on Tuesday May 14, 2019 @01:03PM
(#19911283)
In my field (bioinformatics), there is a trend of using a single hash function, an over-sized bloom filter which is then compressed with something like entropy optimal RRR[1] or RoaringBitmap bit vectors.
The resulting bloom filter ends up taking the same space than a properly sized bloom filter. There is two advantages: knowing the size of the set in advance is not necessary, and a single hash computation and memory access per query. However updates are not well supported.
[1] Raman, R., Raman, V., & Rao, S. S. (2002, January). Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. A blog post: https://alexbowe.com/rrr/
[1] Raman, R., Raman, V., & Rao, S. S. (2002, January). Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. A blog post: https://alexbowe.com/rrr/