Obliczanie przybliżonej populacji filtra Blooma

12

Biorąc pod uwagę filtr Blooma o rozmiarze N-bitów i funkcjach skrótu K, w których ustawionych jest M-bitów (gdzie M <= N) filtra.

Czy jest możliwe przybliżenie liczby elementów wstawionych do filtra Bloom?

Prosty przykład

Zastanawiam się nad poniższym przykładem, zakładając BF 100 bitów i 5 funkcji skrótu, w których ustawiono 10 bitów ...

Najlepszy scenariusz: przy założeniu, że funkcje skrótu są naprawdę idealne i wyjątkowo mapują trochę dla pewnej liczby X wartości, to po ustawieniu 10 bitów możemy powiedzieć, że do BF wstawiono tylko 2 elementy

Najgorszy scenariusz: Zakładając, że funkcje skrótu są złe i konsekwentnie odwzorowywane na ten sam bit (ale unikatowy między sobą), to możemy powiedzieć, że 10 elementów zostało wstawionych do BF

Zakres wydaje się wynosić [2,10], gdzie w przybliżeniu w tym zakresie prawdopodobnie określa się fałszywie dodatnie prawdopodobieństwo filtra - utknąłem w tym momencie.

ds.data-structures pr.probability

— Tander Kulip
źródło

4

Dlaczego nie zachować licznika liczby wstawionych elementów? Potrzeba tylko dodatkowych bitów , jeśli wstawiłeś elementów.

O (\log n)

$O(\log n)$

n

$n$

— Joe

@Joe, chociaż to dobry pomysł, zrujnuje to naprawdę interesujące pytanie.

— dan_waterworth

Wystarczy zauważyć, że w przypadku duplikatów metoda Joe'a będzie miała mały błąd, ponieważ nie zawsze możemy na pewno powiedzieć podczas dodawania elementu, czy jest już obecny (i dlatego powinniśmy zwiększyć liczbę, czy nie).

— usul

5

Tak. Z Wikipedii :

Jeśli wstawiłeś elementy do filtra o rozmiarze za pomocą funkcji skrótu, prawdopodobieństwo, że określony bit nadal wynosi 0, wynosi $i$ $n$ $k$

z = {(1 - \frac{1}{n})}^{k i}

$z = \left(1 - \frac{1}{n}\right)^{ki}$

Możesz zmierzyć to prawdopodobieństwo jako proporcję 0 bitów w filtrze. Rozwiązywanie dla daje $i$

i = \frac{\ln (z)}{k \ln (1 - \frac{1}{n})}

$i = \frac{\ln(z)}{k\ln\left(1 - \frac{1}{n}\right)}$

Użyłem tego w praktyce i dopóki twój filtr nie przekracza swojej pojemności, błąd jest generalnie mniejszy niż 0,1% dla filtrów do milionów bitów. Gdy filtr przekracza swoją pojemność, błąd oczywiście rośnie.

— Jay Hacker
źródło

3

Jeśli przyjmiesz, że dla każdej funkcji skrótu dla każdego obiektu bit jest ustawiany równomiernie losowo, a masz liczyć na liczbę bitów, które zostały ustawione, powinieneś być w stanie ograniczyć prawdopodobieństwo, że liczba wstawionych obiektów była w określonym zakresie, być może przy użyciu formuły kulek i pojemników. Każdy bit jest koszem i jest ustawiany, jeśli ma w nim co najmniej 1 piłkę, każdy wstawiony obiekt rzuca piłek, gdzie jest liczbą funkcji skrótu, a jest liczbą piłek rzuconych po wstawieniu obiektów. Biorąc pod uwagę, że kosze mają w sobie co najmniej 1 piłkę, jakie jest prawdopodobieństwo, że wyrzucono co najmniej piłki? Myślę, że tutaj możesz skorzystać z faktu, że: $k$ $k$ $nk$ $n$ $b$ $t$ Ale problem z tym sformułowaniem polega na tym, że nie widzę prostego sposobu obliczenia lub , ale znalezienie wartości która maksymalizuje to prawdopodobieństwo, nie powinno być zbyt trudne.

P. (t kulki | b pojemniki) = P. (b pojemniki | t kulki) \cdot P. (t) / P. (b)

$P( t \mbox{ balls} | b \mbox{ bins} ) = P(b \mbox{ bins}| t \mbox{ balls}) \cdot P(t)/P(b)$

P (t)

$P(t)$

P (b)

$P(b)$

t

$t$

— Joe
źródło

2

Ciekawe pytanie, spójrzmy na niektóre konkretne przypadki.

Niech będzie klucze, bitów na, bitów całkowitego i elementów wstawianych. Najpierw spróbujemy znaleźć funkcję która jest prawdopodobieństwem wystąpienia stanu. $k$ $n_{on}$ $n_{total}$ $m$ $P(k, n_{on}, n_{total}, m)$

Jeśli , to musi wynosić , tzn. Jest to niemożliwe. $km \lt n_{on}$ $P(k, n_{on}, n_{total}, m)$ $0$

Jeśli , a następnie szukamy prawdopodobieństwo, że hashe spaść w tym samym wiadrze, pierwszy może oznaczać gdzie reszta powinna pójść. Chcemy więc ustalić prawdopodobieństwo, że hasze wpadną do określonego segmentu. $n_{on} = 1$ $km$ $km - 1$

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

