Membership filters are very efficient filters that guarantee no false negatives, but false positives are possible (how much and how many can be adjusted based on the dataset and filter's parameters). An obvious application could something like checking whether passengers are in a no-fly list, where false-positives could be handled by further checks. As far as I know cuckoo filters [0] are the state of the art for this, but per this work in principle you could make very efficient with using a SAT (or XORSAT) solver that could generate many feasible solutions out of random SAT problems.
- Google scholar pointed out this link to get a pdf for one of the papers cited in the repo [1]
My favourite part of these research publications from the US Gov is the licensing.
All of the USDS work is published with "No Copyright".
The SAT filters however still do not support incremental building, which is one of bloom filters fun features when you use them in distributed databases (you can build N of them and then OR bloom filters to get a single one).
I imagine it will still be incredibly useful where you can iterate over them and do OR the old fashioned way, but at higher accuracy for the same size.
the reference in the repo is paywalled (US$ 30!). I did find this https://arxiv.org/pdf/1912.08258 which may or may not be related. but what I found interesting is that the construction looks alot like perfect hashes
- Google scholar pointed out this link to get a pdf for one of the papers cited in the repo [1]
[0] https://en.wikipedia.org/wiki/Cuckoo_filter
[1] http://t-news.cn/Floc2018/FLoC2018-pages/proceedings_paper_4...
reply