Bloom-Filter und probabilistische Datenstrukturen

Kurz: Ein Bloom-Filter prüft platzsparend, ob ein Element vielleicht in einer Menge ist. Er sagt entweder „sicher nicht“ oder „wahrscheinlich ja“, nie fälschlich „nein“.

Genauer: Der Filter ist ein Bit-Array mit mehreren Hash-Funktionen. Beim Einfügen werden k Bits gesetzt, beim Prüfen müssen alle k Bits gesetzt sein. Falsch-Positive sind möglich, Falsch-Negative nicht. Löschen geht nicht (außer bei Counting-Varianten).

Im Detail

• Platz: Etwa 10 Bits pro Element bei ca. 1 % Fehlerrate.
• Einsatz: Datenbanken (LSM-Trees sparen Plattenzugriffe), Caches, Browser (schädliche URLs), Crawler.
• HyperLogLog: Schätzt die Anzahl verschiedener Elemente mit wenigen KB.
• Count-Min-Sketch: Schätzt Häufigkeiten.
• Abwägung: Speicher und Geschwindigkeit gegen Genauigkeit.

Siehe auch: LSM-Tree und Sorted String Tables, Caching-Strategien und Cache-Invalidierung