Warning
Work in progress.
Probabilistic filters data structures in Rust.
- Standard Bloom filter - classic flat bit array with double hashing
- Blocked Bloom filter - 512-bit blocks, multiplicative remix probing (follows RocksDB's
FastLocalBloomImpl) - Register-blocked Bloom filter — 64-bit word-sized blocks with mask-based insert/query
- Prefix Bloom filter - fixed-length prefix extractor over a blocked filter
- Diva range filter
- Serialization
use probfilter::bloom::standard::StandardBloomFilter;
use probfilter::traits::{PointFilter, FilterInsert};
let mut filter = StandardBloomFilter::new(10_000, 0.01);
filter.insert(b"hello");
assert!(filter.may_contain(b"hello"));cargo testcargo bench --bench bloomFilter to a specific group:
cargo bench --bench bloom -- bloom_lookup
cargo bench --bench bloom -- bloom_insertResults are saved to target/criterion/ with HTML reports.
- Modern Bloom Filters: 22x Faster - the article that kicked this off, covering register-blocked and patterned filters with SIMD
- RocksDB Bloom Filter -
FastLocalBloomImpldesign and cache-line blocking - Diva: Dynamic Range Filter for Var-Length Keys and Queries (PVLDB 2025) - sampling trie with infix compression
- Bloom Filters (Arpit Bhayani) - FPR derivations, optimal sizing formulas, and the Kirsch-Mitzenmacher double hashing trick
MIT