Options
All
  • Public
  • Public/Protected
  • All
Menu

Class CountingBloomFilter

A Counting Bloom filter works in a similar manner as a regular Bloom filter; however, it is able to keep track of insertions and deletions. In a counting Bloom filter, each entry in the Bloom filter is a small counter associated with a basic Bloom filter bit.

Reference: F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, “An Improved Construction for Counting Bloom Filters,” in 14th Annual European Symposium on Algorithms, LNCS 4168, 2006, pp. 684–695.

author

Thomas Minier & Arnaud Grall

Hierarchy

Implements

Index

Properties

Methods

Constructors

Accessors

Properties

_filter

_filter: number[][]

_hashing

_hashing: Hashing

_length

_length: number

_nbHashes

_nbHashes: number

_rng

_rng: prng

_seed

_seed: number

_size

_size: number

Methods

add

Static create

equals

Static from

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

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

    Parameters

    Returns CountingBloomFilter

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

remove

saveAsJSON

  • saveAsJSON(): any

Constructors

constructor

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