Gibt es einen Anti-Bloom-Filter?

25

Mit einem Bloom-Filter können Sie effizient verfolgen, ob während der Verarbeitung bereits verschiedene Werte festgestellt wurden. Wenn viele Datenelemente vorhanden sind, kann ein Bloom-Filter zu einer erheblichen Speichereinsparung über eine Hash-Tabelle führen. Das Hauptmerkmal eines Bloom-Filters, das es mit einer Hash-Tabelle teilt, ist, dass es immer "nicht neu" sagt, wenn ein Element nicht neu ist, aber es besteht eine Wahrscheinlichkeit ungleich Null, dass ein Element als "nicht neu" gekennzeichnet wird "auch wenn es neu ist.

Gibt es einen "Anti-Bloom-Filter", der das gegenteilige Verhalten aufweist?

Mit anderen Worten: Gibt es eine effiziente Datenstruktur, die "neu" sagt, wenn ein Artikel neu ist, aber für einige Artikel, die nicht neu sind, auch "neu" sagt?

Das Beibehalten aller zuvor angezeigten Elemente (beispielsweise in einer sortierten verknüpften Liste) erfüllt die erste Anforderung, beansprucht jedoch möglicherweise viel Speicher. Ich hoffe, dass es angesichts der entspannten zweiten Anforderung auch unnötig ist.


Für diejenigen, die eine formalere Behandlung bevorzugen, schreiben Sie b(x)=1 wenn der Bloom-Filter x für neu hält, b(x)=0 , und schreiben Sie n(x)=1 wenn x wirklich neu ist und n(x)=0 sonst.

Dann Pr[b(x)=0|n(x)=0]=1 ; Pr[b(x)=0|n(x)=1]=α ; Pr[b(x)=1|n(x)=0]=0; , für einige .0 < α < 1Pr[b(x)=1|n(x)=1]=1α0<α<1

Ich frage: Existiert eine effiziente Datenstruktur, die eine Funktion mit etwas implementiert , so dass ; ; ; & le; 0 < β < 1 P r [ b ' ( x ) = 0 | n ( x ) = 0 ] = β P r [ b ' ( x ) = 0 | n ( x ) = 1 ] = 0 P r [ b ' ( x ) = 1 | n ( xb0<β<1Pr[b(x)=0|n(x)=0]=βPr[b(x)=0|n(x)=1]=0P r [ b ' ( x ) = 1 | n ( x ) = 1 ] = 1Pr[b(x)=1|n(x)=0]=1βPr[b(x)=1|n(x)=1]=1


Bearbeiten: Es scheint, dass diese Frage zuvor bei StackExchange gestellt wurde, da /programming/635728 und /cstheory/6596 mit einer Reihe von Antworten von "kann nicht sein" done "through" kann mit einigem Aufwand "to" durchgeführt werden, indem die Werte von umgekehrt werden b". Mir ist noch nicht klar, was die "richtige" Antwort ist. Es ist klar, dass ein LRU-Caching-Schema (wie das von Ilmari Karonen vorgeschlagene) ziemlich gut funktioniert, einfach zu implementieren ist und die Zeit für die Ausführung meines Codes um 50% verkürzt.

András Salamon
quelle
Aus irgendeinem Grund bin ich versucht zu sagen, dass dies dem Problem, das Caches und Cache-Platzierungsalgorithmen zu lösen versuchen, sehr ähnlich ist. Betrachten Sie einen Cache mit LFU-Ersatz (Least Frequently Used Replacement). Ein theoretisch optimaler, aber unmöglicher Ersetzungsalgorithmus besteht darin, den Algorithmus zu entfernen, den Sie am längsten nicht mehr sehen werden, genau wie bei Caches. Ich nehme an, dass das Caching von einigen Annahmen über die Art der Verteilung abhängt, die im Allgemeinen möglicherweise nicht zutreffen, aber es lohnt sich zu überlegen, ob dies zutrifft.
Patrick87
Der folgende Vortrag könnte Sie auch interessieren: Auf Zufriedenheit basierende gesetzte Mitgliedschaftsfilter
Kaveh
@Kaveh: danke für den Zeiger, werde zuschauen.
András Salamon

