Bloom-Filter - Bloom filter

Ein Bloom-Filter ist eine platzsparende probabilistische Datenstruktur , die 1970 von Burton Howard Bloom konzipiert wurde und verwendet wird, um zu testen, ob ein Element ein Mitglied einer Menge ist . Falsch positive Übereinstimmungen sind möglich, falsch negative jedoch nicht – mit anderen Worten, eine Abfrage liefert entweder "möglicherweise in Menge" oder "definitiv nicht in Menge". Elemente können dem Set hinzugefügt, aber nicht entfernt werden (obwohl dies mit der zählenden Bloom-Filtervariante behoben werden kann); je mehr Elemente hinzugefügt werden, desto größer ist die Wahrscheinlichkeit falsch positiver Ergebnisse.

Bloom schlug die Technik für Anwendungen vor, bei denen die Menge der Quelldaten unpraktisch viel Speicher erfordern würde, wenn "herkömmliche" fehlerfreie Hashing- Techniken angewendet würden. Er nannte als Beispiel einen Silbentrennungsalgorithmus für ein Wörterbuch mit 500.000 Wörtern, von denen 90 % einfachen Silbentrennungsregeln folgen, aber die restlichen 10 % erfordern teure Plattenzugriffe, um bestimmte Silbentrennungsmuster abzurufen. Bei ausreichendem Kernspeicher könnte ein fehlerfreier Hash verwendet werden, um alle unnötigen Plattenzugriffe zu eliminieren; Andererseits verwendet Blooms Technik bei begrenztem Kernspeicher einen kleineren Hash-Bereich, eliminiert aber dennoch die meisten unnötigen Zugriffe. Beispielsweise eliminiert ein Hash-Bereich von nur 15 % der Größe, die ein idealer fehlerfreier Hash benötigt, immer noch 85 % der Plattenzugriffe.

Allgemeiner sind weniger als 10 Bits pro Element für eine 1%ige Falsch-Positiv-Wahrscheinlichkeit erforderlich, unabhängig von der Größe oder Anzahl der Elemente in der Menge.

Beschreibung des Algorithmus

Ein Beispiel für einen Bloom-Filter, der die Menge { x , y , z } repräsentiert . Die farbigen Pfeile zeigen die Positionen im Bit-Array, denen jedes Satzelement zugeordnet ist. Das Element w ist nicht in der Menge { x , y , z } , da es auf eine Bit-Array-Position mit 0 hasht. Für diese Figur gilt m  = 18 und k = 3 .

Ein leerer Bloom-Filter ist ein Bit-Array von m Bits, die alle auf 0 gesetzt sind. Es müssen auch k verschiedene Hash-Funktionen definiert werden, von denen jede ein Set-Element auf eine der m Array-Positionen abbildet oder hasht , wodurch eine gleichmäßige Zufallsverteilung erzeugt wird. Typischerweise k ist eine kleine Konstante , die von dem gewünschten Falschfehlerrate hängt ε , während m proportional ist zu k und die Anzahl von Elementen hinzugefügt werden.

Um ein Element hinzuzufügen , führen Sie es in jede der k Hashfunktionen ein, um k Arraypositionen zu erhalten. Setzen Sie die Bits an allen diesen Positionen auf 1.

Um ein Element abzufragen (zu testen, ob es in der Menge enthalten ist), geben Sie es an jede der k Hash-Funktionen ein, um k Array-Positionen zu erhalten. Wenn irgendwelche der Bits an diesen Positionen gleich 0 ist, ist das Element auf jeden Fall nicht in der Gruppe; wäre dies der Fall, wären beim Einfügen alle Bits auf 1 gesetzt worden. Wenn alle 1 sind, ist entweder das Element in der Menge, oder die Bits wurden beim Einfügen anderer Elemente zufällig auf 1 gesetzt, was zu einem falsch positiven Ergebnis führt . In einem einfachen Bloom-Filter gibt es keine Möglichkeit, zwischen den beiden Fällen zu unterscheiden, aber fortgeschrittenere Techniken können dieses Problem beheben.

Die Anforderung, k verschiedene unabhängige Hash-Funktionen zu entwerfen, kann für große k unerschwinglich sein . Für eine gute Hash-Funktion mit einer breiten Ausgabe sollte es, wenn überhaupt, nur eine geringe Korrelation zwischen verschiedenen Bitfeldern eines solchen Hashs geben Felder. Alternativ kann man k verschiedene Anfangswerte (wie 0, 1, ..., k  − 1) an eine Hash-Funktion übergeben, die einen Anfangswert annimmt; oder fügen Sie diese Werte dem Schlüssel hinzu (oder hängen Sie sie an). Für größere m und/oder k kann die Unabhängigkeit zwischen den Hash-Funktionen mit einem vernachlässigbaren Anstieg der Falsch-Positiv-Rate gelockert werden. (Insbesondere zeigen Dillinger & Manolios (2004b) die Effektivität der Ableitung der k- Indizes unter Verwendung von Enhanced Double Hashing und Triple Hashing , Varianten von Double Hashing , die effektiv einfache Zufallszahlengeneratoren sind, die mit den zwei oder drei Hashwerten gesät werden.)

Das Entfernen eines Elements aus diesem einfachen Bloom-Filter ist unmöglich, da es keine Möglichkeit gibt, zu sagen, auf welche der k Bits es abgebildet werden soll. Obwohl es ausreicht, eines dieser k Bits auf Null zu setzen, um das Element zu entfernen, würde es auch alle anderen Elemente entfernen, die zufällig auf dieses Bit abgebildet werden. Da der einfache Algorithmus keine Möglichkeit bietet, zu bestimmen, ob irgendwelche anderen Elemente hinzugefügt wurden, die die Bits für das zu entfernende Element beeinflussen, würde das Löschen eines der Bits die Möglichkeit falscher negativer Werte einführen.

Das einmalige Entfernen eines Elements aus einem Bloom-Filter kann simuliert werden, indem ein zweiter Bloom-Filter verwendet wird, der entfernte Elemente enthält. Falsch positive Ergebnisse im zweiten Filter werden jedoch im zusammengesetzten Filter zu falsch negativen Ergebnissen, was unerwünscht sein kann. Bei diesem Ansatz ist das erneute Hinzufügen eines zuvor entfernten Elements nicht möglich, da man es aus dem "entfernten" Filter entfernen müsste.

Es ist oft der Fall, dass alle Schlüssel verfügbar sind, aber das Aufzählen teuer ist (z. B. erfordert viele Plattenlesevorgänge). Wenn die Falsch-Positiv-Rate zu hoch wird, kann der Filter regeneriert werden; Dies sollte ein relativ seltenes Ereignis sein.

Raum- und Zeitvorteile

Bloom-Filter, der verwendet wird, um Antworten in einem Schlüsselwertspeichersystem zu beschleunigen. Die Werte werden auf einer Platte mit langsamen Zugriffszeiten gespeichert. Bloom-Filterentscheidungen sind viel schneller. Es werden jedoch einige unnötige Plattenzugriffe vorgenommen, wenn der Filter ein positives Ergebnis meldet (um die falsch positiven Ergebnisse auszusortieren). Die Gesamtantwortgeschwindigkeit ist mit dem Bloom-Filter besser als ohne den Bloom-Filter. Die Verwendung eines Bloom-Filters zu diesem Zweck erhöht jedoch die Speichernutzung.

