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
81 downloads per month
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.