Antworten:

12

Passend zur Hash-Idee von Patrick87 finden Sie hier eine praktische Konstruktion, die fast Ihren Anforderungen entspricht - die Wahrscheinlichkeit, einen neuen Wert fälschlicherweise mit einem alten zu verwechseln, ist nicht ganz null, kann aber leicht vernachlässigbar klein gemacht werden.

Wählen Sie die Parameter und k ; praktische Werte könnten beispielsweise n = 128 und k = 16 sein . Sei H eine sichere kryptographische Hash-Funktion , die (mindestens) n + k Ausgabebits erzeugt.nkn=128k=16Hn+k

Lassen ein Array von Be 2 k n -Bit bitstrings. Dieses Array speichert den Zustand des Filters mit insgesamt n 2 k Bits. (Es ist nicht besonders wichtig, wie dieses Array initialisiert wird. Wir können es einfach mit Nullen oder mit zufälligen Bits füllen.)a2k nn2k

  • Um dem Filter einen neuen Wert hinzuzufügen , berechnen Sie ix , wobei i die ersten k Bits und j die folgenden n Bits von H ( x ) bezeichnet . Sei a i = j .ij=H(x)ikjnH(x)ai=j

  • Um zu testen, ob dem Filter ein Wert hinzugefügt wurde, berechnen Sie i '.x , wie oben, und überprüfe, ob a i ' = j ' ist . Wenn ja, geben Sie true zurück. Andernfalls wird false zurückgegeben.ij=H(x)ai=j

Anspruch 1: Die Wahrscheinlichkeit eines falsch - positiven (= fälschlich neuen Wert beansprucht gesehen worden war) wird . Dies kann durch Erhöhen von n zu bescheidenen Kosten des Speicherplatzes beliebig klein gemacht werden ; Insbesondere ist diese Wahrscheinlichkeit für n 128 im Wesentlichen vernachlässigbar und in der Praxis viel geringer als die Wahrscheinlichkeit eines falschen Positivs aufgrund einer Hardwarefehlfunktion.1/2n+knn128

Insbesondere beträgt , nachdem verschiedene Werte geprüft und dem Filter hinzugefügt wurden, die Wahrscheinlichkeit, dass mindestens ein falsches Positiv aufgetreten ist, ( N 2 - N ) / 2 n + k + 1 . Zum Beispiel beträgt bei n = 128 und k = 16 die Anzahl der eindeutigen Werte, die erforderlich sind, um ein falsches Positiv mit einer Wahrscheinlichkeit von 50% zu erhalten, ungefähr 2 ( n + k ) / 2 = 2 72 .N(N2N)/2n+k+1n=128k=162(n+k)/2=272

Behauptung 2: Die Wahrscheinlichkeit eines falsch negativen (= früher fälschlicherweise als neu geltend gemachten Mehrwerts) ist nicht größer als wobei N die Anzahl der dem Filter hinzugefügten eindeutigen Werte ist (oder genauer gesagt die Anzahl der eindeutigen Werte, die hinzugefügt wurden, nachdem der zu testende spezifische Wert zuletzt dem Filter hinzugefügt wurde).1(12k)N1exp(N/2k)<N/2kN


Ps. Um "vernachlässigbar klein" ins rechte Licht zu rücken, gilt die 128-Bit-Verschlüsselung mit der derzeit bekannten Technologie im Allgemeinen als unzerbrechlich . Ein falsches Positiv aus diesem Schema mit ist so wahrscheinlich, als würde jemand Ihren geheimen 128-Bit-Verschlüsselungsschlüssel beim ersten Versuch richtig erraten . (Mit n = 128 und k = 16 ist die Wahrscheinlichkeit ungefähr 65.000-mal geringer.)n+k=128n=128k=16

Aber wenn Sie sich dadurch immer noch irrational nervös fühlen, können Sie jederzeit auf umschalten . Es wird Ihren Speicherbedarf verdoppeln, aber ich kann mit Sicherheit sagen, dass niemand jemals ein falsches Positiv mit n = 256 sehen wird - vorausgesetzt, die Hash-Funktion ist ohnehin nicht defekt.n=256n=256

