Ein probabilistischer Satz ohne Fehlalarme?

35

So Bloom Filter sind ziemlich cool - sie sind Sätze , dass die Unterstützung der Mitglieder ohne falsche Negative Kontrolle, aber eine kleine Chance eines falsch positiven Ergebnisses . Kürzlich wollte ich jedoch einen "Bloom-Filter", der das Gegenteil garantiert: keine falschen Positiven, sondern potenziell falsche Negative.

Meine Motivation ist einfach: Angesichts einer großen Anzahl von zu verarbeitenden Elementen (mit Duplikaten) möchten wir vermeiden, Elemente zu verarbeiten, die wir zuvor gesehen haben. Es tut nicht weh, ein Duplikat zu verarbeiten, es ist nur Zeitverschwendung. Wenn wir es versäumen, ein Element zu verarbeiten, wäre dies katastrophal. Mit einem "Reverse Bloom-Filter" könnte man die mit geringem Platzaufwand gesehenen Objekte speichern und vermeiden, dass Duplikate mit hoher Wahrscheinlichkeit verarbeitet werden, indem man auf Mitgliedschaft in der Gruppe prüft.

Trotzdem kann ich nichts dergleichen finden. Das nächstliegende, was ich gefunden habe, sind " retuschierte Bloom-Filter ", mit denen man ausgewählte falsch-positive Ergebnisse gegen eine höhere falsch-negative Rate eintauschen kann. Ich weiß jedoch nicht, wie gut ihre Datenstruktur funktioniert, wenn man alle Fehlalarme entfernen möchte .

Hat jemand so etwas gesehen? :)

Christopher Monsanto
quelle
3
Die Ergänzung des Sets, an dem ich interessiert bin, ist unendlich. Wie würde ich es aufbewahren?
Christopher Monsanto
11
Ich sehe das Problem (moderne Festplatten sind noch nicht groß genug).
Dave Clarke
8
Wenn Sie eine solche Datenstruktur hätten, könnten Sie sie verwenden, um zu "schummeln", indem Sie sie in Verbindung mit einem regulären Bloom-Filter verwenden und die genau festgelegte Mitgliedschaft speichern.
Mark Reitblatt
1
@MarkReitblatt Sowohl Bloom-Filter als auch Caches sind probabilistisch, und jede Kombination davon ist probabilistisch, dh nicht in der Lage, einen exakten Satzzugehörigkeitstest durchzuführen. :)
awdz9nld

Antworten:

25

Eine Antwort ist, eine große Hash-Tabelle zu verwenden und, wenn sie voll ist, die darin enthaltenen Elemente zu ersetzen, anstatt für sie an anderer Stelle (nicht vorhandene) leere Slots zu finden. Sie erhalten nicht die schöne feste Rate falscher Antworten, die Sie mit Bloom-Filtern erhalten, aber es ist besser als nichts. Ich glaube, dies ist Standard, zB in Schachsoftware, um Positionen zu verfolgen, die bereits gesucht wurden.

David Eppstein
quelle
Danke für die Antwort. Ja, das ist die offensichtliche Lösung - wenn es auch die Standardlösung ist, klingt es so, als hätte ich Pech. Naja.
Christopher Monsanto
2
Dies wird als direkt zugeordneter Cache bezeichnet und wird häufig in CPUs verwendet. (Jeder Cache oder jede verlustbehaftete Hash-Menge erfüllt die Anforderungen in unterschiedlichem Maße.) Die Fehlerrate ist eine Funktion der Verteilung der Hash-Funktion (Lawine) und der Anzahl der im Cache / Set verfügbaren Slots - passen Sie sie entsprechend an. :)
awdz9nld
Beachten Sie auch, dass nur wörtliche Schlüssel gespeichert werden können, ohne dass falsche Positive eingegeben werden (z. B. Speichern eines Hash-Schlüssels)
awdz9nld 13.06.12
20

Die Antwort auf diese Frage lautet "nein". Um zu sehen, warum, können wir über einen extremen Fall nachdenken und wie ein regulärer Bloom-Filter im Vergleich zu einem theoretischen "Bizzaro World" Bloom-Filter, den wir "Gloom-Filter" nennen können, funktionieren würde.

