Xorfilter

A no_std, no alloc crate for membership approximation.

Quick Start


const SIZE: usize = 100000;
const N: usize = capacity::<SIZE>();

let mut keys = [0; SIZE];

for i in 0..SIZE {
    keys[i] = splitmix64(i as u64);
}

let x: XorFilter<u8, N> = XorFilter::new(&keys);

for i in 0..SIZE {
    x.contains(keys[i]);
}

Status

No Docs
- Blocking on const_evaluatable_checked
No serialization
- Blocking on Serde

Why Xorfilter

Xorf needs alloc for Vec, which is limiting in various no_std environments.

Limitations

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

Xorfilters could benefit from some features in const generics that are not yet in nightly. We did not want to wait for const generic xor filters, so that is the reason behind why there are some uses of const fn and Sized.

Reference