Ilmari Karonen
quelle
1
Die Wahrscheinlichkeit kann nicht nur mit der von Hardwarefehlern vergleichbar gemacht werden. Dies kann auch mit der Wahrscheinlichkeit verglichen werden, dass jemand beim ersten Versuch Ihren RSA-Schlüssel für die SSH-Anmeldung errät . IMO das letztere vermittelt die praktische Anwendbarkeit Ihrer Lösung mehr als das erstere.
R ..
+1 Sehr schön - ich verstehe, dass dies das Raumeffizienzproblem löst, indem eine (sehr geringe) Wahrscheinlichkeit besteht, dass "nicht neu" falsch beantwortet wird, wenn der Artikel tatsächlich neu ist. Sehr praktisch und gute Analyse.
Patrick87
1
Behauptung 1 besagt lediglich, dass eine anständige Hash-Funktion eine geringe Wahrscheinlichkeit von Kollisionen aufweist. Dies gilt in der Praxis bereits dann, wenn mindestens 50 beträgt. Für meine Anwendung funktionieren n = 44 und k = 20 hervorragend mit einer einfachen, nicht kryptografisch sicheren, aber schnellen 64-Bit-Hash-Funktion. n+kn=44k=20
András Salamon
@ AndrásSalamon: Stimmt, obwohl eine sichere kryptografische Hash-Funktion tatsächlich eine etwas stärkere Garantie bietet: Es ist nämlich unpraktisch, kollidierende Eingaben zu finden, selbst wenn Sie versuchen, sie absichtlich zu suchen. Mit einem ausreichend großen (z. B. n = 128, wie oben vorgeschlagen) bedeutet dies, dass das Speichern der vollständigen Daten unnötig ist, selbst wenn die Kosten für ein falsches Positiv hoch sind und selbst wenn ein aktiver Gegner versucht, eines zu finden. Wenn Sie eine nicht ganz so starke Garantie benötigen, kann natürlich ein etwas höheres Kollisionsrisiko in Kauf genommen werden. nn=128
Ilmari Karonen
1
@Newtopian Der Grund, warum ich eine kryptografische Hash-Funktion angegeben habe, ist, dass es für diese keine Möglichkeit gibt, Kollisionen effektiver als mit Brute Force zu generieren (dh durch Testen vieler Eingaben und Auswählen derjenigen, die kollidieren), oder dass der Hash in Betracht gezogen wird kaputt (wie zum Beispiel MD5 heutzutage ist). Somit können wir für einen kryptografischen Hash ziemlich sicher annehmen, dass die Kollisionsrate dieselbe ist wie für eine ideale zufällige Hash-Funktion. Die Verwendung einer universellen Hash-Funktion oder eines verschlüsselten MAC (mit einem zufälligen geheimen Schlüssel) würde diese Garantie noch verstärken.
Ilmari Karonen
8

Nein, es ist nicht möglich, eine effiziente Datenstruktur mit diesen Eigenschaften zu haben, wenn Sie die Garantie haben möchten, dass die Datenstruktur "neu" sagt, wenn sie wirklich neu ist (wenn nicht, wird sie niemals "nicht neu" sagen) es ist in der Tat neu; keine falschen Negative erlaubt). Jede solche Datenstruktur muss alle Daten enthalten, um jemals "nicht neu" zu antworten. Siehe pents90 Antwort auf cstheory für eine präzise Begründung.

Im Gegensatz dazu Bloom Filter können eine Garantie erhalten , dass die Datenstruktur sagt „nicht neu“ , wenn es nicht neu ist, auf effiziente Art und Weise. Insbesondere können Bloom-Filter effizienter sein als das Speichern aller Daten: Jedes einzelne Element ist möglicherweise recht lang, aber die Größe des Bloom-Filters richtet sich nach der Anzahl der Elemente und nicht nach ihrer Gesamtlänge. Jede Datenstruktur für Ihr Problem muss mit der Gesamtlänge der Daten skaliert werden, nicht mit der Anzahl der Datenelemente.

