Struct ofilter::Params

pub struct Params {
    pub nb_hash: usize,
    pub bit_len: usize,
    pub nb_items: usize,
    pub fp_rate: f64,
    pub predict: bool,
}

Parameters used to build bloom filters.

This is a utility to set up various bloom filter parameters. There are typically 4 parameters:

• n (nb_items): number of items in the filter
• p (fp_rate): probability of false positives, fraction between 0 and 1
• m (bit_len): number of bits in the filter
• k (nb_hash): number of hash functions

All of them are linked, if one changes the size of the filter, obviously, it changes the number of items it can hold.

A few things to keep in mind:

• for a pure Bloom filter, the only technical parameters that matter are nb_hash and bit_len. They fully define the filter.
• from a functional point of view, most of the time you are interested in a given nb_items and fp_rate. From there the 2 others are derived.

You may partially fill this struct, anything which contains zero will be inferred either by deducing it from other defined params, or by replacing it with a default value. This is done by calling .adjust().

Also, there is a predict field which can be used to turn the filter into a predicatable filter. This is convenient for testing, and may be of interest in edge cases but most of the time a real random version is prefered. It avoids bias and also can protect against some DDOS attacks based on hash collision.

A few helpers are defined as well, for common use-cases.

A bit of theory

This interactive Bloom filter params calulator proved very useful while developping this. Also it recaps the usual formulas, with:

• n -> number of items in the filter
• p -> probability of false positives, fraction between 0 and 1
• m -> number of bits in the filter
• k -> number of hash functions

We have:

• n = ceil(m / (-k / log(1 - exp(log(p) / k))))
• p = pow(1 - exp(-k / (m / n)), k)
• m = ceil((n * log(p)) / log(1 / pow(2, log(2))))
• k = round((m / n) * log(2))

A command line equivalent would be this practical bloom-filter-calculator.rb gist

Note that there are corner cases, for example, the formula that gives bit_len (m) from nb_items (n) and fp_rate (p), corresponds to the optimal case, when nb_hash (k) has been chosen optimally. If not, it has to be revisited and adapted to the real value of nb_hash (k). In practice, unless you impose it, what this package does is enforce a nb_hash (k) of 2, which is generally optimal if you consider CPU time and not memory usage.

Links

• Bloom Filter on Wikipedia
• All About Bloom Filters
• Buffered Bloom Filters on Solid State Storage
• Age-Partitioned Bloom Filters
• countBF: A General-purpose High Accuracy and Space Efficient Counting Bloom Filter
• Stable Learned Bloom Filters for Data Streams
• Building a Better Bloom Filter

Examples

Getting a filter for a given number of items, everything else default:

use ofilter::Params;

let params = Params::with_nb_items(10_000);

assert_eq!("{ nb_hash: 2, bit_len: 189825, nb_items: 10000, fp_rate: 0.010000, predict: false }", format!("{}", &params));

Getting a filter for a given number of items, false positive rate, and enforcing number of hash:

use ofilter::Params;

let params = Params{
    nb_hash: 3,
    bit_len: 0,
    nb_items: 100_000,
    fp_rate: 0.1,
    predict: false,
}.adjust();

assert_eq!("{ nb_hash: 3, bit_len: 480833, nb_items: 100000, fp_rate: 0.100000, predict: false }", format!("{}", &params));

Fields

nb_hash: usize

Number of hash functions used by the filter.

Also referred to as k is most Bloom filter papers.

bit_len: usize

Length of the bit vector used by the filter.

Also referred to as m is most Bloom filter papers.

nb_items: usize

Number of items the Bloom filter is designed for.

Also referred to as n is most Bloom filter papers.

fp_rate: f64

False positive rate of the Bloom filter.

Also referred to as p is most Bloom filter papers.

predict: bool

If set to true, Bloom filter is predictable.

Use this for testing, when you want something that is 100% predictable and avoid flaky behavior. In production, it would be safer to rely on the random, statistical default behavior.

