Expand description
Pleated construction for ribbon filters: partition-instead-of-sort.
A ribbon filter is a space-optimal approximate-membership filter (~7.6 bits/key at ~0.8% false-positive rate). This crate builds it fast by pleating — one counting pass groups keys into cache-sized windows before banding, giving ~2x faster construction at scale for a bit-identical result.
§Example
use pleat::filter::RibbonFilter;
let keys: Vec<u64> = (0..100_000).collect();
let f = RibbonFilter::from_keys_pleated(&keys);
assert!(f.contains(42)); // members never missing
// Absent keys are rejected with ~99.2% probability.
let _probably_absent = f.contains(999_999_999);filter::RibbonFilter is the homogeneous w=64 filter; filter::StdRibbon is the
standard w=128 (RocksDB-shape) variant. Both support arrival, pleated, and parallel
construction (all bit-identical), tunable false-positive rate via the result-width
parameter, arbitrary hashable keys, batch queries, and serialization.
Modules§
- filter
- Public ribbon filter API with pleated construction.
- format
- Versioned, self-describing serialization envelope for persisted filters.