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.

Open issues

• [ ] Serialize / Deserialize Xor8 type.
• [ ] Incrementally adding keys to a pre-built Xor8 instance.

Benchmarks

Benchmark number for original golang implementation.

text BenchmarkPopulate100000-32 2000 695796 ns/op BenchmarkContains100000-32 200000000 7.03 ns/op

Benchmark number for this rust-lang implementation.

test 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.

text 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.

text bits per entry 9.864 bits false positive rate 0.3866%

Resources

• Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
• Blog post by Daniel Lemire