XorFilter: const generic powered set membership approximation.

Statically allocated membership approximation

Xorfilter

A no_std, no alloc crate for membership approximation.

Quick Start

const N: usize = 100000;
let mut keys = [0;N];

for i in 0..N {
    keys[i] = i as u64;
}

let x = XorFilter::from(keys);
      
for i in 0..N {
    x.contains(keys[i]);
}

Status

No Docs
- Blocking on generic_const_exprs
No serialization
- Blocking on Serde

Why Xorfilter

Other implementations need alloc for Vec.

Limitations

Xor Filters are not designed to work with duplicate values. [1]

XorFilter could benefit from some features in const generics that are not yet in nightly.

Reference

[1] Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, Journal of Experimental Algorithmics.