Bloom-filter

Bloom-filter

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 100 prozentige Wahrscheinlichkeit 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. log2(1 / ε) pro eingefügtem Wert, wenn ε 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 umso mehr 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 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 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, Communications of the ACM, Volume 13, Issue 7, July 1970.
  • Communications of the ACM - en.

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

  • Bloom — The term bloom usually refers to the general expression describing the aesthetic experience of one or more flowers on a flowering plant. Also used as a metaphor for young people at the peak of their beauty or health. See also Blossom.Bloom or… …   Wikipedia

  • Filtre De Bloom — Le filtre de Bloom, conçu par Burton H. Bloom en 1970, est une structure de données probabiliste qui optimise l espace utilisé. Cette structure est utilisée pour tester si un élément fait partie d un ensemble. Il permet notamment d optimiser les… …   Wikipédia en Français

  • Filtre de bloom — Le filtre de Bloom, conçu par Burton H. Bloom en 1970, est une structure de données probabiliste qui optimise l espace utilisé. Cette structure est utilisée pour tester si un élément fait partie d un ensemble. Il permet notamment d optimiser les… …   Wikipédia en Français

  • Atomic line filter — A potassium Faraday filter designed, built and photographed by Jonas Hedin for making daytime LIDAR measurements at Arecibo Observatory.[1] An atomic line filter (ALF) is an advanced optical band pass filter used in the physical sciences for… …   Wikipedia

  • Algal bloom — Algal blooms can present problems for ecosystems and human society An algal bloom is a rapid increase or accumulation in the population of algae (typically microscopic) in an aquatic system. Algal blooms may occur in freshwater as well as marine… …   Wikipedia

  • Hash filter — A hash filter creates a hash sum from data, typically e mail, and compares the sum against other previously defined sums. Depending on the purpose of the filter, the data can then be included or excluded in a function based on whether it matches… …   Wikipedia

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

  • Bit array — A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). It implements a simple set data structure storing a subset of {1,2,..., n } and is effective at exploiting bit level… …   Wikipedia

  • Cuckoo hashing — example. The arrows show the alternative location of each key. A new item would be inserted in the location of A by moving A to its alternative location, currently occupied by B, and moving B to its alternative location which is currently vacant …   Wikipedia

Share the article and excerpts

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