Cuckoo-Filter #

Einführung #

Ein Cuckoo-Filter ist eine platzsparende probabilistische Datenstruktur, die prüft, ob ein Element in einer Menge enthalten ist. Falsch-positive Übereinstimmungen sind möglich, aber falsch-negative nicht. Eine Abfrage liefert also entweder “möglicherweise in der Menge” oder “definitiv nicht in der Menge”. Ein Cuckoo-Filter kann auch vorhandene Elemente löschen, was von Bloom-Filtern nicht unterstützt wird. Darüber hinaus können Cuckoo-Filter bei Anwendungen, die viele Elemente speichern und eine mässig niedrige Falsch-Positiv-Rate anstreben, einen geringeren Platzbedarf als platzoptimierte Bloom-Filter aufweisen.

Alternativen sind Counting Bloom Filter, Blocked Bloom Filter, d-left Counting Bloom Filter, Quotient Filter.

Die Beschreibung dieses Filters kommt wenn nicht anders ausgewiesen aus dem Paper Cuckoo Filter: Practically Better Than Bloom

Funktionsweise #

Der Cuckoo Filter ist eine kompakte Variante einer Cuckoo hash table, die nur Fingerprints der Daten, anstelle von Key/Value-Paaren speichert.

Die Grösse des Fingerprints richtet sich nach der Falsch-positive Rate. Je tiefer die Falsch-positive Rate sein soll, desto länger muss der Fingerprint sein.

Cuckoo Hashing #

Es gibt zwei Hashfunktionen und eine Fingerprint Funktion. Beim Einfügen passiert dann folgendes:

1) Berechnung des ersten Index auf das Bucket. Prüfen ob frei, dann einfügen und Ende.
2a) Berechnung des zweiten Index auf das Bucket. Prüfen ob frei, dann einfügen und Ende.
2b) Wenn nicht frei: vorhandenes Element mit neuem Element swappen und versuchen das Ursprüngliche Element in sein anderes Bucket zu platzieren. Wenn beide wieder nicht frei mit nächstem Element bei 1 starten. Wenn das letzte Element nicht platzierbar ist abbrechen, sonst Ende.\

Eine Erweiterung ist, dass ein Bucket mehrere Elemente enthält, die linear verkettet sind.

Cuckoo Filter Insert #

Da das Cuckoo Hashing beim Einfügen eventuell eine Neuberechnung erfordert, müsste das ursprüngliche Element vorhanden sein. Da Platz gespart werden muss, muss die Neuberechnung ausschliesslich auf dem Fingerprint basieren.

Die Hashfunktionen sind:

\( h1(x) = hash(x) \) \( h2(x) = h1(x) \oplus hash(Fingerprint von x) \)

Da der Fingerprint im Filter gespeichert wird, kann der Index des anderen Bucket aus dem Index des aktuellen Buckets ( \(h_1\) oder \(h_2\) ) und dem Fingerprint berechnet werden. Das ist eine Eigenschaft von \(\oplus\) (XOR).

Der Pseudo-Code sieht wie folgt aus:

fingerprint = fingerprint(x);
bucket_index1 = hash(x);
bucket_index2 = bucket_index1 XOR hash(fingerprint);

if bucket[bucket_index1] or bucket[bucket_index2] == empty then
  add fingerprint to this bucket;
  return Done;

// wenn kein Platz dann Relocation
bucket_index = randomly pick bucket_index1 or bucket_index2 ;
for n = 0; n < MaxNumKicks; n++ do
  swap fingerprint von x und fingerprint gespeichert in bucket;
  bucket_index = bucket_index XOR hash(fingerprint);
  if bucket[bucket_index] has an empty entry then
    add fingerprint to bucket[bucket_index];
    return Done;
// Hashtable wird als voll angesehen
return Failure;

Cuckoo Filter Delete #

Das Löschen ist in diesem Filter möglich. Es werden dazu die beiden Indices aus dem Hash und Fingerprint berechnet. Enthält eines der Buckets den Fingerprint, kann er gelöscht werden.

Cuckoo Filter Lookup #

Es werden dazu die beiden Indices aus dem Hash und Fingerprint berechnet. Enthält eines der Buckets den Fingerprint, ist das Element im Filter enthalten.