Ein Bloom-Filter 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.
Funktionsprinzip
Ein Bloomfilter besteht aus einem m-stelligen Bit -Array (welches zu Beginn mit Nullen gefüllt ist) und aus k unterschiedlichen Hashfunktionen mit einem Wertebereich von 0 bis m-1. Hierbei ist vor allem wichtig, dass die von den Hashfunktionen gelieferten Werte gleichverteilt sind, kryptografische Eigenschaften sind nicht gefordert. Aus diesem Grund werden häufig einfache und sehr schnelle Hashverfahren (z.
Copyright 2024 puzzlefactory.com Alle Rechte vorbehalten.