Während Fehlalarme zu riskieren, haben Bloom Filter einen erheblichen Raumvorteil gegenüber anderen Datenstrukturen für die Darstellung von Sets, wie selbstausgleich binäre Suchbäume , versucht , Hash - Tabellen oder einfache Arrays oder verkettete Listen der Einträge. Die meisten von ihnen erfordern zumindest die Datenelemente selbst zu speichern, die überall von einer kleinen Anzahl von Bits erfordern können, für kleine ganze Zahlen sind , auf eine beliebige Anzahl von Bits, wie für Streicher ( Versuche sind eine Ausnahme , da sie Lagerung zwischen den Elementen teilen mit gleichen Präfixen). Bloom-Filter speichern die Datenelemente jedoch überhaupt nicht, und für die eigentliche Speicherung muss eine separate Lösung bereitgestellt werden. Verknüpfte Strukturen verursachen einen zusätzlichen linearen Platzbedarf für Zeiger. Ein Bloom-Filter mit einem Fehler von 1% und einem optimalen Wert von k benötigt dagegen nur etwa 9,6 Bit pro Element, unabhängig von der Größe der Elemente. Dieser Vorteil kommt teilweise von seiner Kompaktheit, die von Arrays geerbt wird, und teilweise von seiner probabilistischen Natur. Die Falsch-Positiv-Rate von 1 % kann um den Faktor zehn reduziert werden, indem nur etwa 4,8 Bit pro Element hinzugefügt werden.

Wenn jedoch die Anzahl potenzieller Werte klein ist und viele davon in der Menge enthalten sein können, wird der Bloom-Filter leicht von dem deterministischen Bit-Array übertroffen , das nur ein Bit für jedes potenzielle Element benötigt. Hash-Tabellen gewinnen einen Platz- und Zeitvorteil, wenn sie Kollisionen ignorieren und nur speichern, ob jeder Bucket einen Eintrag enthält; in diesem Fall sind sie mit k  = 1 effektiv zu Bloom-Filtern geworden .

Bloom-Filter haben auch die ungewöhnliche Eigenschaft, dass die Zeit, die benötigt wird, um entweder Elemente hinzuzufügen oder zu überprüfen, ob ein Element in der Menge ist, eine feste Konstante O( k ) ist, völlig unabhängig von der Anzahl der bereits in der Menge enthaltenen Elemente. Keine andere Datenstruktur mit konstantem Speicherplatz hat diese Eigenschaft, aber die durchschnittliche Zugriffszeit von Hash-Tabellen mit geringer Dichte kann sie in der Praxis schneller machen als einige Bloom-Filter. In einer Hardwareimplementierung glänzt der Bloom-Filter jedoch, weil seine k Lookups unabhängig sind und parallelisiert werden können.

Um seine Raumeffizienz zu verstehen, ist es aufschlussreich, den allgemeinen Bloom-Filter mit seinem Spezialfall bei k  = 1 zu vergleichen. Wenn k = 1, dann sollte, um die Falsch-Positiv-Rate ausreichend niedrig zu halten, ein kleiner Bruchteil von Bits gesetzt werden, Das bedeutet, dass das Array sehr groß sein muss und lange Nullen enthalten muss. Der Informationsgehalt des Arrays relativ zu seiner Größe ist gering. Der verallgemeinerte Bloom-Filter ( k größer als 1) ermöglicht es, viel mehr Bits zu setzen, während immer noch eine niedrige Falsch-Positiv-Rate aufrechterhalten wird; wenn die Parameter ( k und m ) gut gewählt sind, wird etwa die Hälfte der Bits gesetzt, und diese werden scheinbar zufällig sein, wodurch die Redundanz minimiert und der Informationsgehalt maximiert wird.

Wahrscheinlichkeit von Fehlalarmen

Die Falsch-Positiv-Wahrscheinlichkeit als Funktion der Anzahl der Elemente im Filter und der Filtergröße . Es wurde eine optimale Anzahl von Hashfunktionen angenommen.${\displaystyle p}$${\displaystyle n}$${\displaystyle m}$${\displaystyle k=(m/n)\ln 2}$

Angenommen, eine Hash-Funktion wählt jede Array-Position mit gleicher Wahrscheinlichkeit aus. Wenn m die Anzahl der Bits im Array ist, ist die Wahrscheinlichkeit, dass ein bestimmtes Bit durch eine bestimmte Hash-Funktion beim Einfügen eines Elements nicht auf 1 gesetzt wird,

${\displaystyle 1-{\frac {1}{m}}.}$

Wenn k die Anzahl der Hashfunktionen ist und jede keine signifikante Korrelation untereinander hat, dann ist die Wahrscheinlichkeit, dass das Bit von keiner der Hashfunktionen auf 1 gesetzt wird

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

Wir können die bekannte Identität für e ^{−1 . verwenden}

${\displaystyle \lim_{m\to\infty}\left(1-{\frac{1}{m}}\right)^{m}={\frac{1}{e}}}$

dass für große abschließen m ,

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m }\right)^{k/m}\approx e^{-k/m}.}$

Wenn wir n Elemente eingefügt haben , ist die Wahrscheinlichkeit, dass ein bestimmtes Bit immer noch 0 ist,

${\displaystyle \left(1-{\frac{1}{m}}\right)^{kn}\approx e^{-kn/m};}$

die Wahrscheinlichkeit, dass es 1 ist, ist also

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}\approx 1-e^{-kn/m}.}$

Testen Sie nun die Mitgliedschaft eines Elements, das nicht in der Menge ist. Jede der k Array-Positionen, die von den Hash-Funktionen berechnet werden, ist 1 mit einer Wahrscheinlichkeit wie oben. Die Wahrscheinlichkeit, dass alle von ihnen 1 sind, was dazu führen würde, dass der Algorithmus fälschlicherweise behauptet, dass das Element in der Menge enthalten ist, wird oft angegeben als

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{ -kn/m}\right)^{k}.}$

Dies ist nicht genau richtig, da es eine Unabhängigkeit für die Wahrscheinlichkeiten jedes gesetzten Bits voraussetzt. Unter der Annahme, dass es sich jedoch um eine enge Annäherung handelt, haben wir, dass die Wahrscheinlichkeit falscher positiver Ergebnisse mit zunehmendem m (der Anzahl der Bits im Array) abnimmt und mit zunehmendem n (der Anzahl der eingefügten Elemente) zunimmt.

Die wahre Wahrscheinlichkeit für ein falsch positives Ergebnis, ohne die Unabhängigkeit anzunehmen, ist

${\displaystyle {\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\ {{kn \atop i}\right\}}$

wobei die {Klammern} Stirlingzahlen zweiter Art bezeichnen .

Eine alternative Analyse, die ohne die Annahme der Unabhängigkeit zur gleichen Näherung gelangt, wird von Mitzenmacher und Upfal gegeben. Nachdem alle n Elemente zum Bloom-Filter hinzugefügt wurden, sei q der Bruchteil der m Bits, die auf 0 gesetzt sind. (Das heißt, die Anzahl der Bits, die noch auf 0 gesetzt sind, ist qm .) Element nicht in der Menge, für die Array-Position, die durch eine der k Hash-Funktionen angegeben wird, ist die Wahrscheinlichkeit, dass das Bit auf 1 gesetzt gefunden wird . Die Wahrscheinlichkeit, dass alle k Hashfunktionen feststellen, dass ihr Bit auf 1 gesetzt ist, ist also . Weiterhin ist der Erwartungswert von q die Wahrscheinlichkeit, dass eine gegebene Array-Position von jeder der k Hash-Funktionen für jedes der n Elemente unberührt bleibt , was (wie oben) ${\displaystyle 1-q}$${\displaystyle (1-q)^{k}}$

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{kn}}$.

