"CuckooFilter" (Data Structure)

"CuckooFilter"

represents a set that tests whether elements are definitely not members.

Details

  • A cuckoo filter is typically used as a probabilistic set that can test if elements are definitely not members.
  • An element can be removed from a cuckoo filter.
  • The same element can be inserted multiple times into a cuckoo filter.
  • Testing an element for membership of a cuckoo filter will always return False if the element is not a member of the set.
  • Testing an element for membership of a cuckoo filter will not always return True if the element is a member of the set.
  • Insertion into a cuckoo filter can fail if there is not space for an element.
  • CreateDataStructure["CuckooFilter",capacity]create a new "CuckooFilter" of specified capacity
    Typed[x,"CuckooFilter"]give x the type "CuckooFilter"
  • For a data structure of type "CuckooFilter", the following operations can be used:
  • ds["Array"]the underlying data in dstime: O(1)
    ds["Capacity"]the storage capacity of dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["CouldContain",x]return True if ds could contain x and False otherwisetime: O(1)
    ds["Delete",x]delete x from ds return True if x might have been an elementtime: O(1)
    ds["FalsePositiveProbability"]the probablility of false positive for membership testingtime: O(1)
    ds["Insert",x]insert x into dstime: O(1)
    ds["Length"]the number of elements stored in dstime: O(1)
    ds["LoadFactor"]the load factor of dstime: O(1)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open allclose all

Basic Examples  (1)

A new "CuckooFilter" can be created with CreateDataStructure:

Any expression can be inserted into a "CuckooFilter" data structure:

It is possible to test if an expression is not present. A result of False means that f[2] is definitely not in the set:

A result of True means that f[1] is possibly in the set:

An element can be removed from the set:

Now the element is definitely not in the set:

Insert an element into the set:

Return an expression version of ds:

A visualization of the data structure can be generated:

Scope  (1)

Information  (1)

A new "CuckooFilter" can be created with CreateDataStructure:

Information about the data structure ds:

Possible Issues  (1)

Insertion into a cuckoo filter can fail if there is not enough space.

Create a cuckoo filter and insert a number of elements. The visualization shows the distribution:

The load factor is useful for showing how much space is available:

Insertion fails here because there is no space for another element with the same hashing properties:

Insertion can work if some elements are deleted: