# "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 ds time: O(1) ds["Capacity"] the storage capacity of ds time: O(1) ds["Copy"] return a copy of ds time: O(n) ds["CouldContain",x] return True if ds could contain x and False otherwise time: O(1) ds["Delete",x] delete x from ds return True if x might have been an element time: O(1) ds["FalsePositiveProbability"] the probablility of false positive for membership testing time: O(1) ds["Insert",x] insert x into ds time: O(1) ds["Length"] the number of elements stored in ds time: O(1) ds["LoadFactor"] the load factor of ds time: O(1) ds["Visualization"] return a visualization of ds time: O(n)
• The following functions are also supported:
•  dsi===dsj True, 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: