Rust library implementing xor filters
Implementation of Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters in rust-lang, Journal of Experimental Algorithmics (to appear).
This package is a port from its golang implementation.
How to use xorfilter in my rust project ?
Add the following under project's Cargo.toml
:
[]
= "0.2.0"
or
[]
= { = "https://github.com/bnclabs/xorfilter" }
use Xor8;
let mut keys: = vec!;
for _ in 0..num_keys
let mut filter = new; // new filter.
filter.populate_keys; // populate keys.
filter.build; // build bitmap.
for key in 0..lookup
Open issues
- Serialize / Deserialize Xor8 type.
- Incrementally adding keys to a pre-built Xor8 instance.
Benchmarks
Benchmark number for original golang implementation.
BenchmarkPopulate100000-32 2000 695796 ns/op
BenchmarkContains100000-32 200000000 7.03 ns/op
Benchmark number for this rust-lang implementation.
test bench_populate_100000 ... bench: 274,349 ns/iter (+/- 18,650)
test bench_contains_100000 ... bench: 7 ns/iter (+/- 0)
Measure of false-positive-rate and bits-per-entry in original golang implementation, using random set of keys.
bits per entry 9.864
false positive rate 0.3874
Measure of false-positive-rate and bits-per-entry in this rust-lang implementation, using random set of keys.
bits per entry 9.864 bits
false positive rate 0.3866%