Bloomfilter

Ein Bloom-Filter (benannt nach Burton Howard Bloom) ist eine probabilistische Datenstruktur, mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem 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 einzeiligen Hashtabelle hinterlassen.

1970 von Burton H. Bloom zur Rechtschreibkontrolle und zur Worttrennung am Zeilenende entwickelt, werden Bloomfilter heute oft bei der Datenbankverwaltung und für das Routing in Netzwerken eingesetzt. Im Gegensatz zu vergleichbaren Algorithmen brauchen Bloom-Filter nur sehr wenig Speicherplatz. Für die Anwendbarkeit sind aber auch die folgenden Eigenheiten von entscheidender Bedeutung: Schlüsselwerte, die einmal in der Hashtabelle erfasst wurden, verbleiben dort. Weiterhin sind falsch positive Ergebnisse möglich, d. h., was der Filter akzeptiert, war mit hoher Wahrscheinlichkeit in den Schlüsselwerten enthalten; hingegen war definitiv nicht enthalten, was er abweist.