Berechnung der ungefähren Population eines Bloom-Filters

Gegeben sei ein Bloom-Filter der Größe N-Bits und K Hash-Funktionen, von denen M-Bits (wobei M <= N) des Filters gesetzt sind.

Ist es möglich, die Anzahl der in den Bloom-Filter eingefügten Elemente zu schätzen?

Einfaches Beispiel

Ich habe über das folgende Beispiel nachgedacht und eine BF von 100-Bit- und 5-Hash-Funktionen angenommen, bei denen 10-Bit gesetzt sind ...

Best-Case-Szenario: Vorausgesetzt, die Hash-Funktionen sind wirklich perfekt und ordnen ein Bit für eine bestimmte Anzahl von X-Werten eindeutig zu. Wenn 10-Bit-Werte festgelegt wurden, können wir sagen, dass nur 2 Elemente in die BF eingefügt wurden

Worst-Case-Szenario: Unter der Annahme, dass die Hash-Funktionen fehlerhaft sind und konsistent auf dasselbe Bit abgebildet werden (jedoch untereinander eindeutig sind), können wir sagen, dass 10 Elemente in die BF eingefügt wurden

Der Bereich scheint [2,10] zu sein, bei dem die Wahrscheinlichkeit eines falsch-positiven Filters wahrscheinlich die Werte in diesem Bereich bestimmt - ich stecke an diesem Punkt fest.

Ja. Aus Wikipedia :

Wenn Sie Elemente mit Hash-Funktionen in einen Filter der Größe eingefügt haben , ist die Wahrscheinlichkeit, dass ein bestimmtes Bit noch 0 ist, gleichn $i$$n$$k$

Sie können diese Wahrscheinlichkeit als Anteil von 0 Bits in Ihrem Filter messen . Löse nach, was gebe$i$

Ich habe dies in der Praxis angewendet. Solange Ihr Filter seine Kapazität nicht überschreitet, liegt der Fehler bei Filtern mit bis zu Millionen von Bits in der Regel unter 0,1%. Wenn der Filter seine Kapazität überschreitet, steigt der Fehler natürlich an.

Wenn Sie davon ausgehen, dass für jede Hash-Funktion für jedes Objekt ein Bit gleichmäßig zufällig gesetzt wird und Sie die Anzahl der gesetzten Bits zählen, sollten Sie in der Lage sein, die Wahrscheinlichkeit zu begrenzen, mit der die Anzahl der eingefügten Objekte lag innerhalb eines bestimmten Bereichs, möglicherweise unter Verwendung einer Kugel- und Behälterformulierung. Jedes Bit ist ein Bin und es wird gesetzt, wenn es mindestens 1 Ball enthält. Jedes eingefügte Objekt wirft Bälle, wobei die Anzahl der Hash-Funktionen und die Anzahl der Bälle ist, die nach dem Einfügen von n Objekten geworfen wurden. Wie hoch ist die Wahrscheinlichkeit, dass mindestens t Bälle geworfen wurden, wenn in b Bins mindestens 1 Ball enthalten ist ? Ich denke hier kann man die Tatsache nutzen, dass: Pk n $k$$k$$nk$$n$$b$$t$ Aber das Problem mit dieser Formulierung istdass ich seheeine einfache Art und Weise zu berechnen nicht P ( t ) oder P ( b ) , aber den Wert von t zu finden, der diese Wahrscheinlichkeit maximiert, sollte nicht zu schwierig sein.

Interessante Frage, schauen wir uns einige konkrete Fälle an.

Es sei Tasten, n o n Bits, n t o t a l Bits insgesamt , und m Elemente eingefügt. Wir werden versuchen , zunächst eine Funktion zu finden P ( k , n o n , n t o t a l , m ) , das ist die Wahrscheinlichkeit , ein Zustand auftritt.$k$$n_{on}$$n_{total}$$m$$P(k, n_{on}, n_{total}, m)$

Wenn , dann P ( k , n o n , n t o t a l , m ) sein muss , 0 , dh es ist ein Ding der Unmöglichkeit.$km \lt n_{on}$$P(k, n_{on}, n_{total}, m)$$0$

Wenn , dann für die Wahrscheinlichkeit , suchen wir , dass k m Hashes in der gleichen Eimer fallen, kann die erste markieren , wo sollten die anderen gehen. Wir wollen also die Wahrscheinlichkeit ermitteln, dass k m - 1 Hashes in einen bestimmten Eimer fallen.$n_{on} = 1$$km$$km - 1$

$P(k, 1, n_{total}, m) = (1/n_{total})^{(km-1)}$

