xor filters?

[Jan Steemann]

Hi,

has anyone ever considered the usage of Xor and Binary Fuse Filtes instead of using Bloom or Ribbon filters for key probing?

There is a C library that implements them:

https://github.com/FastFilter/xor_singleheader

The claim from https://github.com/FastFilter/xor_singleheader#header-only-xor-and-binary-fuse-filter-library is

Bloom filters are used to quickly check whether an element is part of a set. Xor filters and binary fuse filters are faster and more concise alternative to Bloom filters. Furthermore, unlike Bloom filters, xor and binary fuse filters are naturally compressible using standard techniques (gzip, zstd, etc.). They are also smaller than cuckoo filters. They are used in production systems.

• Thomas Mueller Graf, Daniel Lemire, Binary Fuse Filters: Fast and Smaller Than Xor Filters, Journal of Experimental Algorithmics (to appear). DOI: 10.1145/3510449
• Thomas Mueller Graf, Daniel Lemire, Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, Jou

There is also a C++ implementation with a benchmark suite, comparing these filters against Bloom and Ribbon filter implementations:

https://github.com/FastFilter/fastfilter_cpp

Does anyone have experience with these types of filters and would expect that they indeed allow more efficient access and more compact representation than Bloom and/or Ribbon filters? If they are indeed better (as claimed), they would seem like a natural fit for a new RocksDB FilterPolicy implementation.

[Ted Mostly]

`ribbon filter` is some kind of `xor filter`, enhancement

---

	Ted Mostly wangh...@qq.com

[Dan Carfas]

Hey Jan.
Thanks for the great feature suggestion. We are going to open a ticket and do some homework about it 
Your input would be appreciated - please join the discord server here and this is the link to the thread about your suggestion.