Struct xorf::BinaryFuse32

pub struct BinaryFuse32 {
    pub fingerprints: Box<[u32]>,
    /* private fields */
}

A BinaryFuse32 filter is an Xor-like filter with 32-bit fingerprints arranged in a binary-partitioned fuse graph. BinaryFuse32s are similar to Fuse32s, but their construction is faster, uses less memory, and is more likely to succeed.

A BinaryFuse32 filter uses ≈36 bits per entry of the set is it constructed from, and has a false positive rate of effectively zero (1/2^32 =~ 1/4 billion). As with other probabilistic filters, a higher number of entries decreases the bits per entry but increases the false positive rate.

A BinaryFuse32 is constructed from a set of 64-bit unsigned integers and is immutable. Construction may fail, but usually only if there are duplicate keys.

use xorf::{Filter, BinaryFuse32};
use core::convert::TryFrom;

const SAMPLE_SIZE: usize = 1_000_000;
let keys: Vec<u64> = (0..SAMPLE_SIZE).map(|_| rng.gen()).collect();
let filter = BinaryFuse32::try_from(&keys).unwrap();

// no false negatives
for key in keys {
    assert!(filter.contains(&key));
}

// bits per entry
let bpe = (filter.len() as f64) * 32.0 / (SAMPLE_SIZE as f64);
assert!(bpe < 36.2, "Bits per entry is {}", bpe);

// false positive rate
let false_positives: usize = (0..SAMPLE_SIZE)
    .map(|_| rng.gen())
    .filter(|n| filter.contains(n))
    .count();
let fp_rate: f64 = (false_positives * 100) as f64 / SAMPLE_SIZE as f64;
assert!(fp_rate < 0.0000000000000001, "False positive rate is {}", fp_rate);

Serializing and deserializing BinaryFuse32 filters can be enabled with the serde feature (or [bincode] for bincode).

Fields

fingerprints: Box<[u32]>

The fingerprints for the filter

Implementations

impl BinaryFuse32

pub fn try_from_iterator<T>(keys: T) -> Result<Self, &'static str>

where T: ExactSizeIterator<Item = u64> + Clone,

Try to construct the filter from a key iterator. Can be used directly if you don’t have a contiguous array of u64 keys.

Note: the iterator will be iterated over multiple times while building the filter. If using a hash function to map the key, it may be cheaper just to create a scratch array of hashed keys that you pass in.

Trait Implementations

impl Clone for BinaryFuse32

fn clone(&self) -> BinaryFuse32

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BinaryFuse32

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

Formats the value using the given formatter.

impl Filter<u64> for BinaryFuse32

fn contains(&self, key: &u64) -> bool

Returns true if the filter contains the specified key. Has a false positive rate of <0.4%. Has no false negatives.

fn len(&self) -> usize

Returns the number of fingerprints in the filter.

impl TryFrom<&[u64]> for BinaryFuse32

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(keys: &[u64]) -> Result<Self, Self::Error>

Performs the conversion.

impl TryFrom<&Vec<u64>> for BinaryFuse32

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(v: &Vec<u64>) -> Result<Self, Self::Error>

Performs the conversion.

impl TryFrom<Vec<u64>> for BinaryFuse32

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(v: Vec<u64>) -> Result<Self, Self::Error>

Performs the conversion.