Bloom Filter und perfektes Hashing

Ein Bloom-Filter verwendet eine Hash-Funktion, um die Mitgliedschaft in einem bestimmten Satz zu testen , indem überprüft wird, ob ein Element vorhanden ist oder nicht an der angegebenen Position. $S$

Um den Effekt der Hash-Kollision abzuschwächen, werden mehrere Funktionen verwendet, die bei Verwendung von universellem Hash eine Wahrscheinlichkeitsgrenze ergeben.

Wir können 10 Bits pro Element verwenden, um eine "angemessene" Fehlerrate zu erzielen.

Wenn wir direkt eine perfekte Hash-Funktion für die Menge erstellen könnten , wobei das letzte Element in nicht vorhanden ist , könnten wir nur 1 Bit pro Element verwenden und eine perfekte Wiederherstellung erzielen. $S + \infty$ $S$

Was sind die fundamentalen Gründe, warum diese Argumentation falsch ist?

data-structures hash probabilistic-algorithms bloom-filters dictionaries nicolas
quelle

Wie groß ist und warum sind 10 Bits "vernünftig"?

S

$S$

Pål GD

Warum sollte die Größe S ins Spiel kommen? Mir könnte etwas fehlen.

Nicolas

Warum denkst du, stimmt etwas mit deiner Argumentation nicht?

JeffE

@JeffE Es wäre seltsam, eine enorme Platzersparnis zu finden, wenn die von Bloom Filter erkannte Qualität seine Sparsamkeit ist. Sie stützen sich jedoch auf universelle Hash-Funktionen, was möglicherweise nicht überraschend ist. Ich denke, im Extremfall hat die Länge des Programms, die zur Beschreibung des Hashs benötigt wird, selbst etwas Kolmogorov (?) Gebunden, das die Wirksamkeit einschränkt. Wenn wir eine Funktion finden würden, die "besser" gehasht wird, würde dies wahrscheinlich nachweislich zu einigen Programmplatzkosten führen, die die Gewinne ausgleichen. aber ich weiß nichts davon, daher meine Frage ...

Nicole

Ihre Argumentation ist vollkommen richtig. Sie können eine perfekte Wiederherstellung mit nur einem Bit pro Element mit einer perfekten Hash-Funktion erzielen. Die resultierende Datenstruktur wäre völlig nutzlos, da die Auswertung einer perfekten Hash-Funktion zu lange dauern würde, aber viel Platz sparen würde !

JeffE

Antworten:

Ich denke, Ihre Argumentation ist im Prinzip richtig. Perfektes Hashing ist eine Alternative zu Bloom-Filtern. Klassisches dynamisches perfektes Hashing ist jedoch eher ein theoretisches Ergebnis als eine praktische Lösung. Kuckuck-Hashing ist wahrscheinlich die "vernünftigere" Alternative.

Beachten Sie, dass sowohl dynamisches perfektes Hashing als auch Standard-Kuckuck-Hashing nur amortisiert erwartet werden (möglicherweise müssen Sie die Datenstruktur von Zeit zu Zeit vollständig neu erstellen). Auch Bloom-Filter sind einfacher zu implementieren. Dies können Argumente für die Verwendung eines Bloom-Filters sein, insbesondere wenn Sie mit falsch positiven Ergebnissen leben können.

A.Schulz
quelle

Ich denke, der Bloom-Filter bietet Ihnen etwas, was die perfekte Hash-Funktion nicht bietet - er kann die Mitgliedschaft testen.

Die PHFs, die ich kenne, geben eine Antwort für jeden Schlüssel zurück, auf den Sie sie anwenden. Wenn der von Ihnen angegebene Schlüssel nicht in Ihrem Hash-Set enthalten ist, wird immer noch ein Wert angegeben. Dies ist in Ordnung, wenn Sie alle Schlüssel in Ihrem Set irgendwo speichern und der PHF nur einen Zeiger gibt, oder wenn Sie den PHF nur zum Nachschlagen von Satellitendaten der Größe auf Schlüsseln verwenden, die Sie gerade verwenden weiß, in deiner Struktur zu sein. Das Testen der Mitgliedschaft ist jedoch schwieriger. $O(1)$

Insbesondere erfordert das fehlerfreie Speichern von verschiedenen Elementen Speicherbits. $n$ $n \log_2 n$

jbapple
quelle