Ohne die Unabhängigkeitsannahme lässt sich beweisen, dass q sehr stark um seinen Erwartungswert konzentriert ist. Insbesondere beweisen sie aus der Azuma-Hoeffding-Ungleichung , dass

${\displaystyle \Pr(\left|qE[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda^{2}/kn)}$

Aus diesem Grund können wir sagen, dass die genaue Wahrscheinlichkeit falsch positiver Ergebnisse

${\displaystyle \sum_{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1- {\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$

wie vorher.

Optimale Anzahl an Hash-Funktionen

Die Anzahl der Hashfunktionen k muss eine positive ganze Zahl sein. Abgesehen von dieser Einschränkung ist der Wert von k , der die falsch-positive Wahrscheinlichkeit minimiert , für ein gegebenes m und n

${\displaystyle k={\frac {m}{n}}\ln 2.}$

Die erforderliche Anzahl von Bits m bei gegebenem n (der Anzahl der eingefügten Elemente) und einer gewünschten falsch-positiven Wahrscheinlichkeit ε (und unter der Annahme, dass der optimale Wert von k verwendet wird) kann berechnet werden, indem der optimale Wert von k in den obigen Wahrscheinlichkeitsausdruck eingesetzt wird :

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac { m}{n}}\ln 2}}$

was vereinfacht werden kann zu:

${\displaystyle \ln \varepsilon =-{\frac {m}{n}}\left(\ln 2\right)^{2}.}$

Das führt zu:

${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$

Die optimale Anzahl von Bits pro Element ist also

${\displaystyle {\frac {m}{n}}=-{\frac {\log_{2}\varepsilon }{\ln 2}}\approx -1,44\log_{2}\varepsilon}$

mit der entsprechenden Anzahl von Hashfunktionen k (ohne Berücksichtigung der Ganzzahl):

${\displaystyle k=-{\frac {\ln\varepsilon }{\ln 2}}=-\log_{2}\varepsilon.}$

Dies bedeutet, dass für eine gegebene Falsch-Positiv-Wahrscheinlichkeit ε die Länge eines Bloom-Filters m proportional zur Anzahl der zu filternden Elemente n ist und die erforderliche Anzahl von Hash-Funktionen nur von der Ziel-Falsch-Positiv-Wahrscheinlichkeit ε abhängt .

Die Formel ist aus drei Gründen ungefähr. Erstens, und am wenigsten besorgniserregend, approximiert sie sich als , was eine gute asymptotische Approximation ist (dh die als m → ∞ gilt). Zweitens wird davon ausgegangen, dass während des Zugehörigkeitstests das Ereignis, dass ein getestetes Bit auf 1 gesetzt wird, unabhängig von dem Ereignis ist, dass jedes andere getestete Bit auf 1 gesetzt wird . ${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$${\displaystyle 1-{\frac {1}{m}}}$${\displaystyle e^{-{\frac {1}{m}}}}$${\displaystyle k={\frac {m}{n}}\ln 2}$

Goel und Gupta geben jedoch eine strenge obere Schranke an, die keine Näherungen macht und keine Annahmen erfordert. Sie zeigen, dass die False-Positive-Wahrscheinlichkeit für einen endlichen Bloom-Filter mit m Bits ( ), n Elementen und k Hashfunktionen höchstens ${\displaystyle m>1}$

${\displaystyle \varepsilon\leq\left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

Diese Grenze kann dahingehend interpretiert werden, dass die Näherungsformel mit einem Abzug von höchstens einem halben zusätzlichen Element und höchstens einem Bit weniger angewendet werden kann. ${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$

Ungefähre Anzahl der Elemente in einem Bloom-Filter

Swamidass & Baldi (2007) zeigten, dass die Anzahl der Elemente in einem Bloom-Filter mit der folgenden Formel angenähert werden kann:

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

wobei eine Schätzung der Anzahl von Elementen im Filter ist, m die Länge (Größe) des Filters ist, k die Anzahl der Hash-Funktionen ist und X die Anzahl der Bits ist, die auf eins gesetzt sind. ${\displaystyle n^{*}}$

Vereinigung und Schnittmenge von Mengen

Bloom-Filter sind eine Möglichkeit, eine Reihe von Elementen kompakt darzustellen. Es ist üblich zu versuchen, die Größe der Schnittmenge oder Vereinigung zwischen zwei Mengen zu berechnen. Bloom-Filter können verwendet werden, um die Größe der Schnittmenge und Vereinigung von zwei Sätzen anzunähern. Swamidass & Baldi (2007) zeigten, dass für zwei Bloom-Filter der Länge m deren Anzahl jeweils geschätzt werden kann als

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$

und

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

Die Größe ihrer Vereinigung kann geschätzt werden als

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m }}\rechts],}$

wobei die Anzahl der Bits in einem der beiden Bloom-Filter auf eins gesetzt ist. Schließlich kann der Schnittpunkt geschätzt werden als ${\displaystyle n(A\cup B)}$

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{* }),}$

die drei Formeln zusammen verwenden.

Interessante Eigenschaften

• Im Gegensatz zu einer Standard- Hash-Tabelle, die offene Adressierung zur Kollisionsauflösung verwendet , kann ein Bloom-Filter einer festen Größe eine Menge mit einer beliebig großen Anzahl von Elementen darstellen; Das Hinzufügen eines Elements schlägt nie fehl, weil die Datenstruktur "auffüllt". Allerdings steigt die Falsch-Positiv-Rate stetig an, wenn Elemente hinzugefügt werden, bis alle Bits im Filter auf 1 gesetzt sind, woraufhin alle Abfragen ein positives Ergebnis liefern. Beim Hashing mit offener Adressierung werden nie falsch positive Ergebnisse erzeugt, aber die Leistung verschlechtert sich stetig, bis sie sich der linearen Suche nähert.
• Vereinigung und Schnittmenge von Bloom-Filtern mit der gleichen Größe und Menge von Hash-Funktionen können mit bitweisen ODER- bzw. UND-Operationen implementiert werden . Die Vereinigungsoperation für Bloom-Filter ist insofern verlustfrei, als der resultierende Bloom-Filter der gleiche ist wie der Bloom-Filter, der von Grund auf unter Verwendung der Vereinigung der beiden Sätze erstellt wurde. Die Intersect-Operation erfüllt eine schwächere Eigenschaft: Die Falsch-Positiv-Wahrscheinlichkeit im resultierenden Bloom-Filter ist höchstens die Falsch-Positiv-Wahrscheinlichkeit in einem der konstituierenden Bloom-Filter, kann aber größer sein als die Falsch-Positiv-Wahrscheinlichkeit in dem von Grund auf neu erstellten Bloom-Filter mit der Schnittpunkt der beiden Mengen.
• Einige Arten von überlagertem Code können als Bloom-Filter betrachtet werden, der mit physischen Edge-Notched-Karten implementiert wird . Ein Beispiel ist das 1947 von Calvin Mooers erfundene Zatocoding , bei dem die mit einer Information verbundenen Kategorien durch Kerben auf einer Karte dargestellt werden, mit einem zufälligen Muster von vier Kerben für jede Kategorie.

Beispiele