Das Besondere an einem Bloom-Filter ist, dass Sie einseitige Tests für die Zugehörigkeit von Elementen (mit falsch positiven Ergebnissen) mithilfe einer Datenstruktur durchführen können, die eine feste Größe in Bezug auf die Fehlerwahrscheinlichkeit und die Anzahl der gespeicherten Elemente aufweist. Die Größe der Artikel selbst spielt keine Rolle. Wenn zum Beispiel ein Bloom-Filter eingerichtet wäre, um bis zu 1.000 Elemente mit weniger als 3% Fehler zu speichern, könnten 1.000 leicht unterschiedliche Versionen des gesamten Wikipedia-Korpus mit jeweils einem geänderten Buchstaben gespeichert werden Holen Sie sich die gewünschten Metriken, und die Datenstruktur wäre sehr klein (weniger als ein Kilobyte). Natürlich wird das Berechnen dieser Hashes eine Herausforderung sein, aber das Prinzip bleibt bestehen.

Ziehen Sie nun in Betracht, dieselben massiven Zeichenfolgen in einem dunklen Filter zu speichern! Wir können jetzt nur falsche Negative haben. Wenn wir also sagen "Ja, diese Version des gesamten Wikipedia-Korpus ist in diesem Set", dann müssen wir absolut Recht haben. Das heißt, Hashing hilft uns nicht weiter, da es immer eine andere Zeichenfolge gibt, die auf den gleichen Wert hasht. Die einzige Möglichkeit, "Ja" zu sagen und sicher zu sein, besteht darin, die gesamte Zeichenfolge oder einige äquivalente Daten derselben Länge zu speichern. Wir konnten es immer nicht speichern und "nein" sagen, aber irgendwann wird uns die Fehlerrate einholen. Das Beste, was wir tun können, ist die Komprimierung, bei der die Größe der Struktur auf das Produkt aus der Entropie der gespeicherten Daten und der von uns gewünschten Genauigkeit reduziert wird.

Leider gibt es den Düsternisfilter nicht. Zwischenspeichern ist die einzige Lösung, aber es ist nicht wirklich das Gegenteil eines Bloom-Filters, da seine Größe proportional zum Produkt aus der Menge der gespeicherten Informationen und der gewünschten Genauigkeitsrate des Filters ist. Natürlich können in vielen realen Szenarien große Datenmengen durch eine ID dargestellt werden, sodass das Zwischenspeichern immer noch akzeptabel ist. Aber es ist grundlegend anders als der mächtige Blütenfilter.

pents90
quelle
checkout somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - was ist los mit dieser Implementierung /
Yehosef
@Yehosef es ist in Ordnung und funktioniert möglicherweise für Ihre Bedürfnisse, aber Sie werden feststellen, dass der Autor davon spricht, dass es einige "IDs gibt, die das Ereignis vollständig identifizieren". Also, was implementiert wird, ist effektiv immer noch das gesamte Objekt zu speichern. Es ist also eine Variante eines Caches. Ein echtes "Gegenteil eines Blütenfilters", wenn es existiert, müsste nicht ganze Objekte speichern.
pents90
Er erwähnte einige Kennungen, die das Ereignis identifizieren - nicht das gesamte Objekt. Ich muss nur den "Cache" in der session_id behalten - nicht den gesamten Interaktionsdatensatz. Aber ich höre, dass es nicht die gleiche Art der Annäherung wie die Blüte oder ein Hyperlog ist.
Yehosef
In Ihrem "Beweis" gehen Sie davon aus, dass es eine unbegrenzte Anzahl von möglichen Einträgen gibt. Es gibt jedoch Fälle, in denen die Menge der möglichen Einträge im Voraus bekannt ist. Zum Beispiel für die Speicherbereinigung einer Speicherseite: Sie wissen, welche Einträge sie enthält. Jetzt erstellen Sie einen "düsteren Filter", der jeden möglichen Eintrag einem Index 0..n zuordnet. Wenn ein Eintrag entfernt wird, setzen Sie das Bit auf diesen Index. Wenn alle Bits gesetzt sind, können Sie die Seite müllsammeln. Der "Düsterfilter" ist ein MPHF. Ändern Sie den MPHF so, dass einige Einträge auf n + 1 abgebildet werden, um falsch negative Ergebnisse zuzulassen.
Thomas Mueller
@ThomasMueller Richtig, ich gehe vom Worst-Case / Adversarial-Fall aus, der aus Sicht der CS-Theorie Standard ist. Wenn Sie nur eine feste Anzahl von N möglichen Einträgen haben, gibt es viele einfache Lösungen, bei denen nur N Speicherplatz für jedes Element erforderlich ist. Der Bloom-Filter unterliegt jedoch keinen derartigen Einschränkungen.
pents90
13

