XOR filters

[crepererum]

https://lemire.me/blog/2019/12/19/xor-filters-faster-and-smaller-than-bloom-filters/

[dilawar]

https://github.com/bnclabs/xorfilter ?

[crepererum]

@dilawar I am aware that there other implementations already out there (same goes for hyperloglog for example). However the point of this crate here is to:

• offer one go-to place for all kind of probabilistic data structures
• act as some kind of learning material for this topic (this is why we have "how it works" sections for most data structures)
• offer a trait-based interface for data structures that offer the same functionality

If you already know you want data structure X and want the slimmest and most performant implementation, go to crates.io and pick one (or implement your own, because most of these data structures are only really fast if you choose the correct variant for your application).

Hope that makes sense 🙂

[dilawar]

Hi @crepererum, I am sorry for causing confusion by just dropping the link here without adding a few lines. And what you said totally makes sense.

I was wondering if it is possible to reuse the implementation from other crates with modifications to suit the points you mentioned above?

[crepererum]

I was wondering if it is possible to reuse the implementation from other crates with modifications to suit the points you mentioned above?

Technically yes, but I have two concerns:

1. they also implement a bunch of helpers and migrating the code should avoid duplicating this functionality
2. the license: they use Apache2, pdatastructs uses Apache2+MIT which IMHO is the Rust default. I would not like to drop the MIT bit, but we could ask xorfilter if they are willing to extend their license terms.