One reason is security, among other examples, using a predictable hash for a cache may expose you to some sort of DDOS attack.

If in doubt, leave it to false.

Implementations

impl Params

pub fn with_nb_items(nb_items: usize) -> Params

Parameters to store a given number of items.

All other values are using defaults, or are derive from this. This is the go-to function to create a reasonable filter that holds N items.

Examples:

use ofilter::Params;

let p = Params::with_nb_items(10_000);
assert_eq!("{ nb_hash: 2, bit_len: 189825, nb_items: 10000, fp_rate: 0.010000, predict: false }", format!("{}", p));

pub fn with_nb_items_and_fp_rate(nb_items: usize, fp_rate: f64) -> Params

Parameters to store a given number of items, enforcing false positive rate.

By defining nb_items and fp_rate, the filter is almost completely defined. The other missing parameter is the number of hash functions. There is an optimal number for this, but this function will enforce a default of 2, which most of the time yields excellent results, and avoids calculating too many hashes.

If you want to use the optimal number of hashes, create the Params struct with nb_items, fp_rate and nb_hash defined, then call .adjust().

Examples:

use ofilter::Params;

let p = Params::with_nb_items_and_fp_rate(10_000, 0.001);
assert_eq!("{ nb_hash: 2, bit_len: 622402, nb_items: 10000, fp_rate: 0.001000, predict: false }", format!("{}", p));

pub fn with_bit_len(bit_len: usize) -> Params

Parameters to guess the number of items from bit buffer size.

If the only thing you care about, this will give you the best result for that amount of memory.

Examples:

use ofilter::Params;

let p = Params::with_bit_len(8_192);
assert_eq!("{ nb_hash: 2, bit_len: 8192, nb_items: 432, fp_rate: 0.010019, predict: false }", format!("{}", p));

pub fn with_bit_len_and_nb_items(bit_len: usize, nb_items: usize) -> Params

Parameters to store a given number of items, enforcing bit buffer size

If the only thing you care about, this will give you the best result for that amount of memory.

Examples:

use ofilter::Params;

let p = Params::with_bit_len_and_nb_items(8_192, 1_000);
assert_eq!("{ nb_hash: 2, bit_len: 8192, nb_items: 1000, fp_rate: 0.046925, predict: false }", format!("{}", p));

pub fn estimate_nb_items(nb_hash: usize, bit_len: usize, fp_rate: f64) -> usize

Estimate the number of items one can store.

This applies the formula n = ceil(m / (-k / log(1 - exp(log(p) / k)))).

Examples:

use ofilter::Params;

assert_eq!(1994, Params::estimate_nb_items(5, 10_000, 0.1));

pub fn estimate_fp_rate(nb_hash: usize, bit_len: usize, nb_items: usize) -> f64

Estimate the false positive rate.

This applies the formula p = powf(1 - exp(-k / (m / n)), k)

Examples:

use ofilter::Params;

assert_eq!("0.009431", format!("{:0.6}", Params::estimate_fp_rate(5, 10_000, 1_000)));

pub fn optimal_bit_len(nb_items: usize, fp_rate: f64) -> usize

Calculate the optimal number of bits.

This applies the formula m = ceil((n * log(p)) / log(1 / pow(2, log(2))))

Note that this is the optimal number of bits, but for the case where the number of hash has also been chosen optimally. You’ll notice the formula does not depend on fp_rate (p).

See guess_bit_len_for_fp_rate if you want to also take fp_rate in account.

Examples:

use ofilter::Params;

assert_eq!(62353, Params::optimal_bit_len(10_000, 0.05));

pub fn optimal_nb_hash(bit_len: usize, nb_items: usize) -> usize

Calculate the optimal number of hash.

This applies the formula k = round((m / n) * log(2))