To naprawdę proste przypadki. Jeśli wówczas znaleźć prawdopodobieństwo skróty ziemi w różnych wiadra i co najmniej mieści się w każdej z nich. Istnieje par wiadra i prawdopodobieństwo, że skróty ziemi w indywidualnych jest $n_{on} = 2$ $km$ $2$ $1$ $n_{total}(n_{total} - 1)$ $2$ $(2/n_{total})^{km}$ więc prawdopodobieństwo, że skróty mieszczą się w maksymalnie segmentach, wynosi: $2$

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

Wiemy już prawdopodobieństwo, że wpadną do wiadra, więc odejmijmy to, aby dać prawdopodobieństwo, że wpadną dokładnie do . $1$ $2$

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

Myślę, że możemy to teraz uogólnić.

$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)$

Nie jestem do końca pewien, jak uczynić tę formułę bardziej podatną na obliczenia. Zaimplementowane naiwnie, spowodowałoby to czas wykonania wykładniczego czasu, choć jest trywialne, poprzez zapamiętywanie, aby osiągnąć czas liniowy. To tylko przypadek znalezienia najbardziej prawdopodobnego . Mój instynkt mówi, że będzie jeden pik, więc może być możliwe znalezienie go bardzo szybko, ale naiwnie zdecydowanie można znaleźć m w . $m$ $O(n^2)$

— dan_waterworth
źródło

Myślę, że twoja formuła anuluje się do

(ignorując czynniki stałe). Możesz obliczyć maksimum tego analitycznie: rozwiń pierwszy czynnik drugiego terminu i usuń stałe czynniki, aby się ich pozbyć, a wtedy twoja formuła stanie się bardzo prosta.

(\binom{n_{t o t a l}}{n_{o n}}) n_{o n}^{k m} - (\binom{n_{t o t a l}}{n_{o n} - 1}) (n_{o n} - 1)^{k m}

${n_{total} \choose n_{on}}n_{on}^{km}- {n_{total} \choose n_{on}-1}(n_{on}-1)^{km}$ n choose k

— Jules

@Jules, świetnie, byłem pewien, że coś takiego się wydarzy, ale nie miałem czasu, aby to rozgryźć.

— dan_waterworth

Możesz również dojść do tej formuły bezpośrednio w następujący sposób:

. Następnie podłącz

P (n_{o n} = x) = P (n_{o n} \leq x) - P (n_{o n} < x) = P (n_{o n} \leq x) - P (n_{o n} \leq x - 1)

$P(n_{on} = x) = P(n_{on} \leq x) - P(n_{on} < x) = P(n_{on} \leq x) - P(n_{on} \leq x-1)$

dla

.

(\binom{n_{t o t a l}}{x}) (x / n_{t o t a l})^{k m}

${n_{total} \choose x} (x/n_{total})^{km}$

P (n_{o n} \leq x)

$P(n_{on} \leq x)$

— Jules

2

Załóżmy, że skróty są równomiernie rozmieszczone.

Pozwól być liczba wstawionych skrótów. Ponieważ mamy hashe w binach, jeśli mamy hashe w binsach, a następny hash przechodzi do jednego z tych spośród bin LUB jeśli mamy hashe w binach, a następny hash idzie w jednym z innych pojemników mamy: $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$

Przepisanie:

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

Mamy również i gdy i gdy . Daje to algorytm programowania dynamicznego do obliczania P. Obliczanie które maksymalizuje $P(0,0) = 1$ $P(m,0) = 0$ $m \neq 0$ $P(0,i) = 0$ $i \neq 0$ $O(mi)$ $i$ $P(m,i)$ daje oszacowanie maksymalnego prawdopodobieństwa.

Jeśli wiemy, że mamy zakodowane w ten filtr kwitną razy i mamy hashe za przedmiot, wówczas liczba elementów jest . $i$ $k$ $i/k$

Aby to przyspieszyć, możesz zrobić kilka rzeczy. Współczynnik można pominąć, ponieważ nie zmienia położenia maksimum. Możesz udostępniać tabele programowania dynamicznego z wieloma wywołaniami doaby skrócić (asymptotyczny) czas działania do. Jeśli jesteś skłonny uwierzyć, że istnieje tylko jedno maksimum, można zatrzymać iteracji nadwcześnie i uzyskać czas pracy, gdziejest punkt, w którymbierze na maksimum, a nawet zrobić wyszukiwania binarnego i get. $\frac{1}{n}$ $P(m,i)$ $O(nm)$ $i$ $O(jm)$ $j$ $P$ $O(m \log n)$

— Jules
źródło

2

Kluczową ideą jest przybliżenie oczekiwanej liczby bitów zerowych.

Dla każdego bitu możliwość wyzerowania po t wstawieniu za pomocą funkcji skrótu K wynosi: . $(1-\frac{1}{N})^{Kt} \approx e^{-\frac{Kt}{N}}$

Zatem oczekiwanie zerowych liczb bitowych powinno wynosić:

aproksymowane obserwacją $N e^{-\frac{Kt}{N}}$ $N - M$

Wreszcie mamy $t = - \frac{N}{K} ln(1-\frac{M}{N})$

— Yanghong Zhong
źródło

1

Prawdopodobieństwo, że dany bit ma wartość 1 po n wstawieniu, wynosi: P = 1 - (1 - 1 / m) ^ (kn)

Niech X_i będzie dyskretną zmienną losową, która wynosi 1, jeśli bit na i-tej pozycji wynosi 1, a w przeciwnym razie 0. Niech X = X_1 + X_2 + .... + X_m. Następnie E [X] = m * P.

Jeśli całkowita liczba ustawionych bitów to S, to: E [X] = S, co oznacza m * P = S. Można to rozwiązać dla n.

— Nikhil
źródło