Hacker News Reader

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

View on HN

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.

Interesting! 2 makes me wonder if it could work as a very bad but space efficient key-value store ;D

Maybe quotient filters?

Yes, that's one of the bloom successors I was looking for. Thanks.

Link for people reading this: https://systemdesign.one/quotient-filter-explained/

I remember there's more obscure newer stuff someone showed me in 2019 tho.

Reply on news.ycombinator.com