Bloom-Filter 2.0: der Count-Min Sketch

Der sogenannte Count-Min Sketch weißt eine deutliche Ähnlichkeit zum zählenden Bloom-Filter auf (daher am besten zuvor diesen Post lesen). Es geht darum, abschätzen zu können, wie oft ein bestimmtes Element in einem sehr großen Datenstrom, den wir  aus Platzgründen nicht in einer HashMap speichern können oder wollen, vorgekommen ist.

Folgendes Beispiel soll die Anwendung illustrieren: angenommen, wir haben A, C, D, C, A, B, B, A, B, A, P, P als Datenstrom, dann ergibt eine Zählung der Elemente folgendes Ergebnis: 4 x A, 3 x B, 2 x C, 1 x D und 2 x P. Eine konkrete Anwendung für dieses Szenario wäre z.B. das Zählen der Page-Impressions auf diversen Unterseiten einer großen Webseite.

Noch einmal anders ausgedrückt: wir möchten in einer sehr großen Multimenge zählen, wie oft jedes Mengenelement vorgekommen ist.

Aufbau und Mechanik

Auch der Count-Min Sketch ist eine probablistische Datenstruktur, die auf Hash-Funktionen basiert. Verwenden wir (wie beim Bloom-Filter) d = 2 beliebige Hash-Funktionen für die ASCII-Werte unserer Buchstaben (A = 65, B = 66, C = 67, D = 68, P = 80) im Datenstrom:

h₁ = ASCII-Wert modulo 8

h₂ = (ASCII-Wert - 65) * 2 modulo 8

Anders als beim Bloom-Filter erhält allerdings jede Hash-Funktion ihr eigenes Zähler-Array za₁ und za₂ mit jeweils w Einträgen. Beide werden initial vollständig mit Nullen befüllt:

za₁: 0 0 0 0 0 0 0 0

 za₂: 0 0 0 0 0 0 0 0 

        0 1 2 3 4 5 6 7

Nun berechnen wir die Hash-Werte für unseren Datenstrom:

h₁:               h₂:

A -> 1          A -> 0

B -> 2          B -> 2

C -> 3          C -> 4

D -> 4          D -> 6

 P -> 0           P -> 6

Und aktualisieren za₁ und za₂ der Reihe nach, indem wir an der entsprechenden Stelle eins hinzu addieren z.B. für das erste A:

za₁: 0 1 0 0 0 0 0 0

 za₂: 1 0 0 0 0 0 0 0 

        0 1 2 3 4 5 6 7

Für das erste C:

za₁: 0 1 0 1 0 0 0 0

 za₂: 1 0 0 0 1 0 0 0 

        0 1 2 3 4 5 6 7

Für das D:

za₁: 0 1 0 1 1 0 0 0

 za₂: 1 0 0 0 1 0 1 0 

        0 1 2 3 4 5 6 7

Für das zweite C:

za₁: 0 1 0 2 1 0 0 0

 za₂: 1 0 0 0 2 0 1 0 

        0 1 2 3 4 5 6 7

Und so weiter, bis wir schließlich folgende beiden Arrays erhalten:

za₁: 2 4 3 2 1 0 0 0

 za₂: 4 0 3 0 2 0 3 0 

        0 1 2 3 4 5 6 7

Wir sehen, dass sich dabei durch die Kollision der Hash-Werte von D und P in h2 eine kleine "Verfälschung" (rot markiert) ergibt. Diese ist allerdings insofern (noch) nicht von Bedeutung, als wir bei einer Abfrage immer den kleinsten Wert aus beiden Arrays zurückgeben, also min(za₁, za₂) an dem Index, der durch die jeweilige Hash-Funktion geliefert wird. 

Für A wäre also za₁[1] = 4 und za₂[0] = 4, hier besteht sogar eine Übereinstimmung. Betrachten wir uns D, ergibt sich folgendes Bild: za₁[4] = 1 und za₂[6] = 3, der Eintrag in za₂ wurde durch D verfälscht, wir geben aber den kleinsten der beiden Werte zurück und erhalten als Abschätzung für die Anzahl der Ds korrekterweise eine Eins.

Dieser günstige Umstand wird leider nicht dauerhaft erhalten bleiben, angenommen, als nächstes taucht ein X (ASCII = 88) im Datenstrom auf, hier errechnet h₁ eine 0 und h₂ eine 6, so dass unsere Arrays nun wie folgt belegt wären:

za₁: 3 4 3 2 1 0 0 0

 za₂: 4 0 3 0 2 0 4 0 

        0 1 2 3 4 5 6 7

