Jakie są zalety używania filtrów bloom?

Czytam o filtrach bloom i po prostu wydają się głupie. Wszystko, co możesz osiągnąć za pomocą filtra bloom, możesz osiągnąć w mniejszej przestrzeni, bardziej wydajnie, używając pojedynczej funkcji skrótu, a nie wielu, lub tak się wydaje. Dlaczego miałbyś używać filtra Bloom i jak jest on przydatny?

Z Wikipedii :

Filtry Blooma mają dużą przewagę przestrzenną nad innymi strukturami danych do reprezentowania zestawów, takich jak samobalansujące się binarne drzewa wyszukiwania, próby, tablice skrótów lub proste tablice lub połączone listy wpisów. Większość z nich wymaga przechowywania przynajmniej samych elementów danych, co może wymagać dowolnego miejsca, od małej liczby bitów, dla małych liczb całkowitych, do dowolnej liczby bitów, na przykład dla łańcuchów (wyjątek stanowią próby, ponieważ mogą one współdzielić pamięć między elementy o równych przedrostkach). Struktury połączone powodują dodatkowe obciążenie przestrzeni liniowej dla wskaźników. Z drugiej strony filtr Blooma z błędem 1% i optymalną wartością k wymaga tylko około 9,6 bitów na element - niezależnie od wielkości elementów. Ta zaleta wynika częściowo ze zwartości, odziedziczonej po tablicach, a częściowo z jej probabilistycznej natury. Jeśli 1% współczynnik fałszywych trafień wydaje się zbyt wysoki, za każdym razem, gdy dodajemy około 4,8 bitów na element, zmniejszamy go dziesięciokrotnie.

Dla mnie całkiem jasne.

Filtr bloom nie przechowuje samych pierwiastków, to jest kluczowy punkt. Nie używasz filtra bloom, aby sprawdzić, czy element jest obecny, używasz go do sprawdzenia, czy na pewno nie jest obecny, ponieważ gwarantuje to brak fałszywych negatywów. Pozwala to nie wykonywać dodatkowej pracy dla elementów, które nie istnieją w zestawie (takich jak operacje we / wy dysku w celu ich wyszukania).

A wszystko to w znacznie mniejszej ilości miejsca niż coś takiego jak tablica mieszająca (która prawdopodobnie będzie częściowo na dysku w przypadku dużych zestawów danych). Chociaż możesz użyć filtra bloom w połączeniu ze strukturą, taką jak tabela haszująca, gdy masz pewność, że element ma szansę być obecny.

Przykładowy wzorzec użycia może wyglądać tak:

Masz dużo danych na dysku - sam decydujesz, jaki błąd chcesz przypisać (np. 1%), który określa wartość m . Następnie określane jest optymalne k (ze wzoru podanego w artykule). Jeden raz wypełniasz filtr tymi danymi powiązanymi z dyskiem.

Teraz masz filtr w pamięci RAM. Kiedy musisz przetworzyć jakiś element, wysyłasz zapytanie do filtra, aby sprawdzić, czy ma szansę zaistnieć w Twoim zestawie danych. Jeśli tak się nie stanie, nie jest wykonywana żadna dodatkowa praca. Brak odczytów dysku itp. (Co musiałbyś zrobić, gdyby był to skrót lub drzewo itp.).

W przeciwnym razie, jeśli filtr mówi „Tak, jest tam”, istnieje 1% prawdopodobieństwa, że ​​jest źle, więc wykonujesz niezbędne prace, aby się dowiedzieć. 99% czasu, to naprawdę będzie tam być, więc praca nie była do niczego.

Alex całkiem dobrze to wyjaśnił. Dla tych, którzy nadal nie rozumieli, mam nadzieję, że ten przykład pomoże ci zrozumieć:

Powiedzmy, że pracuję dla Google, w zespole Chrome, i chcę dodać do przeglądarki funkcję, która powiadamia użytkownika, jeśli wprowadzony adres URL jest złośliwym adresem URL. Mam więc zbiór danych zawierający około 1 miliona złośliwych adresów URL, przy czym rozmiar tego pliku wynosi około 25 MB. Ponieważ rozmiar jest dość duży (duży w porównaniu z rozmiarem samej przeglądarki), przechowuję te dane na zdalnym serwerze.

