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.Der Filter wurden 1970 von Burton H. Bloom zur Durchführung einer Rechtschreibkontrolle und zur Silbentrennung 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. Bei Anwendungen, wo diese Fehler in Kauf genommen werden können, sind Bloom-Filter meist gut einsetzbar.
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.