Apfel
quelle
Siehe auch die akzeptierte Antwort, da es die gleiche Frage gibt
Joe
-1 Sie sollten sich wahrscheinlich qualifizieren, was Sie meinen, wenn Sie sagen, dass dies nicht möglich ist. Natürlich ist es möglich, dies effizient und mit einer geringen Fehlerrate zu tun. Daher sollte es machbar sein, ein gewisses Gleichgewicht in einer bestimmten Implementierung zu finden. Insbesondere wäre es nützlich, genau zu erklären, was damit gemeint ist "Alle Daten aller Zeiten", da dies nicht unbedingt erforderlich ist, um die Frage zu beantworten. Falschnegative - Antworten "neu", wenn die Antwort "nicht neu" sein soll - sind hier zulässig, sodass nicht alle Daten gespeichert werden müssen.
Patrick87
1
Diese Antwort ist völlig vernünftig und scheint den Brief meiner Frage zu beantworten, aber vielleicht nicht den Geist.
András Salamon
@ DW Vielen Dank, dass Sie sich die Zeit genommen haben, die Antwort zu aktualisieren. Ich bin geneigt, dies jetzt als Antwort zu lassen, obwohl ich immer noch Einwände gegen die Sprache habe, die bei der Beschreibung der Ineffizienz von Anti-Bloom-Filtern verwendet wird. Zusätzlich zu der Überlegung, dass es am besten ist, die "Details", auf die verwiesen wird, etwas genauer zu erläutern. .. Verlassen Sie die -1 für jetzt. Einige veraltete Kommentare wurden entfernt.
Patrick87
@DW Mit "falsch negativ" möchte ich "neu" antworten, wenn die Antwort "nicht neu" hätte sein sollen. (Irgendwie ist "nicht neu" hier der positive Fall.) Sie müssen nicht "alle Daten jemals" speichern, um dies abzurufen, obwohl ich zu der Annahme neige, dass Sie ganze Elemente (nur) speichern müssen nicht alle Elemente - es sei denn, Sie sind bereit, eine hypothetisch bedeutsame Fehlerwahrscheinlichkeit zu akzeptieren, wie in der anderen Antwort auf die Frage hier angegeben.)
Patrick87
6

Was ist mit nur einem Hash-Tisch? Wenn Sie ein neues Element sehen, überprüfen Sie die Hash-Tabelle. Wenn die Stelle des Artikels leer ist, geben Sie "neu" zurück und fügen Sie den Artikel hinzu. Andernfalls prüfen Sie, ob die Stelle des Artikels mit dem Artikel belegt ist. Wenn ja, geben Sie "nicht neu" zurück. Wenn die Stelle mit einem anderen Gegenstand belegt ist, geben Sie "neu" zurück und überschreiben Sie die Stelle mit dem neuen Gegenstand.

Sie erhalten auf jeden Fall immer "Neu", wenn Sie den Hash des Artikels noch nie zuvor gesehen haben. Sie erhalten auf jeden Fall immer "Nicht neu", wenn Sie den Hash des Artikels nur gesehen haben, als Sie den gleichen Artikel gesehen haben. Das einzige Mal, dass Sie "Neu" erhalten, wenn die richtige Antwort "Nicht neu" lautet, ist, wenn Sie Artikel A sehen, dann Artikel B sehen, dann Artikel A erneut sehen und A und B auf dasselbe gehasht haben. Wichtig ist, dass Sie niemals "Nicht neu" falsch erhalten können.

Patrick87
quelle
1
Ich nehme an, diese Art von ignoriert das Problem der Raumeffizienz oder ist wesentlich weniger effizient als ein Bloom-Filter, da ein Bloom-Filter wirklich nur ein bisschen pro Bucket benötigt und dies so viel Platz pro Bucket benötigt, wie es Platz braucht repräsentieren die Elemente. Na ja ... es sei denn, das Universum ist endlich (wie in der Antwort von Wandering Logic). Ich denke, Sie können der Raumeffizienz eines Blütenfilters wahrscheinlich nicht sehr nahe kommen.
Patrick87
Persönlich denke ich, dass Ihre Antwort viel besser ist als meine. Ein Bloom-Filter ist nicht nur ein bisschen pro Bucket, wenn Sie Wahrscheinlichkeiten von mehr als 50% wünschen. Es ist auch eine feste Größe und sobald Sie es mehr als halb voll füllen, steigt die Wahrscheinlichkeit von falsch positiven Ergebnissen steil an. Es gibt keine bequeme Möglichkeit, es zu erweitern, keine bequeme Möglichkeit, es als Cache zu verwenden und keine bequeme Möglichkeit, Elemente zu löschen. Ich werde jedes Mal einen Hash-Tisch nehmen .
Wandering Logic
@WanderingLogic Durch die Verwendung eines kleinen Sättigungszählers anstelle eines einzelnen Bits kann das Löschen unterstützt werden (auf Kosten der Kapazität und natürlich nur, wenn der Zähler nicht maximal ist).
Paul A. Clayton
4

