Xorfilter

A no_std, no alloc crate for membership approximation.

Quick Start

0.1.0

use Xorfilter::*;

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

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

let x: XorFilter<u8, N> = XorFilter::new(keys);
      
for i in 0..N {
    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

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