Options
All
  • Public
  • Public/Protected
  • All
Menu

Class BloomFilter

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

Reference: Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.

see

http://crystal.uta.edu/~mcguigan/cse6350/papers/Bloom.pdf for more details about classic Bloom Filters.

author

Thomas Minier

author

Arnaud Grall

Hierarchy

Implements

Index

Properties

Methods

Constructors

Accessors

Properties

_filter

_filter: BitSet

_hashing

_hashing: Hashing

_nbHashes

_nbHashes: number

_rng

_rng: PRNG

_seed

_seed: number

_size

_size: number

Methods

add

Static create

  • create(nbItems: number, errorRate: number): BloomFilter

  • Create an optimal bloom filter providing the maximum of elements stored and the error rate desired

    Parameters

    • nbItems: number

      The maximum number of item to store

    • errorRate: number

      The error rate desired for a maximum of items inserted

    Returns BloomFilter

equals

  • Check if another Bloom Filter is equal to this one

    Parameters

    Returns boolean

    True if they are equal, false otherwise

Static from

  • Build a new 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 = BloomFilter.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, targeted by the filter

    • Optional seed: number

      The random number seed (optional)

    Returns BloomFilter

    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 BloomFilter(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

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

    example
    const filter = new BloomFilter(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

Constructors

constructor

  • new BloomFilter(size: number, nbHashes: number): BloomFilter

Accessors

length

  • get length(): 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

Generated using TypeDoc