Przypadek 1: Używam funkcji skrótu z tabelą skrótów. Decyduję się na wydajną funkcję mieszającą i uruchamiam wszystkie 1 milion adresów URL przez funkcję mieszania, aby uzyskać klucze skrótu. Następnie tworzę tablicę mieszającą (tablicę), w której klucz skrótu dałby mi indeks do umieszczenia tego adresu URL. Więc teraz, gdy już zaszyfowałem i zapełniłem tablicę haszującą, sprawdzam jej rozmiar. Przechowałem wszystkie 1 milion adresów URL w tabeli skrótów wraz z ich kluczami. Więc rozmiar wynosi co najmniej 25 MB. Ta tablica mieszająca, ze względu na swój rozmiar, będzie przechowywana na zdalnym serwerze. Kiedy pojawia się użytkownik i wpisuje adres URL w pasku adresu, muszę sprawdzić, czy jest złośliwy. W ten sposób uruchamiam adres URL za pomocą funkcji skrótu (sama przeglądarka może to zrobić) i otrzymuję klucz skrótu dla tego adresu URL. Muszę teraz wysłać żądanie do mojego zdalnego serwera za pomocą tego klucza skrótu, aby sprawdzić, czy określony adres URL w mojej tabeli skrótów z tym konkretnym kluczem jest taki sam, jak wpisany przez użytkownika. Jeśli tak, to jest złośliwe, a jeśli nie, to nie jest złośliwe. Dlatego za każdym razem, gdy użytkownik wprowadza adres URL, należy wysłać żądanie do zdalnego serwera, aby sprawdzić, czy jest to złośliwy adres URL. Zajmie to dużo czasu i spowolni moją przeglądarkę.

Przypadek 2: używam filtra bloom. Cała lista 1 miliona adresów URL jest przepuszczana przez filtr bloom przy użyciu wielu funkcji skrótu, a odpowiednie pozycje są oznaczone jako 1, w ogromnej tablicy zer. Powiedzmy, że chcemy fałszywie dodatniego wskaźnika 1%, używając kalkulatora filtra bloom ( http://hur.st/bloomfilter?n=1000000&p=0.01), uzyskujemy rozmiar wymaganego filtra bloom jako zaledwie 1,13 MB. Ten mały rozmiar jest oczekiwany, ponieważ mimo że rozmiar tablicy jest ogromny, przechowujemy tylko 1 lub 0, a nie adresy URL, jak w przypadku tablicy haszującej. Tablicę tę można traktować jako tablicę bitową. To znaczy, ponieważ mamy tylko dwie wartości 1 i 0, możemy ustawić pojedyncze bity zamiast bajtów. Zmniejszyłoby to zajmowane miejsce o 8 razy. Ten filtr bloom o wielkości 1,13 MB dzięki niewielkim rozmiarom może być przechowywany w samej przeglądarce internetowej !! Tak więc, gdy użytkownik przychodzi i wprowadza adres URL, po prostu stosujemy wymagane funkcje skrótu (w samej przeglądarce) i sprawdzamy wszystkie pozycje w filtrze bloom (który jest przechowywany w przeglądarce). Wartość 0 w dowolnej pozycji informuje nas, że ten adres URL ZDECYDOWANIE NIE znajduje się na liście złośliwych adresów URL i użytkownik może swobodnie kontynuować. W ten sposób nie nawiązaliśmy połączenia z serwerem, a tym samym zaoszczędziliśmy czas. Wartość 1 mówi nam, że URL MOŻE znajdować się na liście złośliwych adresów URL. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma 99% racji. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań do zdalnego serwera. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań do zdalnego serwera. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma 99% racji.

Tak więc, używając małego filtra bloom w przeglądarce, zaoszczędziliśmy dużo czasu, ponieważ nie musimy wykonywać wywołań serwera dla każdego wprowadzonego adresu URL.

Widzimy, że tabela skrótów z pojedynczą funkcją skrótu jest używana do zupełnie innego celu niż filtr bloom. Mam nadzieję, że to rozwiąże Twoje wątpliwości :)

