Re:A Visual Interactive Guide to Bloom Filters
by thinkharderdev on Tuesday February 20, 2024 @04:18PM
(#39447049)
Not sure, but I recently came across xorsat filters (https://eecs.ceas.uc.edu/~weaversa/XORSATFilters.pdf). It's not a great replacement for bloom filters in many use cases because they are not modifiable but have some other interesting properties:
1. They are very close to the information theoretic minimum needed to encode the information so are more space-efficient than bloom filters or cuckoo filters.
2. They have a natural way to store metadata (at the cost of additional space of course) so you can associate a few bits of metadata with each set bit at pretty reasonable space cost.
1. They are very close to the information theoretic minimum needed to encode the information so are more space-efficient than bloom filters or cuckoo filters.
2. They have a natural way to store metadata (at the cost of additional space of course) so you can associate a few bits of metadata with each set bit at pretty reasonable space cost.