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.

Inhaltsverzeichnis

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

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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bloom filter — The Bloom filter, conceived by Burton H. Bloom in 1970, is a space efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be… …   Wikipedia

  • Hash-Tabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashmap — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashtable — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Key-to-Address Transform Techniques — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuspeicherverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuwerttabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Bloom — ist der Name mehrerer Personen: Allan Bloom (1930–1992), US amerikanischer Philosoph Arthur Bloom (1942–2006), US amerikanischer Fernsehregisseur Barbara Bloom (* 1951), US amerikanische Künstlerin Barry R. Bloom (* 1937), US amerikanischer… …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”