edytuj :

Zaimplementowałem filtr bloom do zadania testowania złośliwych adresów URL w Pythonie. Kod można znaleźć tutaj - https://github.com/tarunsharma1/Bloom-Filter Kod jest bardzo prosty do zrozumienia, a szczegółowy opis znajduje się w pliku readme.

Zacznę od wyjaśnienia, czym jest filtr bloom, co może, a czego nie może zrobić, dlaczego go potrzebujemy, pokażę intuicyjny opis jego działania, a następnie podam przykład, kiedy mogą być przydatne.

Zatem standardowy filtr poświaty jest probabilistyczną strukturą danych, która może ^* :

• dodać element do zestawu
• sprawdź, czy element jest w zestawie, mówiąc definitely not in the setlubpossibly in the set

Właśnie possibly in the setdlatego nazywa się to probabilistycznym. Używanie inteligentnych słów oznacza, że fałszywie dodatnie są możliwe (mogą wystąpić przypadki, w których fałszywie uważa, że ​​element jest dodatni), ale fałszywie ujemne są niemożliwe.

Ale nie może ^* :

• usunąć przedmiot z zestawu
• daje listę wszystkich elementów, które są obecnie w twoim zestawie

^* _{Ten zestaw puszek / nie dotyczy podstawowego filtra bloom. Ponieważ jest to użyteczna struktura danych, która została stworzona dawno temu, ludzie odkryli, jak rozszerzyć ją o inne przydatne funkcje.}

Ale poczekaj chwilę: znamy już strukturę danych, która może odpowiedzieć na to wszystko bez niejasnego „możliwego”, a także bez wszystkich ograniczeń (nie można usunąć, nie można wyświetlić wszystkich). Nazywa się to zestawem . I tu pojawia się główna zaleta filtra bloom: zajmuje mało miejsca i zapewnia stałą przestrzeń .

