4 ms·
I remember discussing bloom and cuckoo filters a while back and someone linked.to.great papers from late 2010s with much more advanced probabilistic structures
by naugtur 3y ago
I remember discussing bloom and cuckoo filters a while back and someone linked.to.great papers from late 2010s with much more advanced probabilistic structures that were handling modification much better or had other interesting properties. Anyone here knows where to look for these? I didn't take notes...
- thinkharderdev 3y agoNot sure, but I recently came across xorsat filters (https://eecs.ceas.uc.edu/~weaversa/XORSATFilters.pdf 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.
- naugtur 3y agoInteresting! 2 makes me wonder if it could work as a very bad but space efficient key-value store ;D
- randomizedalgs 3y agoMaybe quotient filters?
- naugtur 3y agoYes, that's one of the bloom successors I was looking for. Thanks. Link for people reading this: https://systemdesign.one/quotient-filter-explained/ https://systemdesign.one/quotient-filter-explained/ I remember there's more obscure newer stuff someone showed me in 2019 tho.