Options
All
  • Public
  • Public/Protected
  • All
Menu

Class PartitionedBloomFilter

A Partitioned Bloom Filter is a variation of a classic Bloom filter.

This filter works by partitioning the M-sized bit array into k slices of size m = M/k bits, k = nb of hash functions in the filter. Each hash function produces an index over m for its respective slice. Thus, each element is described by exactly k bits, meaning the distribution of false positives is uniform across all elements.

Be careful, as a Partitioned Bloom Filter have much higher collison risks that a classic Bloom Filter on small sets of data.

Reference: Chang, F., Feng, W. C., & Li, K. (2004, March). Approximate caches for packet classification. In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (Vol. 4, pp. 2196-2207). IEEE.

see

https://pdfs.semanticscholar.org/0e18/e24b37a1f4196fddf8c9ff8e4368b74cfd88.pdf for more details about Partitioned Bloom Filters

author

Thomas Minier & Arnaud Grall

Hierarchy

Implements

Index

Properties

Methods

Accessors

Constructors

Properties

_capacity

_capacity: number

_filter

_filter: BitSet[]

_hashing

_hashing: Hashing

_loadFactor

_loadFactor: number

_m

_m: number

_nbHashes

_nbHashes: number

_rng

_rng: PRNG

_seed

_seed: number

_size

_size: number

Methods

_currentload

  • _currentload(): number

add

Static create

  • Return a PartitionedBloomFilter for a given number of elements and under a given error rate

    Parameters

    • size: number

      The max allowable number of items to insert

    • errorRate: number

      The desired error rate

    • loadFactor: number = 0.5

    Returns PartitionedBloomFilter

    A new PartitionedBloomFilter optimal for the given parameters

equals

Static from

  • Build a new Partitioned Bloom Filter from an existing iterable with a fixed error rate

    example
    // create a filter with a false positive rate of 0.1
    const filter = PartitionedBloomFilter.from(['alice', 'bob', 'carl'], 0.1);

    Parameters

    • items: Iterable<<internal>.HashableInput>

      The iterable used to populate the filter

    • errorRate: number

      The error rate, i.e. 'false positive' rate, targetted by the filter

    • loadFactor: number = 0.5

      The filter's load factor

    Returns PartitionedBloomFilter

    A new Bloom Filter filled with the iterable's elements

Static fromJSON

  • fromJSON(json: JSON): any

  • Load an Object from a provided JSON object

    Parameters

    • json: JSON

      the JSON object to load

    Returns any

    Return the Object loaded from the provided JSON object

has

  • Test an element for membership

    example
    const filter = new PartitionedBloomFilter(15, 0.1);
    filter.add('foo');
    console.log(filter.has('foo')); // output: true
    console.log(filter.has('bar')); // output: false

    Parameters

    Returns boolean

    False if the element is definitively not in the filter, True is the element might be in the filter

nextInt32

  • nextInt32(): number

rate

  • rate(): number

  • Compute the current false positive rate (or error rate) of the filter

    example
    const filter = PartitionedBloomFilter.create(15, 0.1);
    console.log(filter.rate()); // output: something around 0.1

    Returns number

    The current false positive rate of the filter

saveAsJSON

  • saveAsJSON(): any

Accessors

capacity

  • get capacity(): number

loadFactor

  • get loadFactor(): number

random

  • Get a function used to draw random number

    Returns PRNG

    A factory function used to draw random integer

seed

  • get seed(): number
  • set seed(seed: number): void

  • Get the seed used in this structure

    Returns number

  • Set the seed for this structure

    Parameters

    • seed: number

      the new seed that will be used in this structure

    Returns void

size

  • get size(): number

Constructors

constructor

  • new PartitionedBloomFilter(size: number, nbHashes: number, loadFactor: number, capacity?: number): PartitionedBloomFilter

Generated using TypeDoc