Bloomfilter

Bloom-Filter sind probabilistische Datenstrukturen, mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem kontinuierlich fließenden Datenstrom schon einmal vorgekommen sind und welche erstmals auftreten. Hierzu wird mit einer geeigneten Zahl von Hash-Funktionen ein „Fingerabdruck“ des gelesenen Datensatzes in einer Hashtabelle hinterlassen.

Die Filter wurden 1970 von Burton H. Bloom zur Durchführung einer Rechtschreibkontrolle und zur Worttrennung am Zeilenende entwickelt. Heute werden sie oft bei der Datenbankverwaltung und für das Routing in Netzwerken eingesetzt. Im Gegensatz zu vergleichbaren Algorithmen brauchen Bloom-Filter nur sehr wenig Speicherplatz. Nachteile sind hingegen, dass einmal in die Hashtabelle eingefügte Schlüsselwerte nicht mehr entfernt werden können und dass keine hundertprozentige Sicherheit für die Richtigkeit des Ergebnisses vorliegt. Was der Filter abweist, war definitiv nicht in den Schlüsselwerten enthalten, was er akzeptiert, war mit hoher Wahrscheinlichkeit enthalten. Bei Anwendungen, wo diese Fehler in Kauf genommen werden können, sind Bloom-Filter meist gut einsetzbar.

Funktionsprinzip

Der Filter lernt zunächst sein Vokabular. Hierzu wird mittels einer Hash-Funktion für jeden vorkommenden Wert (beispielsweise für jedes richtig geschriebene deutsche Wort) ein Hash-Wert ermittelt, beispielsweise als Binärzahl. Diese Zahl muss umso länger sein, je größer das Vokabular ist, damit sich die Hash-Werte in aller Regel auch voneinander unterscheiden.

Die Hash-Werte werden nun nacheinander in ein zunächst mit Nullen gefülltes Bit-Array geschrieben, das dieselbe Länge hat, wie jeder Wert. Dort, wo ein Hash-Wert eine 1 enthält, wird eine 1 in das Array geschrieben, bei einer 0 bleibt der bisherige Wert erhalten. Es handelt sich also um eine binäre Oder-Funktion. Damit nicht sehr bald im Array nur noch Einsen stehen, sollte die Hash-Funktion Werte liefern, die überwiegend Nullen enthalten.

Ein Hash-Wert kann nicht mehr gelöscht werden, weil im Nachhinein nicht mehr bekannt ist, ob eine 1 an einer bestimmten Stelle im Array womöglich in mehreren Hash-Werten aufgetaucht ist.

Soll nun überprüft werden, ob ein beliebiges Wort im Vokabular enthalten ist, wird auch dessen Hash-Wert ermittelt. Hat er irgendwo eine Eins, wo im Array eine Null steht, kann das Wort nicht enthalten sein. Ist dies aber nicht der Fall, muss das Wort dennoch nicht zwingend im Vokabular enthalten sein, denn das übereinstimmende Bitmuster kann durch die Überlappung mehrerer anderer Hash-Werte zustande kommen, oder auch dadurch, dass zwei Wörter den gleichen Hash-Wert haben.

Dieses Risiko wird kleiner mit steigender Länge der Hash-Werte und nicht zu kleinem Anteil an Nullen im Array. Es verschwindet, wenn sichergestellt wird, dass sich die Bitmuster überhaupt nicht überlappen. Hierfür würde aber pro denkbarem Wort ein Bit Arraylänge benötigt. Gute und brauchbare Lösungen kommen mit deutlich weniger Platz aus.

Theoretisch beläuft sich der Platzbedarf auf ca. $\log_2(1/\epsilon)$ pro eingefügtem Wert, wenn $\epsilon$ die Falschpositiv-Rate ist. Bei 10.000 Werten mit einer Falschpositiv-Rate von 0,01 errechnen sich 66439 Bit (ca. 8,1 KB) für ein komplettes Vokabular. 10.000 Wörter mit durchschnittlich 8 Buchstaben brauchen im Klartext dagegen 78 KB.

Die Zusammenführung der Einzelwerte macht es unmöglich, aus dem Array eine Reihe von Originalwörtern zurückzugewinnen, es kann nur mit einer gewissen (ggf. hohen) Wahrscheinlichkeit ermittelt werden, ob ein vorgegebenes Wort enthalten ist oder nicht. Ein scheinbarer Nachteil, der jedoch von Nutzen sein kann, wo es um sensible Daten geht. Das Verfahren kann beispielsweise verwendet werden, um bei einer Fahndung sicher auszuschließen, dass eine gerade überprüfte Person gesucht wird, ohne dabei Personendaten im Klartext vorhalten zu müssen. Das gilt zum Beispiel auch beim Einsatz von Biometrie.

Beispiel

Das Vokabular bestehe aus den Wörtern

• „der“ (fiktiver Hashwert 001),
• „die“ (Hashwert 101) und
• „das“ (Hashwert 100).

Die angenommene Hashfunktion ist rein fiktiv für dieses Beispiel konstruiert, könnte aber so real existieren.

Das Array enthält nach dem Lernvorgang den Wert (001 OR 101 OR 100) = 101. Nun wird die Existenz verschiedener Wörter überprüft.

• Das Wort „wer“ (Hashwert 011) wird korrekterweise nicht akzeptiert, denn das zweite Bit ist im Array nicht gesetzt, nur das dritte.
• Das Wort „das“ (Hashwert 100) wird korrekterweise akzeptiert, denn das erste Bit ist auch im Array gesetzt.
• Das Wort „sie“ (Hashwert 000) wird hier fälschlicherweise akzeptiert, denn der Hashwert hat keine 1, wo das Array eine 0 hat. Daher handelt es sich um eine falsch-positive Entscheidung.

Man sieht also, dass mit Hilfe von nur drei Bits das Vorhandensein bzw. Nichtvorhandensein einer deutlich größeren Menge an Wörtern (nämlich 5 Stück oder auch deutlich mehr) überprüft werden kann – und dass hierfür jedoch in Kauf genommen werden muss, dass eventuell manche Wörter unzutreffenderweise als vorhanden markiert werden.

Es sollte bedacht werden, dass dieses ein bewusst konstruiertes Extrembeispiel darstellt, welches noch keine Schlüsse auf die Qualität des Verfahrens erlaubt.

Anwendungen

• Der Squid Web Proxy Cache verwendet Bloomfilter für die sogenannten cache digests.

Literatur

• Burton H. Bloom: Space/time trade-offs in hash coding with allowable errors. In: Communications of the ACM. 13, Nr. 7, Juli 1970, ISSN 0001-0782, S. 422-426 (pdf).

Weblinks

• Libhashish – umfangreiche Bloom-Filter-Bibliothek mit Analysefunktionalität