• Fruchtfliegen verwenden eine modifizierte Version von Bloom-Filtern, um Neuheiten von Gerüchen zu erkennen, mit zusätzlichen Merkmalen, einschließlich der Ähnlichkeit des neuartigen Geruchs mit dem von zuvor erlebten Beispielen und der seit der vorherigen Erfahrung des gleichen Geruchs verstrichenen Zeit.
• Die Server von Akamai Technologies , einem Anbieter von Inhalten , verwenden Bloom-Filter, um zu verhindern, dass "One-Hit-Wonders" in ihren Disk-Caches gespeichert werden. One-Hit-Wonder sind Webobjekte, die von Benutzern nur einmal angefordert werden, was Akamai auf fast drei Viertel ihrer Caching-Infrastruktur zutraf. Die Verwendung eines Bloom-Filters zum Erkennen der zweiten Anfrage für ein Webobjekt und das Zwischenspeichern dieses Objekts nur bei seiner zweiten Anfrage verhindert, dass One-Hit-Wonder in den Festplatten-Cache gelangen, wodurch die Festplatten-Arbeitslast erheblich reduziert und die Festplatten-Cache-Trefferraten erhöht werden.
• Google Bigtable , Apache HBase und Apache Cassandra und PostgreSQL verwenden Bloom-Filter, um die Festplattensuche nach nicht vorhandenen Zeilen oder Spalten zu reduzieren. Durch die Vermeidung kostspieliger Festplattensuchvorgänge wird die Leistung eines Datenbankabfragevorgangs erheblich gesteigert.
• Der Google Chrome -Webbrowser verwendet einen Bloom-Filter, um bösartige URLs zu identifizieren. Jede URL wurde zuerst mit einem lokalen Bloom-Filter überprüft, und nur wenn der Bloom-Filter ein positives Ergebnis lieferte, wurde eine vollständige Überprüfung der URL durchgeführt (und der Benutzer warnte, wenn auch dieser ein positives Ergebnis lieferte).
• Microsoft Bing (Suchmaschine) verwendet mehrstufige hierarchische Bloom-Filter für seinen Suchindex BitFunnel . Bloom-Filter boten niedrigere Kosten als der vorherige Bing-Index, der auf invertierten Dateien basierte .
• Der Squid Web Proxy Cache verwendet Bloom-Filter für Cache-Digests .
• Bitcoin verwendete Bloom-Filter, um die Wallet-Synchronisierung zu beschleunigen, bis Datenschutzschwachstellen bei der Implementierung von Bloom-Filtern entdeckt wurden.
• Das Venti- Archivierungsspeichersystem verwendet Bloom-Filter, um zuvor gespeicherte Daten zu erkennen.
• Der SPIN-Modellprüfer verwendet Bloom-Filter, um den erreichbaren Zustandsraum für große Verifikationsprobleme zu verfolgen.
• Das Cascading Analytics Framework verwendet Bloom-Filter, um asymmetrische Joins zu beschleunigen, bei denen einer der zusammengeführten Datensätze erheblich größer ist als der andere (in der Datenbankliteratur oft als Bloom-Join bezeichnet).
• Der Exim Mail Transfer Agent (MTA) verwendet Bloom-Filter in seiner Ratenbegrenzungsfunktion.
• Medium verwendet Bloom-Filter, um zu vermeiden, Artikel zu empfehlen, die ein Benutzer zuvor gelesen hat.
• Ethereum verwendet Bloom-Filter, um Protokolle in der Ethereum-Blockchain schnell zu finden.

Alternativen

Klassische Bloom-Filter verwenden Speicherplatz pro eingefügtem Schlüssel, wobei die False-Positive-Rate des Bloom-Filters ist. Der Platz, der für jede Datenstruktur, die dieselbe Rolle wie ein Bloom-Filter spielt, jedoch unbedingt erforderlich ist, ist nur pro Schlüssel. Daher benötigen Bloom-Filter 44% mehr Platz als eine äquivalente optimale Datenstruktur. Stattdessen haben Pagh et al. eine raumoptimierte Datenstruktur bereitzustellen. Darüber hinaus hat ihre Datenstruktur unabhängig von der Falsch-Positiv-Rate eine konstante Referenzlokalität , im Gegensatz zu Bloom-Filtern, bei denen eine niedrigere Falsch-Positiv-Rate zu einer größeren Anzahl von Speicherzugriffen pro Abfrage führt, . Außerdem können Elemente im Gegensatz zu Bloom-Filtern ohne Platzeinbußen gelöscht werden. Die gleichen verbesserten Eigenschaften der optimalen Raumnutzung, konstanten Referenzlokalität und der Möglichkeit, Elemente zu löschen, bietet auch der Kuckucksfilter von Fan et al. (2014) , von denen eine Open-Source-Implementierung verfügbar ist. ${\displaystyle 1,44\log_{2}(1/\varepsilon)}$${\displaystyle\varepsilon}$${\displaystyle \log_{2}(1/\varepsilon)}$${\displaystyle\varepsilon}$${\displaystyle \log(1/\varepsilon)}$

Stern & Dill (1996) beschreiben eine auf Hash-Tabellen basierende probabilistische Struktur , die Hash- Kompression , die Dillinger & Manolios (2004b) bei optimaler Konfiguration als deutlich genauer als ein Bloom-Filter identifizieren. Dillinger und Manolios weisen jedoch darauf hin, dass die angemessene Genauigkeit eines gegebenen Bloom-Filters über einen weiten Bereich von Additionen ihn für die probabilistische Aufzählung von Zustandsräumen unbekannter Größe attraktiv macht. Die Hash-Komprimierung ist daher attraktiv, wenn die Anzahl der Additionen genau vorhergesagt werden kann; Obwohl die Hash-Komprimierung in der Software sehr schnell ist, ist sie aufgrund der linearen Zugriffszeit im schlimmsten Fall jedoch für Hardware schlecht geeignet.

Putze, Sanders & Singler (2007) haben einige Varianten von Bloom-Filtern untersucht, die entweder schneller sind oder weniger Platz benötigen als klassische Bloom-Filter. Die Grundidee der schnellen Variante besteht darin, die k Hash-Werte, die jedem Schlüssel zugeordnet sind, in einen oder zwei Blöcke mit derselben Größe wie die Speicher-Cache-Blöcke des Prozessors (normalerweise 64 Byte) zu lokalisieren. Dies wird vermutlich die Leistung verbessern, indem die Anzahl potenzieller Speicher- Cache-Fehltreffer verringert wird . Die vorgeschlagenen Varianten haben jedoch den Nachteil, dass sie etwa 32 % mehr Platz benötigen als klassische Bloom-Filter.

Die platzsparende Variante setzt eine einzige Hash - Funktion auf die Verwendung für jede Taste einen Wert in dem Bereich erzeugt , wo die angeforderte falsch positive Rate ist. Die Folge von Werten wird dann sortiert und unter Verwendung von Golomb-Codierung (oder einer anderen Kompressionstechnik) komprimiert, um einen Platz in der Nähe von Bits einzunehmen . Um den Bloom-Filter nach einem bestimmten Schlüssel abzufragen, genügt es zu prüfen, ob der entsprechende Wert im Bloom-Filter gespeichert ist. Das Dekomprimieren des gesamten Bloom-Filters für jede Abfrage würde diese Variante völlig unbrauchbar machen. Um dieses Problem zu lösen, wird die Wertefolge in kleine Blöcke gleicher Größe unterteilt, die separat komprimiert werden. Zur Abfragezeit muss im Durchschnitt nur ein halber Block dekomprimiert werden. Aufgrund des Dekompressions-Overheads kann diese Variante langsamer sein als klassische Bloom-Filter, dies kann jedoch dadurch kompensiert werden, dass eine einzelne Hash-Funktion berechnet werden muss. ${\displaystyle \left[0,n/\varepsilon \right]}$${\displaystyle\varepsilon}$${\displaystyle n\log_{2}(1/\varepsilon)}$

