2 releases
0.1.1 | Jul 31, 2024 |
---|---|
0.1.0 | Jul 22, 2024 |
#342 in Database implementations
40 downloads per month
16KB
180 lines
Grafite
Grafite is a range filter with a simple design and clear theoretical guarantees that hold regardless of the input data and query distribution.
This library is a Rust implementation of the data structure introduced by this paper: Grafite: Taming Adversarial Queries with Optimal Range Filters.
The authors of this paper also created a C++ implementation for Grafite, which can be found on one of the author's GitHub: grafite
.
The Grafite data structure relies on the Elias-Fano encoding of non-decreasing integer sequences, and this library uses the vers_vecs
implementation of the encoding.
Examples
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));
TODO
Dependencies
~2.5MB
~47K SLoC