#serde #alloc #approximation

nightly no-std Xorfilter

No alloc membership approximation

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

#909 in Data structures

Download history 27/week @ 2022-12-09 9/week @ 2022-12-16 9/week @ 2022-12-23 6/week @ 2022-12-30 15/week @ 2023-01-06 13/week @ 2023-01-13 21/week @ 2023-01-20 18/week @ 2023-01-27 124/week @ 2023-02-03 77/week @ 2023-02-10 101/week @ 2023-02-17 2/week @ 2023-02-24 4/week @ 2023-03-03 6/week @ 2023-03-10 7/week @ 2023-03-17 7/week @ 2023-03-24

271 downloads per month

MIT license

43KB
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