Struct BloomFilterCascade 

pub struct BloomFilterCascade { /* private fields */ }

Cascaded bloom filters with decreasing false positive rates

Design

Organizes multiple bloom filters in a cascade where:

• First filter (L0): Smallest, catches most negatives quickly
• Subsequent filters: Progressively lower FPR for items that pass

Benefits

• Fast rejection of non-existent keys (first filter catches ~99%)
• Lower overall FPR than single filter for same memory budget
• Amortized O(1) lookup with early termination

Example Configuration

L0: 1% FPR, 100KB  → Catches 99% of negatives
L1: 0.1% FPR, 50KB → Catches 99.9% of remaining
L2: 0.01% FPR, 25KB → Final filter for edge cases
Combined FPR: 0.01 * 0.001 * 0.0001 = 0.000000001 (1 in billion)

Implementations

impl BloomFilterCascade

pub fn new(expected_items: usize, level_fprs: Vec<f64>) -> Self

Create a new cascade with specified levels

Arguments

• expected_items - Number of items to store
• level_fprs - False positive rate for each level (e.g., [0.01, 0.001, 0.0001])

pub fn default_cascade(expected_items: usize) -> Self

Create default 3-level cascade

• L0: 1% FPR (fast initial check)
• L1: 0.1% FPR (medium precision)
• L2: 0.01% FPR (high precision)

pub fn compact(expected_items: usize) -> Self

Create memory-optimized 2-level cascade

pub fn insert<T: Hash>(&mut self, item: &T)

Insert an item into all cascade levels

pub fn contains<T: Hash>(&self, item: &T) -> bool

Check if item might exist (with early termination)

Returns false (definitely not present) as soon as any level returns false. Returns true only if ALL levels return true.

pub fn contains_with_level<T: Hash>(&self, item: &T) -> (bool, usize)

Check with level tracking (for debugging/stats)

pub fn combined_fpr(&self) -> f64

Combined theoretical false positive rate

pub fn num_levels(&self) -> usize

Number of cascade levels

pub fn memory_usage(&self) -> usize

Memory usage in bytes

pub fn to_bytes(&self) -> Vec<u8>

Serialize to bytes

pub fn from_bytes(bytes: &[u8]) -> Result<Self>

Deserialize from bytes

Trait Implementations

impl Debug for BloomFilterCascade

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.