Struct StableBloomFilter

pub struct StableBloomFilter { /* private fields */ }

Implementations

impl StableBloomFilter

pub fn new(m: usize, d: u8, fp_rate: f64) -> Self

Creates a new Stable Bloom Filter with m cells and d bits allocated per cell optimized for the target false-positive rate. Use default if you don’t want to calculate d.

pub fn new_default(m: usize, fp_rate: f64) -> Self

Creates a new Stable Bloom Filter with m 1-bit cells and which is optimized for cases where there is no prior knowledge of the input data stream while maintaining an upper bound using the provided rate of false positives.

pub fn new_unstable(m: usize, fp_rate: f64) -> Self

NewUnstableBloomFilter creates a new special case of Stable Bloom Filter which is a traditional Bloom filter with m bits and an optimal number of hash functions for the target false-positive rate. Unlike the stable variant, data is not evicted and a cell contains a maximum of 1 hash value.

pub fn cells(&self) -> usize

Returns the number of cells in the Stable Bloom Filter.

pub fn k(&self) -> usize

Returns the number of hash functions.

pub fn p(&self) -> usize

Returns the number of cells decremented on every add.

pub fn max(&self) -> u8

pub fn stable_point(&self) -> f64

Returns the limit of the expected fraction of zeros in the Stable Bloom Filter when the number of iterations goes to infinity. When this limit is reached, the Stable Bloom Filter is considered stable.

pub fn false_positive_rate(&self) -> f64

Returns the upper bound on false positives when the filter has become stable.

pub fn hash_kernel(&self, data: &[u8]) -> (u32, u32)

pub fn reset(&mut self) -> &Self

Restores the Stable Bloom Filter to its original state. It returns the filter to allow for chaining.

pub fn decrement(&mut self)

Will decrement a random cell and (p-1) adjacent cells by 1. This is faster than generating p random numbers. Although the processes of picking the p cells are not independent, each cell has a probability of p/m for being picked at each iteration, which means the properties still hold.

Trait Implementations

impl Filter for StableBloomFilter

fn test(&self, data: &[u8]) -> bool

Will test for membership of the data and returns true if it is a member, false if not. This is a probabilistic test, meaning there is a non-zero probability of false positives and false negatives.

fn add(&mut self, data: &[u8]) -> &Self

Will add the data to the Stable Bloom Filter. It returns the filter to allow for chaining.

fn test_and_add(&mut self, data: &[u8]) -> bool

Is equivalent to calling Test followed by Add. It returns true if the data is a member, false if not.