Note that this is the optimal number of hash, but it does not account for false positive rate, which you may want to impose. You’ll notice the formula does not depend on fp_rate (p).

See guess_bit_len_for_fp_rate if you want to also take fp_rate in account.

Examples:

use ofilter::Params;

assert_eq!(13, Params::optimal_nb_hash(10_000, 500));

pub fn guess_bit_len_for_fp_rate( nb_hash: usize, nb_items: usize, fp_rate: f64 ) -> usize

Guess the number of bits for a given false positive rate.

There is a formula m = ceil((n * log(p)) / log(1 / pow(2, log(2)))) to get this result but it gives it for the optimal case. Sometimes you can prefer to, typically, lower the number of bits in the bits buffer to get something smaller in memory, and just give up a bit on the optimal fp_rate (p).

This function does a bisect search to find the correct value.

Examples:

use ofilter::Params;

assert_eq!(480833, Params::guess_bit_len_for_fp_rate(3, 100_000, 0.1));

pub fn guess_nb_hash_for_fp_rate( bit_len: usize, nb_items: usize, fp_rate: f64 ) -> usize

Guess the number of hash for a given false positive rate.

There is a formula k = round((m / n) * log(2)) to get this result but it gives it for the optimal case. Sometimes you can prefer to, typically, lower the number of hash functions to get something faster, and just give up a bit on the optimal fp_rate (p).

This function starts with the optimal nb_hash as a seed, and then tries to lower the it as long as the false positive rate gets closer to the target fp_rate.

Examples:

use ofilter::Params;

assert_eq!(6, Params::guess_nb_hash_for_fp_rate(100_000, 10_000, 0.0005));

pub fn adjust(self) -> Self

Adjust params so that they are consistent.

The 4 parameters in a Bloom filter are closely linked. More precisely, with:

• n (nb_items) -> number of items in the filter
• p (fp_rate) -> probability of false positives, fraction between 0 and 1
• m (bit_len) -> number of bits in the filter
• k (nb_hash) -> number of hash functions

We have:

• n = ceil(m / (-k / log(1 - exp(log(p) / k))))
• p = pow(1 - exp(-k / (m / n)), k)
• m = ceil((n * log(p)) / log(1 / pow(2, log(2))))
• k = round((m / n) * log(2))

This function works as follows:

• if any parameter is non-zero, tries to respect it
• if any parameter is zero, and can be inferred from others, calculate it
• for all other parameters, use defaults

Once everything has a value, it will ultimately re-calculate the fp_rate so that it matches the other 3, which are integers, so may not be changed linearily.

In practice, use it to feed the new_with_params constructors for filters.

Examples:

use ofilter::Params;

let params = Params{
    nb_hash: 2,
    bit_len: 0,
    nb_items: 1_000,
    fp_rate: 0.1,
    predict: false,
};

assert_eq!("{ nb_hash: 2, bit_len: 0, nb_items: 1000, fp_rate: 0.100000, predict: false }",
    format!("{}", params)
);
assert_eq!("{ nb_hash: 2, bit_len: 5262, nb_items: 1000, fp_rate: 0.099980, predict: false }",
    format!("{}", params.adjust())
);

Trait Implementations

impl Clone for Params

fn clone(&self) -> Params

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Params

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

Formats the value using the given formatter.

impl Default for Params

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Params

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Params

Pretty-print parameters

Examples

use ofilter::Params;

let p = Params::with_nb_items(100);
assert_eq!("{ nb_hash: 2, bit_len: 1899, nb_items: 100, fp_rate: 0.009992, predict: false }", format!("{}", p));

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

Formats the value using the given formatter.

impl PartialEq for Params

Compare two parameters sets.

The false positive rate is rounded to 6 digits.

Examples

use ofilter::Params;

let p1 = Params::with_nb_items(100);
let mut p2 = Params::with_nb_items(100);
p2.fp_rate += 1e-8;
assert_eq!(p1, p2);

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for Params

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for Params