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:

[dependencies]
xorfilter-rs = "0.2.0"

or

[dependencies]
xorfilter-rs = { git = "https://github.com/prataprc/xorfilter" }

use xorfilter::{xor8::Xor8Builder, BuildHasherDefault};

fn main() {
    let num_keys = 1000;
    let lookup = 10;
    let mut b = Xor8Builder::<BuildHasherDefault>::default();
    for i in 0..num_keys {
        if i % 2 == 0 {
            b.insert(&i);
        }
    }

    // build bitmap.
    let filter = b.build().unwrap();
    for key in 0..lookup {
        // there can be false positives, but no false negatives.
        println!("{key}: {}", filter.contains(&key));
    }
}

Open issues

• Serialize / Deserialize Xor8 type.
• Incrementally adding keys to a pre-built Xor8 instance.
• Gather benchmark results for other implementations - Go, C, C++, Erlang, Java, Python.

Benchmarks

Following are the results for a set of 10-million u64 keys:

	build 10M keys	membership	FPP	Bits/Entry
Xor8-C	1.206 secs	NA	0.389 %	9.84 bits
Xor8-rust	1.809 secs	61.716 ns	0.392 %	9.84 bits
Fuse8-C	0.508 secs	NA	0.390 %	9.02 bits
Fuse8-rust	0.577 secs	42.657 ns	0.392 %	9.02 bits
Fuse16-C	0.515 secs	NA	0.001 %	18.04 bits
Fuse16-rust	0.621 secs	54.657 ns	0.001 %	18.03 bits

• Build time is measured in Seconds, for 10 million entries.
• Membership is measured in Nanosec, for single lookup in a set of 10 million entries.
• FPP = False Positive Probability measured in percentage

Useful links

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

Contribution

• Simple workflow. Fork - Modify - Pull request.
• Before creating a PR,
  • Run make build to confirm all versions of build is passing with 0 warnings and 0 errors.
  • Run check.sh with 0 warnings, 0 errors and all test-cases passing.
  • Run perf.sh with 0 warnings, 0 errors and all test-cases passing.
  • Install and run cargo spellcheck to remove common spelling mistakes.
• Developer certificate of origin is preferred.