Oznacza to, że nie ma znaczenia, ile elementów tam zgromadzimy, przestrzeń będzie taka sama. Tak, filtr bloom z 10^6elementami (bezużyteczny filtr bloom) zajmie tyle samo miejsca co filtr bloom z 10^20elementami i taką samą przestrzeń jak filtr bloom z 0elementami. Ile to zajmie miejsca? Decyzja należy do Ciebie (ale jest wymiana: im więcej masz elementów, tym bardziej niepewna jest Twoja possible in the setodpowiedź.

Kolejną fajną rzeczą jest to, że jest to stała przestrzenna. Kiedy zapisujesz dane w zestawie, musisz faktycznie zapisać te dane. Więc jeśli przechowujesz this long string in the set, musisz użyć co najmniej 27 bajtów miejsca. Ale dla 1% błędu i optymalnej wartości k ^** będziesz potrzebować ~ 9,6 bitów (<2 bajty) na dowolny element (bez względu na to, czy jest to krótki int, czy duża ściana tekstu).

Inną właściwością jest to, że wszystkie operacje mają stały czas, co absolutnie nie jest tym samym, co zamortyzowany stały czas w przypadku zbiorów (pamiętaj, że jeśli zbiór ma kolizje, może z O(n)czasem ulec pogorszeniu ).

^** _{k jest wartością funkcji skrótu używanej w filtrze bloom}

Nie będę opisywał, jak działają filtry bloom (artykuł na Wikipedii bardzo dobrze wszystko wyjaśnia). Tutaj krótko opowiem o podstawach.

• inicjujesz pustą tablicę bitów długości m
• wybierasz króżne funkcje skrótu (im bardziej niezależne, tym lepiej)
• jeśli chcesz dodać element, obliczasz wszystkie kskróty tej wartości i ustawiasz odpowiednie bity na 1
• jeśli chcesz sprawdzić, czy element istnieje, obliczasz również wszystkie kskróty i jeśli przynajmniej jeden z nich nie jest ustawiony, to na pewno nie ma go w zestawie. W przeciwnym razie może być w zestawie.

Nawet ten opis wystarczy, aby zrozumieć, dlaczego nie możemy być pewni (możesz pobrać wszystkie bity z różnych innych wartości). Oto bardzo ładna wizualizacja tego, jak to działa .

Kiedy więc filtry bloom mogą być przydatne? Krótka odpowiedź jest wszędzie tam, gdzie fałszywie dodatnie są dopuszczalne i gdzie chciałbyś sprawdzić, czy coś jest w zestawie , ale nawet jeśli tak nie jest, może to być pierwsza linia obrony, aby wykluczyć drogie wezwania do weryfikatorów.

Oto lista bardziej konkretnych opisów:

• standardowy przykład złośliwych stron internetowych i przeglądarki jest opisywany w prawie każdym miejscu, w którym ludzie mówią o filtrach bloom
• jest słabym hasłem: zamiast mieć ogromny zestaw wszystkich możliwych słabych haseł, możesz po prostu sprawdzić, czy hasło na pewno nie jest słabe za pomocą o wiele mniejszego filtra bloom
• jeśli masz listę artykułów i listę użytkowników, możesz użyć filtra bloom, aby wyświetlić artykuły użytkowników, których nie przeczytali. Ciekawostką jest to, że możesz mieć tylko jeden filtr (sprawdzasz, czy jest tam kombinacja user_id + article_id)
• Bitcoin używa filtra Bloom do synchronizacji portfela
• Serwery sieciowe Akamai używają filtrów Bloom, aby zapobiec przechowywaniu „cudów za jednym trafieniem” w pamięci podręcznej dysku. Cuda za jednym trafieniem to obiekty internetowe, o które użytkownicy proszą tylko raz, co, jak ustalił Akamai, dotyczyło prawie trzech czwartych ich infrastruktury buforowania. Użycie filtru Blooma do wykrycia drugiego żądania obiektu internetowego i buforowanie tego obiektu tylko przy drugim żądaniu zapobiega przedostawaniu się cudów za jednym trafieniem do pamięci podręcznej dysku, znacznie zmniejszając obciążenie dysku i zwiększając współczynniki trafień w pamięci podręcznej dysku (wzięte z przykładów w filtrze Blooma artykuł na wiki)

Filtry Blooma są bardzo przydatne w bioinformatyce. Mogą być bardziej wydajne pod względem miejsca w porównaniu ze zwykłym hashem, zwłaszcza gdy rozmiar ciągów, z którymi pracujesz, może wynosić setki milionów liter z bardzo małym alfabetem, tj. {A, G, T, C}. Są zwykle używane do oceny, czy określony k-mer jest obecny lub nieobecny w genomie. Oto przykład jednego używanego do czegoś istotnego tutaj .

EDYTOWAĆ:

Wielokrotne funkcje skrótu służą do minimalizowania fałszywych alarmów. Istnieje nadzieja, że ​​między wszystkimi funkcjami k-hash każda wartość będzie miała unikalną sygnaturę w tablicy bitów w porównaniu z każdą inną możliwą wartością. Jednak fałszywe alarmy istnieją, ale można je zminimalizować do rozsądnego poziomu. Używając tej techniki, haszujesz elementy niezależnie od ich rozmiaru. Kiedy ich szukasz, używasz każdej funkcji skrótu i ​​sprawdzasz, czy wszystkie ich wartości bitowe to 1.

Porównaj to z ludzkim genomem, gdzie wzrost rozmiaru elementu znacząco zwiększa rozmiar tablicy z haszowaniem (wielkość tabeli to 4 * 4 ^k ). Zakłada się, że kodujesz elementy przy użyciu 2 bitów / literę.

Jeśli filtr Blooma zwraca, że ​​element jest członkiem zestawu, istnieje pewne prawdopodobieństwo fałszywie dodatniego wyniku. Gdyby do wskazania członkostwa w zbiorze użyto tylko jednej funkcji skrótu, prawdopodobieństwo wystąpienia wyniku fałszywie dodatniego byłoby większe niż przy użyciu wielu funkcji skrótu.