Wenn das Universum der Elemente endlich ist, dann ja: Verwenden Sie einfach einen Bloom-Filter, der aufzeichnet, welche Elemente nicht in der Menge, sondern in der Menge enthalten sind. (Verwenden Sie also einen Bloom-Filter, der das Komplement des interessierenden Satzes darstellt.)

Ein Ort, an dem dies nützlich ist, besteht darin, eine begrenzte Form des Löschens zuzulassen. Sie behalten zwei Blütenfilter. Sie fangen leer an. Wenn Sie Elemente einfügen, fügen Sie sie in Bloom-Filter A ein. Wenn Sie später ein Element löschen möchten, fügen Sie dieses Element in Bloom-Filter B ein. Es gibt keine Möglichkeit, die Löschung rückgängig zu machen. Um eine Suche durchzuführen, müssen Sie zuerst in Bloom-Filter A nachschlagen. Wenn Sie keine Übereinstimmung finden, wurde der Artikel nie eingefügt (mit Wahrscheinlichkeit 1). Wenn Sie eine Übereinstimmung finden, wurde das Element möglicherweise (oder möglicherweise nicht) eingefügt. In diesem Fall führen Sie eine Suche in Bloom-Filter B durch. Wenn Sie keine Übereinstimmung finden, wurde der Artikel nie gelöscht. Wenn Sie in Bloom-Filter B eine Übereinstimmung finden, wurde der Artikel wahrscheinlich eingefügt und dann gelöscht.

Dies beantwortet Ihre Frage nicht wirklich, aber in diesem begrenzten Fall führt der Bloom-Filter B genau das "Anti-Bloom-Filter" -Verhalten aus, das Sie suchen.

Real Bloom filter researchers use much more efficient ways of representing deletion, see Mike Mitzenmacher's publication's page.

Wandering Logic
quelle
In dieser Frage verarbeiten wir Elemente und es gibt keine Löschvorgänge. Es gibt keine sinnvolle Möglichkeit, das Kompliment aufzubewahren, ohne Gegenstände aus dem Blütenfilter entfernen zu müssen
Joe,
1
@ Joe: Ich stimme zu, dass das Problem im Allgemeinen unlösbar ist. Daher beschränkte ich meine Antwort auf den Fall, in dem das Komplement endlich und klein war.
Wandering Logic
1

Ich möchte hier nur hinzufügen, dass Sie, wenn Sie sich in einer glücklichen Situation befinden, alle Werte kennen vichdass Sie möglicherweise sehen könnten; Dann können Sie einen Zählblütenfilter verwenden.

Ein Beispiel könnten IP-Adressen sein, und Sie möchten jedes Mal wissen, wenn eine solche Adresse erscheint, die Sie noch nie gesehen haben. Aber es ist immer noch eine endliche Menge, sodass Sie wissen, was Sie erwarten können.

Die eigentliche Lösung ist einfach:

  1. Fügen Sie alle Ihre Artikel dem Zählblütenfilter hinzu.
  2. Wenn Sie ein neues Objekt sehen, hat es Werte 1 in allen Steckplätzen.
  3. Nachdem Sie ein aktuelles neues Element gesehen haben, subtrahieren Sie es vom Filter.

Es kann also sein, dass Sie "falsch-positive" Werte haben, die zwar alt, aber als neu erkannt wurden. Sie werden jedoch für einen neuen Wert niemals "nicht neu" erhalten, da sein Wert immer noch in allen Slots vorhanden ist, und niemand anderes hätte ihn wegnehmen können.

Thomas Ahle
quelle