3 ms·
Direct link to paper (pdf) - https://arxiv.org/pdf/1912.08258.pdf https://arxiv.org/pdf/1912.08258.pdf I haven't fully read the paper yet, but it seems like a
by colinchartier 7y ago
Direct link to paper (pdf) - https://arxiv.org/pdf/1912.08258.pdf https://arxiv.org/pdf/1912.08258.pdf
I haven't fully read the paper yet, but it seems like a variation of a bloom filter where membership is determined by xoring three hashes (see algorithm 1 in the pdf)
- aidenn0 7y agoIf that's the case then both membership and non-membership will be probabilistic, rather than one or the other being certain like boom filters, right?
- colinchartier 7y ago"Membership test: returns true if the key x is likely in S, false otherwise" I think they circumvent the problem by making a complicated insertion procedure where all of the keys need to be inserted at once, it seems uses a stack to avoid hash collisions Take a look at https://github.com/FastFilter/xorfilter/blob/master/xorfilter.go#L110 https://github.com/FastFilter/xorfilter/blob/master/xorfilte... I can usually read go, but I've never been that great at deciphering "academic code" so the exact details escape me here.
- DaiPlusPlus 7y agoYeah, TFA says it's intended as an immutable structure that has to be rebuilt to add new data to it - which limits its applications.
- layoutIfNeeded 7y agoYep, also the insertion procedure is retried with increasingly larger arrays until no “collisions” are encountered. Reminds me of minimal perfect hash construction.
- thomasmg 7y agoYes, the underlying theory is from a minimal perfect hash function called "BDZ": http://cmph.sourceforge.net/bdz.html http://cmph.sourceforge.net/bdz.html . Yes, sometimes a retry is needed, but the array is not made larger; it just retries with a different seed.