Options
All
  • Public
  • Public/Protected
  • All
Menu

Class CuckooFilter

Cuckoo filters improve on Bloom filters by supporting deletion, limited counting, and bounded False positive rate with similar storage efficiency as a standard Bloom filter.

Reference: Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014, December). Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies (pp. 75-88). ACM.

see

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf for more details about Cuckoo filters

author

Thomas Minier & Arnaud Grall

Hierarchy

Implements

Index

Properties

Methods

Accessors

Constructors

Properties

_bucketSize

_bucketSize: number

_filter

_filter: <internal>.default<string>[]

_fingerprintLength

_fingerprintLength: number

_hashing

_hashing: Hashing

_length

_length: number

_maxKicks

_maxKicks: number

_rng

_rng: PRNG

_seed

_seed: number

_size

_size: number

Methods

_computeHashTableLoad

  • _computeHashTableLoad(): { free: number; load: number; size: number; used: number }

  • Return the load of this filter

    Returns { free: number; load: number; size: number; used: number }

    load: is the load, size is the number of entries, free is the free number of entries, used is the number of entry used

    • free: number
    • load: number
    • size: number
    • used: number

Private _locations

  • For a element, compute its fingerprint and the index of its two buckets

    Parameters

    Returns { fingerprint: string; firstIndex: number; secondIndex: number }

    The fingerprint of the element and the index of its two buckets

    • fingerprint: string
    • firstIndex: number
    • secondIndex: number

add

  • Add an element to the filter, if false is returned, it means that the filter is considered as full.

    example
    const filter = new CuckooFilter(15, 3, 2);
    filter.add('alice');
    filter.add('bob');

    Parameters

    Returns boolean

    True if the insertion is a success, False if the filter is full

Static create

  • create(size: number, errorRate: number, bucketSize?: number, maxKicks?: number): CuckooFilter

  • Return a new optimal CuckooFilter given the number of maximum elements to store and the error rate desired

    Parameters

    • size: number

      The number of items to store

    • errorRate: number

      The desired error rate

    • bucketSize: number = 4

      The number of buckets desired per cell

    • maxKicks: number = 500

      The number of kicks done when a collision occurs

    Returns CuckooFilter

    A Cuckoo Filter optimal for these parameters

equals

  • Check if another Cuckoo filter is equal to this one

    Parameters

    • filter: CuckooFilter

      The cuckoo filter to compare to this one

    Returns boolean

    True if they are equal, false otherwise

Static from

  • Build a new optimal CuckooFilter from an iterable with a fixed error rate

    Parameters

    • items: Iterable<<internal>.HashableInput>

      Iterable used to populate the filter

    • errorRate: number

      The error rate of the filter

    • bucketSize: number = 4

      The number of buckets desired per cell

    • maxKicks: number = 500

      The number of kicks done when a collision occurs

    Returns CuckooFilter

    A new Cuckoo 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 CuckooFilter(15, 3, 2);
    filter.add('alice');

    console.log(filter.has('alice')); // output: true
    console.log(filter.has('bob')); // 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

remove

  • Remove an element from the filter

    example
    const filter = new CuckooFilter(15, 3, 2);
    filter.add('alice');
    filter.add('bob');

    // remove an element
    filter.remove('bob');

    Parameters

    Returns boolean

    True if the element has been removed from the filter, False if it wasn't in the filter

saveAsJSON

  • saveAsJSON(): any

Accessors

bucketSize

  • get bucketSize(): number

fingerprintLength

  • get fingerprintLength(): number

fullSize

  • get fullSize(): number

length

  • get length(): number

maxKicks

  • get maxKicks(): 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 CuckooFilter(size: number, fLength: number, bucketSize: number, maxKicks?: number): CuckooFilter

  • Constructor

    Parameters

    • size: number

      The filter size

    • fLength: number

      The length of the fingerprints

    • bucketSize: number

      The size of the buckets in the filter

    • maxKicks: number = 500

      (optional) The max number of kicks when resolving collision at insertion, default to 1

    Returns CuckooFilter

Generated using TypeDoc