Jak działają skalowalne filtry Bloom?

Czytałem o skalowalnych filtrach Bloom i nie mogłem zrozumieć, jak za każdym razem, gdy wypełniają się filtry Bloom Bloom, dodawany jest nowy filtr Bloom o większym rozmiarze.

Elementy, które przyczyniły się do ustawienia bitów we wstępnie utworzonych filtrach, nie mogą być wyszukiwane pod kątem obecności. Może się mylę, rozumiejąc to?

Rozumiem podstawowe filtry Bloom. Nie mogę jednak owinąć głowy dynamicznymi filtrami Bloom.

Pozwólcie, że spróbuję dać temu szansę, aby zobaczyć, jak bardzo mogę to zrobić. :-)

Tak więc, na początek, musisz być w stanie stworzyć regularny filtr kwitnienia, który pozwala na skończoną liczbę elementów z maksymalnym prawdopodobieństwem fałszywie dodatniego. Dodanie tych funkcji do podstawowego filtra jest wymagane przed próbą zbudowania skalowalnej implementacji.

Zanim spróbujemy kontrolować i zoptymalizować prawdopodobieństwo, dowiedzmy się, jakie jest prawdopodobieństwo dla danego rozmiaru filtra Blooma.

Najpierw podzielimy pole bitowe według tego, ile mamy funkcji skrótu (całkowita liczba bitów / liczba funkcji skrótu = plasterki), aby uzyskać k kawałków bitów, które reprezentują każdą funkcję skrótu, więc każdy element jest zawsze opisany przez k bitów.

Jeśli zwiększysz liczbę wycinków lub liczbę bitów na wycinek, prawdopodobieństwo fałszywych trafień zmniejszy się.

Wynika z tego również, że wraz z dodawaniem elementów, więcej bitów jest ustawianych na 1, więc rośnie liczba fałszywych alarmów. Nazywamy to „współczynnikiem wypełnienia” każdego plastra.

Gdy filtr przechowuje dużą ilość danych, możemy założyć, że prawdopodobieństwem fałszywych trafień dla tego filtra jest współczynnik wypełnienia podniesiony do liczby wycinków (Jeśli tak naprawdę policzymy bity zamiast używać współczynnika, to upraszcza się do permutacja z problemem powtarzania).

Jak więc wymyślić, jak wybrać prawdopodobieństwo fałszywych alarmów w filtrze kwitnienia? Możemy zmodyfikować liczbę plasterków (co wpłynie na współczynnik wypełnienia).

Aby dowiedzieć się, ile plasterków powinniśmy mieć, zaczynamy od ustalenia optymalnego współczynnika wypełnienia plasterka. Ponieważ współczynnik wypełnienia zależy od liczby bitów w wycinku, które są równe 1, w porównaniu do liczby bitów, które wynoszą 0, możemy ustalić, że każdy bit pozostanie nieustawiony z prawdopodobieństwem (100% - (1 / bit w wycinku) ). Ponieważ będziemy wstawiać wiele elementów, mamy kolejną permutację z problemem reputacji i rozszerzamy rzeczy do oczekiwanego współczynnika wypełnienia, który wynosi (100% - ((100% - (1 / bity w plasterku)) ^ „wstawione elementy”)). Okazuje się, że jest to bardzo podobne do innego równania. W pracy odnoszą się one do współczynnika wypełnienia do innego równania, więc ładnie pasuje do szeregu Taylora (1-e ^ (- n / m)). Po odrobinie dudnienia z tym okazuje się, że optymalny współczynnik wypełnienia wynosi zawsze około 50%,

Tak więc, ponieważ prawdopodobieństwo filtra to współczynnik wypełnienia podniesiony do liczby plasterków, możemy wypełnić 50% i uzyskać P = (50%) ^ k lub k = log_2 (1 / P). Następnie możemy użyć tej funkcji do obliczenia liczby wycinków, które powinniśmy wygenerować dla danego filtra na liście filtrów dla skalowalnego filtra Bloom.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Edycja: Po napisaniu tego, natrafiłem na wzmiankę o „regule pięćdziesięcioprocentowej”, czytając o dynamicznej alokacji pamięci opartej na systemie koleżeńskim w TAoCP tom 1, str. 442–445 z dużo czystszym uzasadnieniem w porównaniu z dopasowaniem krzywej do (1 -e ^ (- n / m)). Knuth odwołuje się także do artykułu „Zrewidowana reguła pięćdziesięcioprocentowa” z odrobiną tła na temat tej koncepcji ( pdf dostępny tutaj ).

Element znajduje się w skalowalnym filtrze Bloom, jeśli jakikolwiek filtr zwróci wartość true. Dlatego możesz dodawać filtry bez wpływu na zapytania członkostwa dotyczące poprzednich elementów.

Aby upewnić się, że nadal masz najgorszą fałszywą gwarancję, dodawane są nowe filtry z fałszywie dodatnimi wskaźnikami, które zmniejszają się geometrycznie. Na przykład, pierwszy filtr ma wyników fałszywie dodatnich p, drugi rp, trzeci r^2pitd Prawdopodobieństwo fałszywego dodatnie na skalowalnej filtr Bloom jest wtedy ograniczony przez związek wyznaczony: sum_{k>=0} r^k p = p/(1-r).

Czytałem o skalowalnych filtrach Bloom i nie mogłem zrozumieć, jak za każdym razem, gdy wypełniają się filtry Bloom Bloom, dodawany jest nowy filtr Bloom o większym rozmiarze.

Elementy, które przyczyniły się do ustawienia bitów we wstępnie utworzonych filtrach, nie mogą być wyszukiwane pod kątem obecności. Może się mylę, rozumiejąc to?

Cześć,
Podstawową ideą jest dodanie do pierwszego filtra, aż pole bitowe filtra pierwszego poziomu zostanie nasycone. Bycie nasyconym nie oznacza, że ​​każdy bit jest używany, ale oznacza, że ​​filtr zawiera tak wiele wpisów, że dodatkowe wpisy spowodowałyby zbyt wiele fałszywych trafień.

Z punktu nasycenia, żadna nowa pozycja nie zostanie dodana do filtra nasyconego, ale do świeżego i większego subfiltru (filtr drugiego poziomu).

Aby znaleźć wartość, poszukaj jej w filtrze pierwszego poziomu, a jeśli nie możesz jej tam znaleźć, poszukaj w filtrze drugiego poziomu. Jeśli można go znaleźć w którymkolwiek z tych filtrów, jest on (z dużym prawdopodobieństwem) „znany” filtrowi (fałszywe pozytywne mogą wystąpić w wyniku natury filtrów Blooma). Jeśli nie możesz znaleźć wartości w żadnym z filtrów, na pewno nie zobaczysz tego filtru. Można to oczywiście wyrazić jako rekurencyjną strukturę danych.

Możesz przeczytać mój post na blogu, który zawiera skalowalną implementację filtra Blooma w Javie i wyjaśnienie, w jaki sposób to działa.