News for hackers. Stuff that matters.
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/

There are no comments on this comment yet.