19 releases

0.2.2 Dec 14, 2021
0.2.1 Oct 5, 2021
0.2.0 Sep 6, 2021
0.1.6 Aug 9, 2021
0.0.4 Dec 30, 2019

#2174 in Data structures

Download history 15/week @ 2024-07-28

81 downloads per month

MIT license

44KB
935 lines

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.


lib.rs:

XorFilter: const generic powered set membership approximation.

No runtime deps