7 ms·
related and useful: "Ribbon filter: Practically smaller than Bloom and Xor" (https://arxiv.org/abs/2103.02515 https://arxiv.org/abs/2103.02515) This paper does
by awmarthur 4y ago
related and useful: "Ribbon filter: Practically smaller than Bloom and Xor" (https://arxiv.org/abs/2103.02515 https://arxiv.org/abs/2103.02515)
This paper does a good job of showing the space/time tradeoffs of various approximate sets.
- Genbox 4y agoSimilarly, there is Binary Fuse Filters (https://arxiv.org/abs/2201.01174 https://arxiv.org/abs/2201.01174) [1] The paper includes comparisons with Ribbon filter [1] Graf, T. M., & Lemire, D. (2022). Binary Fuse Filters: Fast and Smaller Than Xor Filters. arXiv. https://doi.org/10.1145/3510449 https://doi.org/10.1145/3510449
- eloff 4y agoThanks for sharing! Ribbon filters, xor filters, these binary fuse filters, are all immutable sets where the keys are known at construction time. But there are many classes of problems where that's true.
- nullc 4y agoIt's not really a very equal comparison to compare something that supports dynamic updates and which doesn't. If you're willing to compare arbitrary operating behavior, a simple entropy coded bitset will achieve the information theoretic bound -- it just isn't updatable or queryable on the fly. :P
- vlovich123 4y agoBut these other filters are dynamically queryable on the fly. I think all these keys also support dynamic additions. What they don’t support (and neither does Bloom afaik) is removal of a key. For the kinds of typical applications for these, it tends to fit well enough.
- vlovich123 4y agoI’m wrong. You need to give the entire set of keys upfront during construction for some of these filters.
- nullc 4y agoYeah, I believe ~all of the ones with greater space efficiency than cuckoo filters (or blocked bloom, depending on the false positive rate) don't have incremental insert.