Ich habe Probleme, die möglichen Probleme des Bloom Filters mit Dynamic Sets zu verstehen.Bloom Filter Mögliche Probleme beim Umgang mit dynamischen Sets
Können Sie mir einige mögliche Probleme nennen, die beim Hinzufügen/Entfernen von Elementen aus dem Set auftreten können?
Das Hauptproblem sind Bloom-Filter sind nicht für die Entfernung konzipiert.
Zum Beispiel. Angenommen
h1(x) = x %5
h2(x) = (x+2) % 5
Und bedenken Sie 2 Elemente im Satz haben: 2,4.
Sie haben die bitset:
bitset = { 0, 1, 1, 0, 1 }
Jetzt wollen Sie 2 aus dem Set entfernen. Wie machst du das? Sie haben keine Ahnung, dass bitset [4], um beide Elemente gemeinsam ist, und wenn Sie es entfernen, werden Sie die neue bitset erhalten:
bitset' = { 0, 0, 1, 0, 0 }
Aber jetzt, wenn Sie versuchen, zu überprüfen, ob 4 in es ist, Sie werden eine falsche Antwort bekommen.
Eine mögliche Lösung zum Entfernen von Bloomfiltern ist counting bloom filters, aber es hat auch negative.
Noch ein Problem, wenn Ihr Set dynamisch ist und weiter wachsen kann, ist es nicht trivial, seine Größe zu erhöhen. Sie können nicht einfach den doppelten Platz zuweisen und die gesamte Sammlung neu zusammenstellen, Sie haben keine Ahnung, was die ursprünglichen Elemente waren.
Daher wird Bloom Filter verwendet, wenn seine Größe bekannt (oder begrenzt) apriori ist.