Ist die herkömmliche Analyse von Bloom-Filtern falsch?

In diesem Artikel wird behauptet, dass die herkömmliche Analyse der Fehlerrate in Bloom-Filtern nicht korrekt ist. Anschließend wird eine ausführliche und nicht triviale Analyse der tatsächlichen Fehlerrate durchgeführt. Das verlinkte Papier wurde 2010 veröffentlicht, aber ich habe gesehen, dass die traditionelle Analyse von Bloom-Filtern weiterhin in verschiedenen Kursen zu Algorithmen und Datenstrukturen vermittelt wurde.

Ist die herkömmliche Analyse von Bloom-Filtern tatsächlich falsch?

Vielen Dank!

Die traditionelle Analyse ist in Ordnung. Die "traditionelle" Analyse ist, wenn sie richtig erklärt wird, eine Annäherung; Es basiert auf der Berechnung der erwarteten Anzahl von Zellen mit einem Wert von 0/1, wenn Sie die Schlüssel im Filter haben, und der Analyse, als ob dies die tatsächliche Anzahl wäre. Der Punkt ist, dass die Anzahl der Zellen, die 0 (oder 1) sind, eng um ihre Erwartung konzentriert ist, so dass es eine feine Annäherung ist. Dies war allgemein bekannt und kann, glaube ich, bereits in meinem Umfrageartikel bei Andrei Broder gefunden werden.

In diesem Artikel heißt es, dass die Leistung eines Bloom-Filters eine Zufallsvariable ist (die dem tatsächlichen Anteil von 0/1 Einträgen entspricht). Wenn Sie diese Leistung aus irgendeinem Grund genau berechnen möchten, müssen Sie die Kombinatorik durchführen. Bei kleineren Filtern sehen Sie einen wohl nicht trivialen Unterschied.

Ich habe mit den Autoren dieses Papiers gesprochen. Ihre Analyse ist alle gut und gut (obwohl ich behaupten würde, dass es nicht tief oder neu ist); Ihre Motivation, dass die "traditionelle Analyse falsch ist", war meines Erachtens übertrieben.

Lassen Sie mich zu Michaels Antwort hinzufügen, dass für Split- Bloom-Filter, bei denen die Hash-Funktionen disjunkte Bereiche aufweisen, die traditionelle Analyse in der Tat ohne Annäherung oder Konzentrationsgrenzen korrekt ist. Dies liegt daran, dass die Fehlerwahrscheinlichkeiten für verschiedene Hash-Funktionen unabhängig und nicht korreliert werden. Der Raum / Fehler-Kompromiss für geteilte Bloom-Filter ist im Wesentlichen der gleiche wie für herkömmliche Bloom-Filter, daher denke ich, dass dies eine gute Variante für das Unterrichten ist.