Lib.rs

Rust 实现的异或过滤器库

在 rust-lang 中实现了 Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters，发表于《实验算法杂志》（待发表）。

此包是从其 golang 实现版本 转换而来。

如何在 Rust 项目中使用 xorfilter？

在项目的 Cargo.toml 中添加以下内容

[dependencies]
xorfilter-rs = "0.2.0"

或

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

use xorfilter::Xor8;

let mut keys: Vec<u64> = vec![];
for _ in 0..num_keys {
    keys.push(rng.gen());
}

let mut filter = Xor8::new(); // new filter.
filter.populate_keys(&keys); // populate keys.
filter.build(); // build bitmap.

for key in 0..lookup {
    // there can be false positives, but no false negatives.
    filter.contains_key(key);
}

打开问题

• 序列化/反序列化 Xor8 类型。
• 向预先构建的 Xor8 实例逐步添加密钥。
• 收集其他实现（Go、C、C++、Erlang、Java、Python）的基准测试结果。

基准测试

以下是针对 1000 万个 u64 密钥的测试结果

• 构建时间 以秒为单位，针对 1000 万条记录。
• 成员资格 以纳秒为单位，针对 1000 万条记录中的一个查找。
• 假阳性率 以百分比表示

有用链接

• 异或过滤器：比布隆过滤器和小鸟过滤器更快、更小
• 由 Daniel Lemire 发表的博客文章

贡献

• 简单的工作流程。Fork - 修改 - 提交请求。
• 在创建 PR 之前，
  • 运行 make build 以确认所有构建版本均通过，无警告和无错误。
  • 使用 0 警告、0 错误和所有测试用例通过运行 check.sh。
  • 使用 0 警告、0 错误和所有测试用例通过运行 perf.sh。
  • 安装 并运行 cargo spellcheck 以移除常见的拼写错误。
• 推荐使用开发者原产地证书。