Cuckoo

v1.0.2

Cuckoo v1.0.2 Cuckoo View Source

This module implements a Cuckoo Filter.

Implementation Details

The implementation follows the specification as per the paper above.

For hashing we use the x64_128 variant of Murmur3 and the Erlang phash2.

Examples 

iex> cf = Cuckoo.new(1000, 16, 4)
%Cuckoo.Filter{...}

iex> {:ok, cf} = Cuckoo.insert(cf, 5)
%Cuckoo.Filter{...}

iex> Cuckoo.contains?(cf, 5)
true

iex> {:ok, cf} = Cuckoo.delete(cf, 5)
%Cuckoo.Filter{...}

iex> Cuckoo.contains?(cf, 5)
false

Link to this section Summary

Types

t()

Functions

contains?(cuckoo, element)

Checks if the Cuckoo Filter contains element

delete(filter, element)

Attempts to delete element from the Cuckoo Filter if it contains it

delete!(filter, element)

Returns a filter with the removed element or raises Cuckoo.Error if an error occurs

insert(filter, element)

Tries to insert element into the Cuckoo Filter

insert!(filter, element)

Returns a filter with the inserted element or raises Cuckoo.Error if an error occurs

new(max_num_keys, fingerprint_size, fingerprints_per_bucket \\ 4)

Creates a new Cuckoo Filter using the given max_num_keys, fingerprint_size and fingerprints_per_bucket

Link to this section Types

Link to this type t() View Source 
t() :: %Cuckoo{
  buckets: :array.array(),
  fingerprint_size: pos_integer(),
  fingerprints_per_bucket: pos_integer(),
  max_num_keys: pos_integer()
}

Link to this section Functions

Link to this function contains?(cuckoo, element) View Source 
contains?(Cuckoo.t(), any()) :: boolean()

Checks if the Cuckoo Filter contains element.

Returns true if does, otherwise returns false.

Link to this function delete(filter, element) View Source 
delete(Cuckoo.t(), any()) :: {:ok, Cuckoo.t()} | {:error, :inexistent}

Attempts to delete element from the Cuckoo Filter if it contains it.

Returns {:error, :inexistent} if the element doesn’t exist in the filter, otherwise returns {:ok, filter}.

Link to this function delete!(filter, element) View Source 
delete!(Cuckoo.t(), any()) :: Cuckoo.t() | no_return()

Returns a filter with the removed element or raises Cuckoo.Error if an error occurs.

Link to this function insert(filter, element) View Source 
insert(Cuckoo.t(), any()) :: {:ok, Cuckoo.t()} | {:error, :full}

Tries to insert element into the Cuckoo Filter.

Returns {:ok, filter} if successful, otherwise returns {:error, :full} from which you should consider the Filter to be full.

Link to this function insert!(filter, element) View Source 
insert!(Cuckoo.t(), any()) :: Cuckoo.t() | no_return()

Returns a filter with the inserted element or raises Cuckoo.Error if an error occurs.

Link to this function new(max_num_keys, fingerprint_size, fingerprints_per_bucket \\ 4) View Source 
new(pos_integer(), pos_integer(), pos_integer()) :: Cuckoo.t()

Creates a new Cuckoo Filter using the given max_num_keys, fingerprint_size and fingerprints_per_bucket.

The suggested values for the last two according to one of the publications should be 16 and 4 respectively, as it allows the Cuckoo Filter to achieve a sweet spot in space effiency and table occupancy.