石墨

石墨 是一个具有简单设计和清晰理论保证的范围过滤器，这些保证不受输入数据和查询分布的影响。

这个库是这个论文中引入的数据结构的 Rust 实现： 石墨：使用最优范围过滤器驯服对抗查询。

该论文的作者还创建了一个 Grafite 的 C++ 实现，可以在作者的 GitHub 上找到： grafite。

石墨数据结构依赖于非递增整数序列的 Elias-Fano 编码，并且这个库使用了编码的 vers_vecs 实现。

示例

use grafite::{OrderPreservingHasher, RangeFilter};

let values = [1, 2, 3, 7, 8, 9, 15, 20];

let epsilon = 0.01;
let max_query_range = 20;
let hasher = OrderPreservingHasher::new(values.len(), epsilon, max_query_range)
    .expect("The input parameters should be valid");

let rf = RangeFilter::new(values.iter().copied(), hasher);

// If there are any values in the range, it will return `true`.
assert!(rf.query(..));
assert!(rf.query(..42));
assert!(rf.query(10..));
assert!(rf.query(0..20));

// Start is inclusive.
assert!(rf.query(3..5));
assert!(rf.query(9..16));

// End is exclusive. Note that false positives are possible depending on the input `epsilon`.
assert!(!rf.query(10..15));
assert!(rf.query(10..=15));

待定