Eine weitere Alternative zum klassischen Bloom-Filter ist der Kuckucksfilter , basierend auf platzsparenden Varianten des Kuckucks-Hashings . In diesem Fall wird eine Hash-Tabelle erstellt, die weder Schlüssel noch Werte enthält, sondern kurze Fingerabdrücke (kleine Hashes) der Schlüssel. Wenn das Nachschlagen des Schlüssels einen passenden Fingerabdruck findet, ist der Schlüssel wahrscheinlich im Set. Eine nützliche Eigenschaft von Kuckucksfiltern ist, dass sie aktualisierbar sind; Einträge können dynamisch hinzugefügt (mit einer geringen Ausfallwahrscheinlichkeit, da die Hash-Tabelle voll ist) und entfernt werden.

Graf & Lemire (2019) beschreiben einen als Xor-Filter bezeichneten Ansatz, bei dem Fingerabdrücke in einer bestimmten Art von perfekter Hash- Tabelle gespeichert werden, wodurch ein Filter erzeugt wird, der speichereffizienter ( Bits pro Schlüssel) und schneller als Bloom- oder Kuckucksfilter ist. (Die Zeitersparnis ergibt sich aus der Tatsache, dass ein Lookup genau drei Speicherzugriffe erfordert, die alle parallel ausgeführt werden können.) Die Filtererstellung ist jedoch komplexer als Bloom- und Kuckucksfilter, und es ist nicht möglich, das Set nach der Erstellung zu ändern. harvtxt-Fehler: kein Ziel: CITEREFGrafLemire2019 ( Hilfe )${\displaystyle 1.23\log_{2}(1/\varepsilon)}$

Erweiterungen und Anwendungen

Es gibt über 60 Varianten von Bloom-Filtern, viele Untersuchungen auf diesem Gebiet und eine anhaltende Flut von Anwendungen (siehe zB Luo et al. ). Einige der Varianten weichen ausreichend vom ursprünglichen Vorschlag ab, um Verletzungen oder Verzweigungen der ursprünglichen Datenstruktur und ihrer Philosophie zu sein. Eine Behandlung, die Bloom-Filter mit anderen Arbeiten zu Zufallsprojektionen , Compression Sensing und ortssensitivem Hashing vereint , muss noch durchgeführt werden (obwohl siehe Dasgupta et al. für einen von den Neurowissenschaften inspirierten Versuch).

Cache-Filterung

Die Verwendung eines Bloom-Filters, um zu verhindern, dass One-Hit-Wonder in einem Web-Cache gespeichert werden, verringerte die Rate der Festplattenschreibvorgänge um fast die Hälfte, wodurch die Belastung der Festplatten verringert und möglicherweise die Festplattenleistung erhöht wurde.

Content Delivery Networks stellen weltweit Web-Caches bereit, um Webinhalte zwischenzuspeichern und Benutzern mit höherer Leistung und Zuverlässigkeit bereitzustellen. Eine Schlüsselanwendung von Bloom-Filtern ist ihre Verwendung bei der effizienten Bestimmung, welche Webobjekte in diesen Web-Caches gespeichert werden sollen. Fast drei Viertel der URLs, auf die aus einem typischen Webcache zugegriffen wird, sind "One-Hit-Wonder", auf die Benutzer nur einmal und nie wieder zugreifen. Es ist eindeutig eine Verschwendung von Festplattenressourcen, One-Hit-Wonder in einem Web-Cache zu speichern, da nie wieder auf sie zugegriffen werden kann. Um One-Hit-Wonder zwischenzuspeichern, wird ein Bloom-Filter verwendet, um alle URLs zu verfolgen, auf die von Benutzern zugegriffen wird. Ein Web-Objekt wird nur dann zwischengespeichert, wenn zuvor mindestens einmal darauf zugegriffen wurde, dh das Objekt wird bei seiner zweiten Anforderung zwischengespeichert. Die Verwendung eines Bloom-Filters auf diese Weise reduziert die Schreibarbeitslast der Festplatte erheblich, da One-Hit-Wonder nie in den Festplatten-Cache geschrieben werden. Darüber hinaus spart das Herausfiltern der One-Hit-Wonder auch Cache-Speicherplatz auf der Festplatte, was die Cache-Trefferraten erhöht.

Vermeidung von Fehlalarmen in einem endlichen Universum

Kiss et al. beschrieben eine neue Konstruktion für den Bloom-Filter, die zusätzlich zum typischen Fehlen von falsch-negativen falsch-positiven Ergebnissen vermeidet. Die Konstruktion gilt für ein endliches Universum, aus dem Mengenelemente entnommen werden. Es stützt sich auf das bestehende nicht-adaptive kombinatorische Gruppentestschema von Eppstein, Goodrich und Hirschberg. Im Gegensatz zum typischen Bloom-Filter werden Elemente durch deterministische, schnelle und einfach zu berechnende Funktionen zu einem Bit-Array gehasht. Die maximale Satzgröße, bei der Fehlalarme vollständig vermieden werden, ist eine Funktion der Universumsgröße und wird durch die Menge des zugewiesenen Speichers gesteuert.

Bloom-Filter zählen

Zählfilter bieten eine Möglichkeit, einen Löschvorgang für einen Bloom-Filter zu implementieren , ohne den Filter neu zu erstellen. In einem Zählfilter werden die Array-Positionen (Buckets) von einem einzelnen Bit zu einem Multibit-Zähler erweitert. Tatsächlich können reguläre Bloom-Filter als Zählfilter mit einer Bucket-Größe von einem Bit betrachtet werden. Zählfilter wurden von Fan et al. (2000) .

Die Einfügeoperation wird erweitert , um inkrementiert den Wert der Schaufeln, und die Lookup - Operation überprüft , dass jede der erforderlichen Schaufeln nicht Null ist . Die Löschoperation besteht dann darin, den Wert jedes der jeweiligen Buckets zu dekrementieren.

Ein arithmetischer Überlauf der Eimer ist ein Problem und die Eimer sollten ausreichend groß sein, um diesen Fall selten zu machen. In diesem Fall müssen die Inkrement- und Dekrementierungsoperationen den Bucket auf den maximal möglichen Wert eingestellt lassen, um die Eigenschaften eines Bloom-Filters beizubehalten.

Die Größe von Zählern beträgt normalerweise 3 oder 4 Bit. Das Zählen von Bloom-Filtern benötigt daher 3 bis 4 Mal mehr Platz als statische Bloom-Filter. Die Datenstrukturen von Pagh, Pagh & Rao (2005) und Fan et al. (2014) erlauben auch Löschungen, benötigen aber weniger Platz als ein statischer Bloom-Filter.

Ein weiteres Problem bei Zählfiltern ist die eingeschränkte Skalierbarkeit. Da die zählende Bloom-Filtertabelle nicht erweitert werden kann, muss die maximale Anzahl gleichzeitig im Filter zu speichernder Schlüssel im Voraus bekannt sein. Sobald die vorgesehene Kapazität des Tisches überschritten ist, steigt die Falsch-Positiv-Rate schnell an, wenn mehr Schlüssel eingeführt werden.

Bonomiet al. (2006) stellten eine Datenstruktur vor, die auf d-links-Hashing basiert, die funktional äquivalent ist, aber etwa halb so viel Platz benötigt wie das Zählen von Bloom-Filtern. Das Skalierbarkeitsproblem tritt in dieser Datenstruktur nicht auf. Sobald die vorgesehene Kapazität überschritten ist, könnten die Schlüssel wieder in eine neue Hash-Tabelle doppelter Größe eingefügt werden.