Sie möchten nur einen Cache , denken aber auf seltsame Weise darüber nach.

Craig Gidney
quelle
1
... möchten Sie näher darauf eingehen? Natürlich würde ein Cache funktionieren, aber das ist nicht ideal, daher eine Frage zum Stand der Technik bei probabilistischen Datenstrukturen. Genauer gesagt: Ich kenne Caching-Techniken, die viel Speicherplatz benötigen. Je mehr Cache-Ebenen, desto mehr Speicher wird verwendet. Man könnte die im Cache gespeicherten Elemente einschränken, Tricks mit Nutzungsmustern ausführen usw., aber das kommt immer noch nicht in die Nähe des Verhältnisses von Raumeffizienz zu falscher Antwort, das ein Bloom-Filter bietet.
Christopher Monsanto
1
(Fortsetzung) Abgesehen davon könnte ich eine offensichtliche Caching-Technik vergessen, die alle meine Probleme löst. In diesem Fall könnten Sie diese Technik erläutern, anstatt mir einen Link zu einer allgemeinen Kategorie auf Wikipedia zu geben?
Christopher Monsanto
2

HAFTUNGSAUSSCHLUSS: Ich bin kein Cachespezialist, daher könnte dies eine naive Idee sein und auch eine bekannte Idee, von der ich noch nie zuvor gehört habe. Entschuldigen Sie mich, wenn ich den Verweis nicht zitiere (falls vorhanden). und informieren Sie mich bitte, wenn es einen Verweis dafür gibt, um den Beitrag zu bearbeiten und hinzuzufügen. (Ich vermute, es könnte eine Referenz haben, weil es so intuitiv ist).

Eine schnelle Lösung, nachdem Sie sich von Strilanc inspirieren lassen, vielleicht, um nur eine assoziative Karte des Maximums zu erstellen c Einträge (wo cist eine Konstante), die einen Gegenstand mit der Häufigkeit verknüpft, mit der er gesehen wurde. Wenn die assoziative Karte voll ist und Sie auf ein neues Objekt stoßen, das nicht in der Karte enthalten ist, werfen Sie eine Münze, um es hinzuzufügen, oder nicht. Wenn Sie es hinzufügen möchten, entfernen Sie ein Element mit einer Wahrscheinlichkeit, die umgekehrt proportional zu der Häufigkeit ist, mit der es bisher gesehen wurde.

M. Alaggan
quelle
0

Ich habe AVL-Bäume (und manchmal rot-schwarze) mit Teilelementen verwendet, um als Filter ohne falsche Negative zu fungieren. Verwenden Sie nur die ersten X Bytes des Elements, wenn Sie den Baum einfügen oder abfragen. Da die Datenstruktur in ihrer Form nicht probabilistisch ist, besteht nicht die Gefahr eines Fehlalarms durch Bitkollision. Und im Gegensatz zum Zwischenspeichern des gesamten Elements erhalten Sie auf diese Weise einen kalkulierbaren maximalen Speicherplatz. Sie können die Rate falsch positiver Ergebnisse optimieren, indem Sie unterschiedliche Präfixlängen / Baumtiefen im Vergleich zu den Kosten für falsch positive Ergebnisse und Speicherplatz berücksichtigen.

JRideout
quelle
Ich wollte auch versuchen, Versuche mit String-Daten, aber meine Daten neigen dazu, Binärstrukturen gepackt.
JRideout
0

Ich denke, man kann eine Untergrenze beweisen, die besagt, dass die obige Datenstruktur nicht existieren kann. Wenn die Datenstruktur m Bits verwendet, kann ein fester Bitvektor (Darstellung einer Eingabe) im Grunde höchstens (((un) + n eps) \ choose (un)) Mengen durch ein Zählargument entsprechen. Da das 2 ^ m-fache dieser Zahl mindestens (u \ choose n) sein muss (alle Mengen müssen dargestellt werden), erhalten wir eine Untergrenze, die im Grunde der genauen Speicherung der Menge S sehr nahe kommt.

Mayank
quelle