Das sind die wirklich einfachen Fälle. Wenn dann wollen wir die Wahrscheinlichkeit finden , dass k m Hashes in landen zwei verschiedene Eimer und mindestens 1 fällt in jedem. Es gibt n t o t a l ( n t o t a l - 1 ) Paare von Schaufeln und die Wahrscheinlichkeit , dass die Hash - Werte in einem bestimmten Land 2 ist ( 2 / n t o t a l ) k $n_{on} = 2$$km$$2$$1$$n_{total}(n_{total} - 1)$$2$$(2/n_{total})^{km}$Die Wahrscheinlichkeit, dass die Hashes in bis zu Eimern abfallen, ist also:$2$

$n_{total}(n_{total} - 1)(2/n_{total})^{km}$

Wir wissen schon , die Wahrscheinlichkeit , dass sie in fällt Eimer Werfen sich also subtrahiert , dass die Wahrscheinlichkeit zu geben , dass sie in genau fallen 2 .$1$$2$

$P(k, 2, n_{total}, m) = n_{total}(n_{total} - 1)(2/n_{total})^{km} - (1/n_{total})^{(km-1)}$

Ich denke, wir können das jetzt verallgemeinern.

$P(k, n_{on}, n_{total}, m) = {n_{total} \choose n_{on}}(n_{on}/n_{total})^{km} - \sum_{i=1}^{i<n_{on}} P(k, i, n_{total}, m)$

Ich bin mir nicht ganz sicher, wie ich diese Formel für die Berechnung besser geeignet machen kann. Naiv implementiert, würde dies zu einer exponentiellen Zeitausführungszeit führen, obwohl es trivial ist, durch Merken eine lineare Zeit zu erreichen. Es geht dann nur darum, das wahrscheinlichste . Mein Instinkt sagt, dass es einen einzelnen Peak geben wird, so dass es möglich sein kann, ihn sehr schnell zu finden, aber naiv kann man definitiv das wahrscheinlichste m in O ( n 2 ) finden .$m$$O(n^2)$

Angenommen, die Hashes sind gleichmäßig verteilt.

Sei die Anzahl der eingefügten Hashes. Da wir i Hashes in m Bins haben, wenn wir i - 1 Hashes in m Bins haben und der nächste Hash in einen dieser m aus n Bins geht, ODER wenn wir i - 1 Hashes in m - 1 Bins haben und der nächste Hash geht In einen der anderen n - ( m - 1 ) Behälter haben wir:$i$$i$$m$$i-1$$m$$m$$n$$i-1$$m-1$$n-(m-1)$

$P(m,i) = P(m,i-1)(m/n) + P(m-1,i-1)(n-(m-1))/n$

Umschreiben:

$P(m,i) = \frac{1}{n}(mP(m,i-1) + (n-m+1)P(m-1,i-1))$

Wir haben auch und P ( m , 0 ) = 0, wenn m ≤ 0 und P ( 0 , i ) = 0, wenn i ≤ 0 . Dies gibt Ihnen einen dynamischen O ( m i ) -Programmieralgorithmus zum Berechnen von P. Berechnen des i , das P ( m , i ) maximiert.$P(0,0) = 1$$P(m,0) = 0$$m \neq 0$$P(0,i) = 0$$i \neq 0$$O(mi)$$i$$P(m,i)$ gibt Ihnen die maximale Wahrscheinlichkeitsschätzung.

Wenn wir wissen, dass wir mal in diesen Bloom-Filter gehasht haben und wir k Hashes pro Element haben, dann ist die Anzahl der Elemente i / k .$i$$k$$i/k$

Um dies zu beschleunigen, können Sie einige Dinge tun. Der Faktor kann weggelassen werden, da es die Position des Maximums nicht ändert. Sie können die dynamischen Programmiertabellen für mehrere Aufrufe vonP(m,i)freigeben, um die (asymptotische) Laufzeit aufO(nm)zu reduzieren. Wenn Sie glauben möchten, dass es ein einzelnes Maximum gibt, können Sie die Iteration überifrühzeitigstoppenund die LaufzeitO(jm)abrufen,wobeij derPunkt ist, an demPsein Maximum annimmt, oder sogar eine binäre Suche durchführen und abrufenO(mlogn).$\frac{1}{n}$$P(m,i)$$O(nm)$$i$$O(jm)$$j$$P$$O(m \log n)$

Die Schlüsselidee besteht darin, die Erwartung der Anzahl der Null-Bits anzunähern.

$(1-\frac{1}{N})^{Kt} \approx e^{-\frac{Kt}{N}}$

Dann sollte die Erwartung von Nullbitzahlen sein:

$N e^{-\frac{Kt}{N}}$$N - M$

Finally we got $t = - \frac{N}{K} ln(1-\frac{M}{N})$

Probability that a particular bit is 1 after n insertions is: P = 1 - (1 - 1/m) ^ (kn)

Let X_i be a discrete random variable which is 1 if the bit at i'th position is 1 and 0 otherwise. Let X = X_1 + X_2 + .... + X_m. Then, E[X] = m * P.

If total number of set bits are S, then: E[X] = S which implies m * P = S. This could be solved for n.