Nun würde sowohl eine Abfrage für X, als auch eine Abfrage für P ein überschätztes Ergebnis, nämlich jeweils 3 liefern, womit wir die Schwäche des Count-Min-Sketch-Ansatzes aufgedeckt haben.

Eine weitere interessante Eigenschaft des Count-Min Sketchs ist, dass er durch die Verwendung der Hash-Funktionen die gespeicherten Daten anonymisiert. Unter Datenschutzgesichtspunkten lässt sich das durchaus als Vorteil sehen, da es zwar beispielsweise möglich ist, zu prüfen, ob eine gegebene IP-Adresse bereits gespeichert wurde, es kann aber keine Liste von vorhandenen IP-Adressen generiert werden.

Genauigkeit
Durch eine Vergrößerung des Bit-Arrays und eine Erhöhung der Anzahl an Hash-Funktionen lässt sich die Wahrscheinlichkeit für Kollisionen und damit False Positives natürlich verringern. Die Berechnung der Zahl der Hash-Funktionen d und der Anzahl der jeweils benötigten Zähler w ist beispielsweise in [2] erklärt, kurz gesagt müssen 2/w gleich der gewünschten Fehlerwahrscheinlichkeit und (1/2)^d gleich dem gewünschten Konfidenzniveau sein.

Als Beispiel: wir möchten N Elemente per Count-Min Sketch zählen, dabei eine maximale relative Abweichung in der Zählung von 0,1% bei einer 99,5%igen Sicherheit tolerieren; dies erfordert folgende Berechnungen:

w = 2 / 0,001 = 2.000

d = log(0,005) / log(1/2) ~ 8

Somit erhalten wir bei 4 Byte-Integer-Zählern einen Speicherbedarf von w * d * 4 = 64 kByte für das Zählerrarray und z.B. bei N = 100 Millionen eine maximale absolute Zählerabweichung von rund 100.000.

Literaturverweise

1. das Original-Paper (schwer verdaulich)
2. ein leichter verdauliches Paper

Bloom-Filter zur Prüfung von Mengenzugehörigkeit

Beginnen wir mit einem einfachen Beispiel, um den Verwendungszweck von Bloom-Filtern zu umreißen. In großen Datenbeständen ist das Durchsuchen bzw. Überprüfen von Listen auf einen bestimmten Eintrag häufig aufwendig. Nämlich insbesondere dann, wenn der Eintrag gar nicht enthalten ist, da in diesem Fall die komplette Liste durchlaufen werden muss. Könnten wir allerdings vorab mit einer platzsparenden Datenstruktur überprüfen, ob ein Eintrag überhaupt in der Datenbank gespeichert sein kann, ließe sich einiges an Aufwand einsparen. 

Dazu im Folgenden ein kurzes Beispiel zur Illustration der Funktionalität eines Bloom-Filters: nehmen wir an, wir hätten den Datenstrom A, C, D, C, B, A, P, P in einer Datenbank gespeichert und möchten danach überprüfen, ob A, C und X in unserem Speicher enthalten sind. Der Bloom-Filter würde das bei A und C bejahen und bei X verneinen. Für X brauchen wir also keine teuere Suche in der Datenbank zu unternehmen. Der klassische ("Small Data") Lösungsansatz wäre die Verwendung einer Hash-Tabelle, die allerdings deutlich mehr Speicherplatz benötigt, als ein Bloom-Filter.

Da Bloom-Filter zu den probabilistischen Datenstrukturen gehören, arbeiten sie zwar speichersparend und schnell, haben aber leider auch eine Schattenseite: sie können False Positives zurückliefern. Es besteht also die Gefahr, dass ein Bloom-Filter angibt, einen Wert gespeichert zu haben, den er tatsächlich noch nicht zu Gesicht bekommen hat. Immerhin kann niemals der umgekehrte Fall vorkommen: Werte, die der Bloom-Filter gespeichert hat, wird er auch definitiv als bekannt markieren. Sogenannte False Negatives sind also ausgeschlossen.

Zur Mechanik
Schauen wir uns als nächstes die "Mechanik" eines Bloom-Filters genauer an: im Wesentlichen besteht er aus einem hinreichend großen Bit-Array der Länge n und einer Reihe von Hash-Funktionen. Soll dem Filter nun ein Wert hinzugefügt werden, wird dieser von allen Hash-Funktionen verarbeitet und jedes Bit, dessen Index im Bit-Array dem Ergebnis einer Hash-Funktion entspricht, auf eins gesetzt. Das folgende, bewusst einfache Beispiel soll dieses Vorgehen illustrieren:

