Bloom Filter Hashes: mehr oder größer?

15

Bei der Implementierung eines Bloom-Filters erfordert der herkömmliche Ansatz mehrere unabhängige Hash-Funktionen. Kirsch und Mitzenmacher haben gezeigt, dass man eigentlich nur zwei braucht und den Rest als Linearkombination daraus erzeugen kann.

Meine Frage ist: Was ist der Unterschied zwischen zwei Hash-Funktionen und einer mit der doppelten Entropie?

Dies hängt damit zusammen, was Sie tatsächlich mit der Ausgabe Ihrer Hash-Funktionen tun: Sie werden Ihren (etwa) 64-Bit-Hash-Wert auf die Größe Ihres Bitvektors skalieren, der wahrscheinlich bedeutend kleiner als 2 ist 64 . Dies ist eindeutig eine Transformation, bei der die Entropie verloren geht (außer in seltenen Fällen stimmen Ihre Hash-Größe und Filterkapazität genau überein). Angenommen, mein Filter enthält weniger als 2 32 Einträge. Was hindert mich daran, meinen 64-Bit-Hash-Wert in zwei 32-Bit-Hashes aufzuteilen und lineare Kombinationen daraus zu erstellen? Oder verwenden Sie es, um einen PRNG zu erzeugen?

Mit anderen Worten, wie viele Informationen muss ich tatsächlich über jedes Element wissen, das ich in einen Bloom-Filter einfüge, um sicherzustellen, dass die Standard-False-Positive-Rate gilt? Oder allgemeiner: In welchem ​​Verhältnis steht es, wie gut ich Elemente unterscheiden kann (wie viele Bits benutze ich, um sie zu beschreiben) und wie gut mein Bloom-Filter funktioniert?

Es scheint sicher, dass ich bei einer Filtergröße von mit Bits davonkommen kann , oder äquivalent mit Bits, die gespeichert werden müssen Elemente mit falsch positiver Wahrscheinlichkeit ....2lg(m)m2(lg(-nlnp)-2lg(ln2))np

Jay Hacker
quelle

Antworten:

16

Man kann sich Hash-Funktionen zu Recht als "zufällig erzeugte Bits" vorstellen. Wenn Sie also eine Hash-Funktion haben, die einen 64-Bit-Hash erzeugt, können Sie dies wie 4 16-Bit-Hashes (durch Aufteilen) behandeln und so weiter.

Für das oben beschriebene Schema (das Dillinger und Manolios zugeschrieben werden sollte; Kirsch / Mitzenmacher haben es gerade analysiert) heißt das, Sie haben Recht; Wenn Sie eine einzelne Hash-Funktion mit Bits haben, sollten Sie in Ordnung sein.2lg(m)

Michael Mtizenmacher
quelle
5
Willkommen bei cstheory, Michael :)
Suresh Venkat