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:
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 hf1 und hf2, die idealerweise alle Eingaben ei auf Werte zwischen 0 und 7 abbilden:
hf1 = (ei + 1) * 3 modulo 8
hf2 = (ei + 2) * 2 modulo 8
hf2 = (ei + 2) * 2 modulo 8
Ferner benötigen wir natürlich einige beispielhafte Eingaben: e1 = 7 und e2 = 13 sollten für den Einstieg genügen:
hf1(7) = 0 hf1(13) = 2
hf2(7) = 2 hf2(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:
hf1(7) = 0 hf1(4) = 7
hf2(7) = 2 hf2(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.
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.
Keine Kommentare:
Kommentar veröffentlichen