Wir benötigen ein Bit-Array ba mit beispielsweise n = 8 (0..7) Einträgen, die zu Beginn alle mit Nullen (bzw. mit false) belegt werden:

0 0 0 0 0 0 0 0

0 1 2 3 4 5 6 7

Ferner verwenden wir mehrere bzw. im Beispiel genau zwei Hash-Funktionen hf₁ und hf₂, die idealerweise alle Eingaben e_i auf Werte zwischen 0 und 7 abbilden:

hf₁ = (e_i + 1) * 3 modulo 8
hf₂ = (e_i + 2) * 2  modulo 8

Ferner benötigen wir natürlich einige beispielhafte Eingaben: e₁ = 7 und e₂ = 13 sollten für den Einstieg genügen:

hf₁(7) = 0        hf₁(13) = 2

hf₂(7) = 2        hf₂(13) = 6

In unserem Bit-Array werden entsprechend die Einträge ba[0], ba[2] (zwei Mal!) und ba[6] auf eins gesetzt:

1 0 1 0 0 0 1 0

0 1 2 3 4 5 6 7

Möchten wir nun unseren Bloom-Filter abfragen, wenden wir abermals die Hash-Funktionen an und überprüfen, ob die Einträge bei allen zurückgelieferten Indices auf eins gesetzt sind, also beispielsweise wie folgt für vier und sieben:

hf₁(7) = 0        hf₁(4) = 7

hf₂(7) = 2        hf₂(4) = 6

Für die Sieben sind beide Werte (ba[0] und ba[2]) auf eins gesetzt, weshalb mit hoher Wahrscheinlichkeit davon auszugehen ist, dass eine Sieben bereits im Filter aufgenommen wurde. Obwohl das in unserem Beispiel korrekt ist, könnte sich eine solchen Konstellation auch über Hash-Kollision ergeben haben, was dann zu einem False Positive führen würden. Die Vier wird allerdings auf jeden Fall als unbekannt eingestuft, da hier ist nur der Eintrag ba[6] gesetzt ist. ba[7] steht nach wie vor auf null, so dass noch keine Vier im Filter gespeichert worden sein kann.

Einschränkungen
Leider können derart einfache Bloom-Filter zunächst einmal nur neue Daten aufnehmen, ein Zurücksetzen von Werten auf null ist nicht möglich, da dies das Ergebnis verfälschen würde.

Ferner steigt der "Füllstand" des Filters (also die Anzahl der gesetzen Einsen) immer weiter an, womit gleichzeitig das Risiko für den Erhalt eines False Positives immer weiter ansteigt. Eine offensichtliche Abhilfe für dieses Problem ist es, das Bit-Array mit einer ausreichenden Größe zu initialisieren. Eine brauchbare Orientierung für die Praxis besagt, dass die Anzahl der Hash-Funktionen ca. zwischen drei und acht liegen sollte, während die Anzahl der Bits pro erwartetem Eintrag im Bloom-Filter mindestens sechs betragen sollte, um die Rate der False Positives unter 10% zu halten. Dieser Online-Calculator kann bei der Abschätzung eine gute Hilfe sein.

Erweiterung
Eine naheliegende Erweiterung des Bloom-Filters ist die Verwendung von Zählern (also Zahlen) anstatt von Bits im Array. Das ergibt den sogenannten Counting Bloom Filter, der es ermöglicht abzuschätzen, wie oft ein Element bisher gesehen worden ist. Durch das damit möglich gemachte  Herunterzählen der Zähler im Array erlaubt er sogar das Löschen von Elementen.

Für die Suche nach einem Element in einem zählenden Bloom-Filter muss nur der kleinste Wert in den von den Hash-Funktionen ausgewählten Array-Einträgen gefunden und zurückgegeben werden. Dann wissen wir, wie oft ein Element vermutlich bisher vorgekommen ist. Durch Kollisionen kann es nach wie vor zu Überschätzungen (also False Positives) kommen. Unter der Annahme, dass nur zuvor tatsächlich hinzugefügte Elemente auch gelöscht werden, sind False Negatives (Unterschätzungen) ebenfalls weiterhin nicht möglich.

Ganz ähnlich zu dieser Erweiterung des Bloom-Filters funktioniert übrigens der sogenannte Count-Min Sketch, den ich in diesem Post beschreibe.

Ausprobieren
Um Bloom-Filter schnell und unkompliziert zu testen, bietet sich die Nutzung dieses Tutorials an, dort wird die Nutzung des Bloom-Filters aus der Guava-Library mit wenigen Worten erklärt.