Auch die platzsparende Variante von Putze, Sanders & Singler (2007) könnte verwendet werden, um Zählfilter zu implementieren, indem Einfügungen und Löschungen unterstützt werden.

Rottenstreich, Kanizo & Keslassy (2012) stellten eine neue allgemeine Methode vor, die auf variablen Inkrementen basiert, die die Falsch-Positiv-Wahrscheinlichkeit des Zählens von Bloom-Filtern und ihren Varianten signifikant verbessert und gleichzeitig Deletionen unterstützt. Im Gegensatz zum Zählen von Bloom-Filtern werden die Hash-Zähler bei jeder Elementeinfügung um ein Hash-Variableninkrement anstelle eines Einheitsinkrements erhöht. Um ein Element abzufragen, werden die genauen Werte der Zähler berücksichtigt und nicht nur deren Positivität. Kann eine durch einen Zählerwert repräsentierte Summe nicht aus dem entsprechenden variablen Inkrement für das abgefragte Element zusammengesetzt werden, kann eine negative Antwort auf die Abfrage zurückgegeben werden.

Kimet al. (2019) zeigt, dass das Falsch-Positiv des Counting Bloom-Filters von k=1 bis zu einem definierten Punkt abnimmt und von positiv unendlich ansteigt , und findet als Funktion des Zählschwellenwerts. ${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$

Dezentrale Aggregation

Bloom-Filter können in verteilten Datenstrukturen organisiert werden , um vollständig dezentralisierte Berechnungen von Aggregatfunktionen durchzuführen . Die dezentrale Aggregation macht Sammelmessungen in jedem Knoten eines verteilten Netzes lokal verfügbar, ohne dass hierfür eine zentrale Recheninstanz involviert ist.

Verteilte Bloom-Filter

Distributed Single Shot Bloom Filter zur Dublettenerkennung mit False Positive Rate: 6 Elemente werden auf 3 PEs mit jeweils einem Bit-Array der Länge 4 verteilt. Während des ersten Kommunikationsschritts empfängt PE 1 den Hash '2' zweimal und sendet ihn an einen der beiden zurück PE 2 oder 3, je nachdem, wer es später geschickt hat. Das PE, das den Hash '2' empfängt, sucht dann nach dem Element mit diesem Hash und markiert es als mögliches Duplikat.

Parallel Bloom-Filter können implementiert werden, um die Vorteile der mehreren Verarbeitungselemente (PEs) zu nutzen, die in parallelen Shared-Nothing-Maschinen vorhanden sind . Eines der Haupthindernisse für einen parallelen Bloom-Filter ist die Organisation und Kommunikation der ungeordneten Daten, die im Allgemeinen bei der Initiierung oder bei Stapeleinfügungen gleichmäßig auf alle PEs verteilt werden. Um die Daten zu ordnen, können zwei Ansätze verwendet werden, die entweder dazu führen, dass ein Bloom-Filter über alle Daten, die auf jedem PE gespeichert werden, replizierter Bloom-Filter genannt wird, oder der Bloom-Filter über alle Daten in gleiche Teile aufgeteilt wird, wobei jedes PE einen Teil davon speichert . Für beide Ansätze wird ein "Single Shot" Bloom Filter verwendet, der nur einen Hash berechnet, was zu einem Flipped Bit pro Element führt, um das Kommunikationsvolumen zu reduzieren.

Verteilte Bloom-Filter werden initiiert, indem zuerst alle Elemente auf ihrem lokalen PE gehasht und dann lokal nach ihren Hashes sortiert werden. Dies kann in linearer Zeit mit zB Bucket-Sort erfolgen und ermöglicht auch eine lokale Dublettenerkennung. Die Sortierung wird verwendet, um die Hashes mit ihrem zugewiesenen PE als Trennzeichen zu gruppieren, um für jede Gruppe einen Bloom-Filter zu erstellen. Nach der Codierung dieser Bloom-Filter unter Verwendung von zB Golomb-Codierung wird jeder Bloom-Filter als Paket an das PE gesendet, das für die Hash-Werte verantwortlich ist, die darin eingefügt wurden. Ein PE p ist für alle Hashes zwischen den Werten und verantwortlich , wobei s die Gesamtgröße des Bloom-Filters über alle Daten ist. Da jedes Element nur einmal gehasht wird und somit nur ein einzelnes Bit gesetzt wird, muss zur Überprüfung, ob ein Element in den Bloom-Filter eingefügt wurde, nur das für den Hash-Wert des Elements verantwortliche PE operiert werden. Einzelne Einfügungsoperationen können auch effizient durchgeführt werden, da der Bloom-Filter von nur einem PE geändert werden muss, im Vergleich zu replizierenden Bloom-Filtern, bei denen jedes PE seinen Bloom-Filter aktualisieren müsste. Durch die Verteilung des globalen Bloom-Filters über alle PEs, anstatt ihn separat auf jedem PE zu speichern, kann die Größe des Bloom-Filters viel größer sein, was zu einer größeren Kapazität und einer niedrigeren Falsch-Positiv-Rate führt. Distributed Bloom-Filter können verwendet werden, um die Duplikaterkennungsalgorithmen zu verbessern, indem die "einzigartigsten" Elemente herausgefiltert werden. Diese können berechnet werden, indem nur die Hashes von Elementen übermittelt werden, nicht die Elemente selbst, die ein viel größeres Volumen aufweisen, und sie aus dem Satz entfernen, wodurch der Arbeitsaufwand für den anschließend verwendeten Duplikaterkennungsalgorithmus reduziert wird. ${\displaystyle p*(s/|{\text{PE}}|)}$${\displaystyle (p+1)*(s/|{\text{PE}}|)}$

Während der Übertragung der Hashes suchen die PEs nach Bits, die in mehr als einem der empfangenden Pakete gesetzt sind, da dies bedeuten würde, dass zwei Elemente den gleichen Hash hätten und somit Duplikate sein könnten. Wenn dies auftritt, wird eine Nachricht mit dem Index des Bits, der auch der Hash des Elements ist, das ein Duplikat sein könnte, an die PEs gesendet, die ein Paket mit dem gesetzten Bit gesendet haben. Wenn mehrere Indizes von einem Sender an dasselbe PE gesendet werden, kann es vorteilhaft sein, die Indizes ebenfalls zu kodieren. Alle Elemente, deren Hash nicht zurückgesendet wurde, sind jetzt garantiert kein Duplikat und werden nicht weiter ausgewertet, für die restlichen Elemente kann ein Repartitionierungsalgorithmus verwendet werden. Zuerst werden alle Elemente, deren Hash-Wert zurückgesendet wurde, an das PE gesendet, für das ihr Hash verantwortlich ist. Jedes Element und sein Duplikat befinden sich jetzt garantiert auf demselben PE. Im zweiten Schritt verwendet jedes PE einen sequentiellen Algorithmus zur Duplikaterkennung auf den Empfangselementen, die nur einen Bruchteil der Anzahl der Startelemente ausmachen. Durch Zulassen einer False-Positive-Rate für die Duplikate kann das Kommunikationsvolumen weiter reduziert werden, da die PEs überhaupt keine Elemente mit dupliziertem Hash senden müssen und stattdessen jedes Element mit dupliziertem Hash einfach als Duplikat markiert werden kann. Als Ergebnis ist die Falsch-Positiv-Rate für die Duplikatserkennung die gleiche wie die Falsch-Positiv-Rate des verwendeten Bloom-Filters.

Das Herausfiltern der „einzigartigsten“ Elemente kann auch mehrmals wiederholt werden, indem die Hash-Funktion in jedem Filterschritt geändert wird. Wenn nur ein einziger Filterschritt verwendet wird, muss er eine kleine falsch-positive Rate archivieren, wenn der Filterschritt jedoch einmal wiederholt wird, kann der erste Schritt eine höhere falsch-positive Rate ermöglichen, während letzterer eine höhere hat, aber auch mit weniger Elementen arbeitet so viele wurden bereits durch den früheren Filterschritt entfernt. Während die Verwendung von mehr als zwei Wiederholungen das Kommunikationsvolumen weiter reduzieren kann, wenn die Anzahl der Duplikate in einem Set gering ist, ist die Auszahlung für die zusätzlichen Komplikationen gering.

Replizierende Bloom-Filter organisieren ihre Daten unter Verwendung eines bekannten Hypercube- Algorithmus zum Klatschen, zB Zuerst berechnet jedes PE den Bloom-Filter über alle lokalen Elemente und speichert ihn. Durch Wiederholen einer Schleife, in der die PEs in jedem Schritt i ihren lokalen Bloom-Filter über die Dimension i senden und den Bloom-Filter, den sie über die Dimension empfangen, mit ihrem lokalen Bloom-Filter zusammenführen, ist es möglich, die Elemente, die jeder Bloom-Filter enthält, in jeder Iteration zu verdoppeln. Nach dem Senden und Empfangen von Bloom-Filtern über alle Dimensionen enthält jedes PE den globalen Bloom-Filter über alle Elemente. ${\displaystyle \log |{\text{PE}}|}$

Replizieren Bloom Filter sind effizienter , wenn die Anzahl der Abfragen viel größer als die Anzahl der Elemente ist , dass die Bloom - Filter enthalten, zeigen Sie die Break - even im Vergleich zu verteilten Bloom - Filter etwa nach Zugriffen, wobei als falsch - positiven Rate der Bloom - Filter. ${\displaystyle |{\text{PE}}|*|{\text{Elemente}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$${\displaystyle f^{\text{+}}}$

Datensynchronisation

Bloom-Filter können zur ungefähren Datensynchronisation verwendet werden, wie in Byers et al. (2004) . Counting Bloom-Filter können verwendet werden, um die Anzahl der Unterschiede zwischen zwei Sätzen zu approximieren, und dieser Ansatz wird in Agarwal & Trachtenberg (2006) beschrieben .

Bloom-Filter für Streaming-Daten

Bloom-Filter können an den Kontext von Streaming-Daten angepasst werden. Zum Beispiel schlugen Deng & Rafiei (2006) Stable Bloom-Filter vor, die aus einem zählenden Bloom-Filter bestehen, bei dem das Einfügen eines neuen Elements die zugehörigen Zähler auf einen Wert setzt und dann nur eine feste Anzahl von Zählern um 1 verringert wird, daher die Speicher enthält hauptsächlich Informationen über aktuelle Elemente (intuitiv könnte man annehmen, dass die Lebensdauer eines Elements in einer SBF von Zählern ungefähr beträgt ). Eine andere Lösung ist der Aging Bloom-Filter, der aus zwei Bloom-Filtern besteht, die jeweils die Hälfte des gesamten verfügbaren Speichers belegen: Wenn ein Filter voll ist, wird der zweite Filter gelöscht und diesem neu leeren Filter werden neue Elemente hinzugefügt. ${\displaystyle c}$${\displaystyle s}$${\displaystyle N}$${\displaystyle c{\frac {s}{N}}}$

Es hat sich jedoch , daß keine der Filter Rolle, nachdem sich gezeigt, Insertionen, die Summe der falsch positiven und falsch negativen Wahrscheinlichkeiten begrenzt ist unten durch , wo ist , die Menge aller möglichen Elemente (die Alphabetgröße), die Speichergröße (in Bits) , vorausgesetzt . Dieses Ergebnis zeigt, dass für groß genug und gegen unendlich gehend, dann die untere Schranke gegen konvergiert , was die charakteristische Beziehung eines Zufallsfilters ist. Daher ist es nach genügend Einfügungen und wenn das Alphabet zu groß ist, um im Speicher gespeichert zu werden (was im Zusammenhang mit Wahrscheinlichkeitsfiltern angenommen wird), für einen Filter unmöglich, eine bessere Leistung als der Zufall zu erbringen. Dieses Ergebnis kann genutzt werden, indem nur erwartet wird, dass ein Filter auf einem gleitenden Fenster und nicht auf dem gesamten Stream arbeitet. In diesem Fall wird der Exponent in der obigen Formel durch ersetzt , was eine Formel ergibt, die von 1 abweichen kann, wenn sie nicht zu klein ist. ${\displaystyle n}$${\displaystyle FP}$${\displaystyle FN}$${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$${\displaystyle L}$${\displaystyle m}$${\displaystyle n>m}$${\displaystyle L}$${\displaystyle n}$${\displaystyle FP+FN=1}$${\displaystyle n}$${\displaystyle w}$${\displaystyle w}$

Bloomier-Filter

Chazelleet al. (2004) entwarfen eine Verallgemeinerung von Bloom-Filtern, die jedem eingefügten Element einen Wert zuordnen konnten und ein assoziatives Array implementierten . Wie Bloom-Filter erreichen diese Strukturen einen geringen Platz-Overhead, indem sie eine geringe Wahrscheinlichkeit von Fehlalarmen akzeptieren. Im Fall von "Bloomier-Filtern" ist ein falsch positives Ergebnis definiert als Rückgabe eines Ergebnisses, wenn der Schlüssel nicht in der Karte enthalten ist. Die Map gibt nie den falschen Wert für einen Schlüssel zurück, der sich in der Map befindet.

Kompakte Approximatoren

Boldi & Vigna (2005) vorgeschlagen , ein Gitter -basierte Verallgemeinerung von Bloom - Filter. Ein kompakter Approximator ordnet jedem Schlüssel ein Element eines Gitters zu (die Standard-Bloom-Filter sind der Fall des Booleschen Zwei-Element-Gitters). Anstelle eines Bit-Arrays haben sie ein Array von Gitterelementen. Beim Hinzufügen einer neuen Assoziation zwischen einem Schlüssel und einem Element des Gitters berechnen sie das Maximum des aktuellen Inhalts der k Array-Positionen, die dem Schlüssel mit dem Gitterelement zugeordnet sind. Beim Lesen des einem Schlüssel zugeordneten Werts berechnen sie das Minimum der Werte, die an den k Stellen gefunden werden, die dem Schlüssel zugeordnet sind. Der resultierende Wert nähert sich von oben dem ursprünglichen Wert an.

Parallel partitionierte Bloom-Filter

Diese Implementierung verwendet ein separates Array für jede Hash-Funktion. Diese Methode ermöglicht parallele Hash-Berechnungen sowohl für Einfügungen als auch für Abfragen.

Skalierbare Bloom-Filter

Almeidaet al. (2007) schlugen eine Variante von Bloom-Filtern vor, die sich dynamisch an die Anzahl der gespeicherten Elemente anpassen kann und gleichzeitig eine minimale Wahrscheinlichkeit falscher positiver Ergebnisse gewährleistet. Die Technik basiert auf Sequenzen von Standard-Bloom-Filtern mit zunehmender Kapazität und engeren Falsch-Positiv-Wahrscheinlichkeiten, um sicherzustellen, dass eine maximale Falsch-Positiv-Wahrscheinlichkeit im Voraus festgelegt werden kann, unabhängig von der Anzahl der einzufügenden Elemente.

Räumliche Bloom-Filter

Räumliche Bloom Filter (SBF) wurden ursprünglich von vorgeschlagen Palmieri, Calderoni & Maio (2014) als Datenstruktur zur Speicherung Standortinformationen , insbesondere im Zusammenhang mit kryptographischen Protokollen für die Lage der Privatsphäre . Das Hauptmerkmal von SBFs ist jedoch ihre Fähigkeit, mehrere Sets in einer einzigen Datenstruktur zu speichern , wodurch sie für eine Reihe unterschiedlicher Anwendungsszenarien geeignet sind. Die Zugehörigkeit eines Elements zu einer bestimmten Menge kann abgefragt werden, und die Falsch-Positiv-Wahrscheinlichkeit hängt von der Menge ab: Die ersten Mengen, die während der Konstruktion in den Filter eingegeben werden, haben höhere Falsch-Positiv-Wahrscheinlichkeiten als die am Ende eingegebenen Mengen. Diese Eigenschaft ermöglicht eine Priorisierung der Sets, wobei Sets mit "wichtigeren" Elementen erhalten bleiben können.

Mehrschichtige Bloom-Filter

Ein geschichteter Bloom-Filter besteht aus mehreren Bloom-Filterschichten. Layered Bloom-Filter ermöglichen es, zu verfolgen, wie oft ein Element zum Bloom-Filter hinzugefügt wurde, indem überprüft wird, wie viele Layer das Element enthalten. Bei einem mehrschichtigen Bloom-Filter gibt eine Prüfoperation normalerweise die Nummer der tiefsten Ebene zurück, in der das Element gefunden wurde.

Abgeschwächte Bloom-Filter

Beispiel eines abgeschwächten Bloomfilters: Suche nach Muster 11010, beginnend mit Knoten n1.

Ein abgeschwächter Bloom-Filter der Tiefe D kann als eine Anordnung von D normalen Bloom-Filtern angesehen werden. Im Kontext der Diensterkennung in einem Netzwerk speichert jeder Knoten lokal reguläre und abgeschwächte Bloom-Filter. Der reguläre oder lokale Bloom-Filter zeigt an, welche Dienste vom Knoten selbst angeboten werden. Der abgeschwächte Filter der Stufe i zeigt an, welche Dienste auf Knoten gefunden werden können, die i-Hops vom aktuellen Knoten entfernt sind. Der i-te Wert wird konstruiert, indem eine Vereinigung lokaler Bloom-Filter für Knoten-i-Hops vom Knoten entfernt wird.

Nehmen wir als Beispiel ein kleines Netzwerk, das in der folgenden Grafik dargestellt ist. Angenommen, wir suchen nach einem Dienst A, dessen ID in die Bits 0, 1 und 3 hasht (Muster 11010). Sei n1 Knoten der Startpunkt. Zuerst prüfen wir, ob Service A von n1 angeboten wird, indem wir seinen lokalen Filter prüfen. Da die Muster nicht übereinstimmen, überprüfen wir den abgeschwächten Bloom-Filter, um zu bestimmen, welcher Knoten der nächste Hop sein soll. Wir sehen, dass n2 keinen Dienst A anbietet, sondern auf dem Weg zu Knoten liegt, die dies tun. Daher gehen wir zu n2 und wiederholen das gleiche Verfahren. Wir stellen schnell fest, dass n3 den Service anbietet und somit das Ziel lokalisiert ist.

Durch die Verwendung von abgeschwächten Bloom-Filtern, die aus mehreren Schichten bestehen, können Dienste in mehr als einer Sprungdistanz entdeckt werden, während eine Sättigung des Bloom-Filters durch Abschwächen (Herausschieben) von Bits vermieden wird, die von weiter entfernten Quellen gesetzt werden.

Suche nach chemischen Strukturen

Bloom-Filter werden häufig verwendet, um große Datenbanken mit chemischen Strukturen zu durchsuchen (siehe chemische Ähnlichkeit ). Im einfachsten Fall sind die dem Filter hinzugefügten Elemente (in diesem Feld Fingerabdruck genannt) nur die im Molekül vorhandenen Ordnungszahlen oder ein Hash basierend auf der Ordnungszahl jedes Atoms und der Anzahl und Art seiner Bindungen. Dieser Fall ist zu einfach, um nützlich zu sein. Fortschrittlichere Filter codieren auch Atomzahlen, größere Substrukturmerkmale wie Carboxylgruppen und Grapheigenschaften wie die Anzahl der Ringe. Bei Hash-basierten Fingerabdrücken wird eine auf Atom- und Bindungseigenschaften basierende Hash-Funktion verwendet, um einen Teilgraphen in einen PRNG- Seed zu verwandeln , und die ersten Ausgabewerte werden verwendet, um Bits im Bloom-Filter zu setzen.

Molekulare Fingerabdrücke begannen in den späten 1940er Jahren, um nach chemischen Strukturen auf Lochkarten zu suchen. Es dauerte jedoch bis etwa 1990, bis Daylight Chemical Information Systems, Inc. eine Hash-basierte Methode zur Generierung der Bits einführte, anstatt eine vorberechnete Tabelle zu verwenden. Im Gegensatz zum Dictionary-Ansatz kann die Hash-Methode Bits für Unterstrukturen zuweisen, die zuvor nicht gesehen wurden. In den frühen 1990er Jahren wurde der Begriff "Fingerabdruck" als anders angesehen als "Strukturschlüssel", aber der Begriff umfasst seitdem die meisten molekularen Merkmale, die für einen Ähnlichkeitsvergleich verwendet werden können, einschließlich Strukturschlüssel, Fingerabdrücke mit geringer Anzahl und 3D-Fingerabdrücke . Im Gegensatz zu Bloom-Filtern ermöglicht die Daylight-Hash-Methode, dass die Anzahl der pro Feature zugewiesenen Bits eine Funktion der Feature-Größe ist, aber die meisten Implementierungen von Daylight-ähnlichen Fingerabdrücken verwenden eine feste Anzahl von Bits pro Feature, was sie zu einem Bloom-Filter macht. Die ursprünglichen Daylight-Fingerabdrücke könnten sowohl für Ähnlichkeits- als auch für Screening-Zwecke verwendet werden. Viele andere Fingerabdrucktypen, wie der beliebte ECFP2, können zur Ähnlichkeit, aber nicht zum Screening verwendet werden, da sie lokale Umgebungsmerkmale beinhalten, die bei der Verwendung als Screen zu falschen Negativen führen. Auch wenn diese mit dem gleichen Mechanismus aufgebaut sind, sind dies keine Bloom-Filter, da sie nicht zum Filtern verwendet werden können.

Siehe auch

• Count-Minute-Skizze
• Feature-Hashing
• MinHash
• Quotientenfilter
• Liste überspringen
• Bloomfilter in der Bioinformatik
• Kuckucksfilter

Anmerkungen

Verweise

Externe Links

• "Verwenden von Bloom-Filtern" Detaillierte Erklärung des Bloom-Filters mit Perl
• Warum Bloom-Filter so funktionieren, wie sie es tun (Michael Nielsen, 2012)
• Bloom Filters — A Tutorial, Analysis and Survey (Blustein & El-Maazawi, 2002) an der Dalhousie University
• Tabelle der falsch-positiven Raten für verschiedene Konfigurationen von einer Website der University of Wisconsin-Madison
• "More Optimal Bloom Filters", Ely Porat (Nov/2007) Google TechTalk-Video auf YouTube