Bloom-Filter sind probabilistische Datenstrukturen, die verwendet werden, um zu testen, ob ein Element ein Mitglied eines Satzes ist.Sie sind platz- und geschwindigkeitsmäßig effizient und eignen sich daher für Anwendungen, bei denen schnelle Mitgliedschaftsabfragen mit einigen akzeptablen falschen Positiven erforderlich sind.

Wie Bloom Filter funktionieren

Ein Bloom-Filter verwendet ein Bit-Array und mehrere Hash-Funktionen. Wenn ein Element hinzugefügt wird, ordnet jede Hash-Funktion es einer Position im Array zu, wobei diese Bits auf 1 gesetzt werden. Um zu überprüfen, ob ein Element existiert, werden die gleichen Hash-Funktionen angewendet und die entsprechenden Bits untersucht. Wenn alle auf 1 gesetzt sind, ist das Element wahrscheinlich im Satz; wenn irgendwelche 0 sind, ist es definitiv nicht.

Berechnungen für Bloom Filter

Die falsch positive Wahrscheinlichkeit hängt von der Größe des Bitfeldes (m), der Anzahl der eingefügten Elemente (n) und der Anzahl der Hash-Funktionen (k) ab. Die Wahrscheinlichkeit (p) eines falsch positiven Ergebnisses kann durch folgende Näherungswerte ermittelt werden:

p ≈ (1 - e-kn/m)k

Optimale Werte für k und m können falsche Positive für ein gegebenes n minimieren. Typischerweise wird k wie folgt gewählt:

k = (m/n) * ln 2

Anwendungsfälle von Bloom Filtern

Bloom-Filter werden in verschiedenen Bereichen verwendet, darunter:

  • Datenbanksysteme für schnelles Mitgliedschaftstesten
  • Web-Caching zur Reduzierung von Disk Lookups
  • Verteilte Systeme zur Datensynchronisation
  • Netzwerksicherheit für Spam-Filterung

Einschränkungen von Bloom Filtern

Bloom-Filter sind zwar effizient, aber sie können falsche Positive erzeugen, aber keine falschen Negative. Sobald Bits auf 1 gesetzt sind, können sie nicht zurückgesetzt werden, was zu Ungenauigkeiten im Laufe der Zeit führen kann. Sie sind auch nicht geeignet, einzelne Elemente ohne zusätzliche Datenstrukturen zu löschen.