Czy jest filtr przeciw Bloomowi?

25

Filtr Bloom pozwala efektywnie śledzić, czy różne wartości zostały już napotkał podczas przetwarzania. Gdy jest wiele elementów danych, filtr Bloom może spowodować znaczne oszczędności pamięci w tabeli skrótów. Główną cechą filtra Bloom, który dzieli z tabelą skrótów, jest to, że zawsze mówi „nie nowy”, jeśli element nie jest nowy, ale istnieje niezerowe prawdopodobieństwo, że element zostanie oznaczony jako „nie nowy „nawet gdy jest nowy.

Czy istnieje „filtr przeciw Bloomowi”, który ma przeciwne zachowanie?

Innymi słowy: czy istnieje wydajna struktura danych, która mówi „nowy”, jeśli element jest nowy, ale który mógłby również powiedzieć „nowy” dla niektórych elementów, które nie są nowe?

Przechowywanie wszystkich wcześniej widocznych elementów (na przykład na posortowanej liście połączonej) spełnia pierwsze wymaganie, ale może zużywać dużo pamięci. Mam nadzieję, że jest to również zbędne, biorąc pod uwagę łagodny drugi wymóg.


Dla tych, którzy wolą bardziej formalne leczenie, napisz jeśli filtr Bloom myśli, że jest nowy, przeciwnym razie i napisz jeśli naprawdę jest nowy, a przeciwnym razie.b(x)=1xb(x)=0n(x)=1xn(x)=0

Następnie ; ; ; , dla niektórych .Pr[b(x)=0|n(x)=0]=1Pr[b(x)=0|n(x)=1]=αPr[b(x)=1|n(x)=0]=0Pr[b(x)=1|n(x)=1]=1α0<α<1

Pytam: czy istnieje wydajna struktura danych, implementująca funkcję z pewnymi , tak że ; ; ; ? 0 < β < 1 P r [ b ( x ) = 0 | n ( x ) = 0 ] = β P r [ b ( x ) = 0 | n ( x ) = 1 ] = 0 P r [ b ( x ) = 1 | n ( xb0<β<1Pr[b(x)=0|n(x)=0]=βPr[b(x)=0|n(x)=1]=0P r [ b ( x ) = 1 | n ( x ) = 1 ] = 1Pr[b(x)=1|n(x)=0]=1βPr[b(x)=1|n(x)=1]=1


Edycja: Wygląda na to, że pytanie zostało zadane wcześniej na StackExchange, ponieważ /programming/635728 i /cstheory/6596 z szeregiem odpowiedzi od „nie można „do” można zrobić, za pewnym kosztem „do”, jest to trywialne, poprzez odwrócenie wartości ”. Nie jest jeszcze dla mnie jasne, jaka jest „właściwa” odpowiedź. Co jest jasne, że system buforowania LRU jakiegoś rodzaju (takie jak ten zaproponowany przez Ilmari Karonen) działa dość dobrze, jest łatwe do wykonania, a zakończyło się 50% redukcji czasu potrzebnego do uruchomienia mojego kodu.b

András Salamon
źródło
Z jakiegoś powodu kusi mnie, aby powiedzieć, że jest to bardzo podobne do problemu, który próbują rozwiązać bufory i algorytmy umieszczania buforów. Rozważ pamięć podręczną przy użyciu najczęściej używanej zamiany (LFU). Teoretycznie optymalnym, ale niemożliwym do zastąpienia algorytmem jest eksmisja tego, którego nie zobaczysz przez dłuższy czas, tak samo jak w przypadku pamięci podręcznych. Przypuszczam, że buforowanie opiera się na pewnych założeniach dotyczących charakteru dystrybucji, które mogą się nie utrzymywać ogólnie, ale warto zastanowić się, czy to dotyczy.
Patrick87,
Możesz być zainteresowany następującą rozmową: Filtry członkostwa oparte na satysfakcji
Kaveh
@Kaveh: dzięki za wskaźnik, będzie oglądać.
András Salamon,

Odpowiedzi:

12

Idąc za hasłem Patrick87, oto praktyczna konstrukcja, która prawie spełnia twoje wymagania - prawdopodobieństwo fałszywego pomylenia nowej wartości ze starą nie jest całkiem zerowe, ale można ją łatwo uczynić pomijalnie małym.

Wybierz parametry i ; praktycznymi wartościami mogą być, powiedzmy, i . Niech będzie bezpieczną kryptograficzną funkcją skrótu wytwarzającą (co najmniej) bitów wyjściowych.k n = 128 k = 16 H n + knkn=128k=16Hn+k

Niech być tablicą -bitowych bitstrings. Ta tablica przechowuje stan filtra, używając łącznie bitów. (Nie ma szczególnego znaczenia, w jaki sposób ta tablica jest inicjowana; możemy po prostu wypełnić ją zerami lub losowymi bitami.)2 k n n 2 ka2k nn2k

  • Aby dodać nową wartość do filtra, oblicz , gdzie oznacza pierwsze bitów, a oznacza kolejne bitów . Niech .ixi k j n H ( x ) a i = jij=H(x)ikjnH(x)ai=j

  • W celu sprawdzenia, czy wartość została dodana do filtra, oblicz , jak opisano powyżej, i sprawdzenia, czy . Jeśli tak, zwróć wartość true; w przeciwnym razie zwróci false.i xa i = j ij=H(x)ai=j

Zastrzeżenie 1: Prawdopodobieństwo fałszywie dodatniego (= nowej wartości, o której istnieniu fałszywie twierdzono, że została zauważona), wynosi . Można to zrobić dowolnie małym, przy niewielkich kosztach w przestrzeni dyskowej, zwiększając ; w szczególności, dla , prawdopodobieństwo to jest w zasadzie pomijalne, ponieważ w praktyce jest znacznie mniejsze niż prawdopodobieństwo fałszywie dodatniego wyniku awarii sprzętu. n n 1281/2n+knn128

W szczególności, po sprawdzeniu różnych wartości i dodaniu ich do filtra, prawdopodobieństwo wystąpienia co najmniej jednego fałszywie dodatniego wyniku to . Na przykład przy i liczba odrębnych wartości potrzebnych do uzyskania fałszywie dodatniego wyniku z 50% prawdopodobieństwem wynosi około .( N 2 - N ) / 2 n + k + 1 n = 128 k = 16 2 ( n + k ) / 2 = 2 72N(N2N)/2n+k+1n=128k=162(n+k)/2=272

Twierdzenie 2: Prawdopodobieństwo fałszywie ujemnego (= poprzednio dodanej wartości fałszywie twierdzonej, że jest nowa) nie jest większe niż , gdzie jest liczbą odrębnych wartości dodanych do filtra (lub dokładniej liczbę odrębnych wartości dodanych po tym, jak konkretna badana wartość została ostatnio dodana do filtra). N1(12k)N1exp(N/2k)<N/2kN


Ps. Mówiąc „pomijalnie mały” w perspektywie, 128-bitowe szyfrowanie jest ogólnie uważane za niezniszczalne w obecnie znanej technologii. Uzyskanie fałszywego wyniku pozytywnego z tego schematu przy jest tak samo prawdopodobne, jak ktoś poprawnie zgaduje twój tajny 128-bitowy klucz szyfrujący przy pierwszej próbie . (Przy i jest to około 65 000 razy mniej prawdopodobne).n = 128 k = 16n+k=128n=128k=16

Ale jeśli to nadal powoduje, że czujesz się irracjonalnie zdenerwowany, zawsze możesz przełączyć na ; podwoi twoje wymagania dotyczące przechowywania, ale mogę spokojnie założyć się o każdą sumę, którą zechcesz nazwać, że nikt nigdy nie zobaczy fałszywego wyniku pozytywnego przy - zakładając, że funkcja skrótu i ​​tak nie jest zepsuta.n = 256n=256n=256

Ilmari Karonen
źródło
1
Prawdopodobieństwo to można nie tylko porównać do prawdopodobieństwa awarii sprzętu; można to również uczynić porównywalnym z prawdopodobieństwem zgadnięcia klucza RSA podczas logowania SSH przy pierwszej próbie . IMO to drugie przekazuje praktyczność twojego rozwiązania bardziej niż poprzednie.
R ..
+1 Bardzo fajnie - rozumiem, że rozwiązuje to problem wydajności przestrzeni, pozwalając na pewną (bardzo małą) szansę niepoprawnej odpowiedzi „nie nowa”, gdy przedmiot jest w rzeczywistości nowy. Bardzo praktyczna i dobra analiza.
Patrick87
1
W zastrzeżeniu 1 stwierdza się po prostu, że przyzwoita funkcja skrótu ma małe prawdopodobieństwo kolizji. Jest to prawdą już w praktyce, jeśli wynosi co najmniej 50 lub więcej. W mojej aplikacji i działa świetnie z prostą 64-bitową, nieszyfrowaną, ale szybką funkcją skrótu. n = 44 k = 20n+kn=44k=20
András Salamon
@ AndrásSalamon: To prawda, chociaż bezpieczna funkcja skrótu kryptograficznego faktycznie daje nieco silniejszą gwarancję: mianowicie, że znalezienie kolidujących danych wejściowych jest niepraktyczne, nawet jeśli próbujesz celowo ich szukać. Przy dostatecznie dużej wartości (np. jak zasugerowałem powyżej), oznacza to, że przechowywanie pełnych danych nie jest konieczne, nawet jeśli koszt fałszywie dodatniego wyniku jest wysoki, a nawet jeśli może istnieć aktywny przeciwnik próbujący je znaleźć. Oczywiście, jeśli nie potrzebujesz tak silnej gwarancji, akceptowalne może być nieco wyższe ryzyko kolizji. n = 128nn=128
Ilmari Karonen
1
@Newtopian Powodem, dla którego określiłem kryptograficzną funkcję skrótu, jest to, że dla nich nie ma znanego sposobu na generowanie kolizji bardziej efektywnie niż za pomocą brutalnej siły (tj. Przez testowanie wielu danych wejściowych i wybieranie tych, które kolidują), w przeciwnym razie hasz będzie brany pod uwagę zepsuty (jak, powiedzmy, MD5 jest obecnie). Zatem w przypadku kryptograficznego skrótu możemy dość bezpiecznie założyć, że współczynnik kolizji jest taki sam, jak w przypadku idealnej funkcji losowego mieszania. Użycie uniwersalnej funkcji skrótu lub klucza MAC (z losowym tajnym kluczem) uczyniłoby tę gwarancję jeszcze silniejszą.
Ilmari Karonen,
8

Nie, nie można mieć wydajnej struktury danych z tymi właściwościami, jeśli chcesz mieć gwarancję, że struktura danych powie „nowy”, jeśli jest naprawdę nowy (nigdy, nigdy nie powie „nie nowy”, jeśli jest w rzeczywistości nowy; niedozwolone są fałszywe negatywy). Każda taka struktura danych będzie musiała zachować wszystkie dane, aby zawsze odpowiadać „nie nowe”. Dokładne uzasadnienie można znaleźć w odpowiedzi pents90 na cstheory .

Natomiast filtry Blooma mogą uzyskać gwarancję, że struktura danych powie w sposób „nie nowy”, jeśli nie jest nowa, w efektywny sposób. W szczególności filtry Bloom mogą być bardziej wydajne niż przechowywanie wszystkich danych: każdy pojedynczy element może być dość długi, ale rozmiar filtra Blooma skaluje się wraz z liczbą elementów, a nie ich całkowitą długością. Każda struktura danych dla twojego problemu będzie musiała być skalowana wraz z całkowitą długością danych, a nie liczbą elementów danych.

jbapple
źródło
Zobacz także zaakceptowaną odpowiedź, ponieważ pytanie jest takie samo
Joe
-1 Prawdopodobnie powinieneś określić, co masz na myśli, gdy mówisz, że nie jest to możliwe. Oczywiście można to zrobić efektywnie, a także można to zrobić przy niskim poziomie błędu, więc osiągnięcie równowagi w danym wdrożeniu powinno być wykonalne ... w szczególności przydatne byłoby wyjaśnienie, co dokładnie oznacza „wszystkie dane kiedykolwiek”, ponieważ nie jest to absolutnie konieczne, aby zaspokoić pytanie. Fałszywe negatywy - odpowiadanie „nowe”, gdy odpowiedź powinna być „nie nowa” - są tutaj dozwolone, więc nie wszystkie dane muszą być przechowywane.
Patrick87
1
Ta odpowiedź jest całkowicie rozsądna i wydaje się odnosić do litery mojego pytania, ale być może nie do ducha.
András Salamon
@DW Dziękujemy za poświęcenie czasu na aktualizację odpowiedzi. Skłaniam się do pozostawienia tej odpowiedzi teraz, chociaż nadal sprzeciwiam się językowi używanemu przy opisywaniu nieefektywności filtrów przeciwzakłóceniowych, oprócz myślenia, że ​​najlepiej byłoby rozwinąć nieco więcej na temat wspomnianych „szczegółów”. .. pozostawiając na razie -1. Usunięto kilka przestarzałych komentarzy.
Patrick87,
@DW Przez „fałszywie negatywny” zamierzam odpowiedzieć „nowy”, gdy odpowiedź powinna być „nie nowa”. (Nieco intuicyjnie, pozytywny przypadek to „nie nowy”). Nie musisz zapisywać „wszystkich danych”, aby to zrobić, chociaż jestem skłonny wierzyć, że musisz zapisać całe elementy (po prostu nie wszystkie elementy - chyba że jesteś gotów zaakceptować hipotetycznie znaczącą szansę na błąd, zgodnie z inną odpowiedzią na pytanie tutaj).
Patrick87,
6

Co powiesz na tylko tablicę haszującą? Gdy zobaczysz nowy element, sprawdź tabelę skrótów. Jeśli miejsce przedmiotu jest puste, zwróć „nowe” i dodaj przedmiot. W przeciwnym razie sprawdź, czy miejsce przedmiotu jest zajęte przez przedmiot. Jeśli tak, zwróć „nie nowy”. Jeśli miejsce jest zajęte przez inny przedmiot, zwróć „nowy” i zastąp miejsce nowym.

Na pewno zawsze poprawnie otrzymasz „Nowy”, jeśli nigdy wcześniej nie widziałeś skrótu przedmiotu. Na pewno zawsze poprawnie otrzymujesz komunikat „Nie nowy”, jeśli widzisz skrót przedmiotu tylko wtedy, gdy widziałeś ten sam przedmiot. Jedyny raz, gdy dostaniesz „Nowy”, gdy poprawna odpowiedź to „Nie nowy”, to jeśli zobaczysz pozycję A, następnie zobaczysz pozycję B, następnie ponownie zobaczysz pozycję A, a zarówno A, jak i B mieszają się z tym samym. Co ważne, nigdy nie można niepoprawnie wyświetlić „Not New”.

Patrick87
źródło
1
Przypuszczam, że ten rodzaj ignoruje problem z wydajnością przestrzeni, a raczej jest znacznie mniej wydajny niż byłby filtr Bloom, ponieważ filtr Bloom naprawdę potrzebuje tylko trochę na wiadro, a to wymaga tyle miejsca na wiadro, ile zajmuje miejsce reprezentują przedmioty. No cóż ... chyba że wszechświat jest skończony (jak w odpowiedzi Wandering Logic) Myślę, że prawdopodobnie nie możesz bardzo zbliżyć się do wydajności kosmicznej filtra Bloom.
Patrick87,
Osobiście uważam, że twoja odpowiedź jest znacznie lepsza niż moja. Filtr Bloom jest nie tylko trochę na wiadro, jeśli chcesz prawdopodobieństwo większe niż 50%. Ma również ustalony rozmiar i po wypełnieniu go w ponad połowie pełna gwałtownie wzrasta prawdopodobieństwo fałszywych trafień. Nie ma wygodnego sposobu na rozwinięcie go, żadnego wygodnego sposobu użycia go jako pamięci podręcznej i żadnego wygodnego sposobu usuwania elementów. Za każdym razem wezmę stół haszujący .
Wandering Logic
@WanderingLogic Użycie małego licznika nasycenia zamiast pojedynczego bitu umożliwia obsługę usuwania (kosztem pojemności i oczywiście tylko wtedy, gdy licznik nie jest na maksimum).
Paul A. Clayton
4

W przypadku, gdy wszechświat elementów jest skończony, to tak: wystarczy użyć filtra Bloom, który rejestruje, które elementy są poza zestawem, a nie w zestawie. (Tj. Użyj filtru Bloom, który reprezentuje dopełnienie zbioru zainteresowań).

Miejsce, w którym jest to przydatne, umożliwia ograniczenie formy usuwania. Trzymasz dwa filtry Bloom. Zaczynają puste. Podczas wstawiania elementów wstawiasz je do filtra Bloom A. Jeśli później chcesz usunąć element, wstaw ten element do filtra Bloom B. Nie ma możliwości cofnięcia usunięcia. Aby wykonać wyszukiwanie, najpierw wyszukaj w filtrze Bloom A. Jeśli nie znajdziesz pasującego elementu, element nigdy nie został wstawiony (z prawdopodobieństwem 1). Jeśli znajdziesz dopasowanie, element mógł (ale nie musi) zostać wstawiony. W takim przypadku przeprowadzasz wyszukiwanie w filtrze rozkwitu B. Jeśli nie znajdziesz dopasowania, element nigdy nie został usunięty. Jeśli znajdziesz dopasowanie w filtrze rozkwitu B, element prawdopodobnie został wstawiony, a następnie usunięty.

To tak naprawdę nie odpowiada na twoje pytanie, ale w tym ograniczonym przypadku filtr rozkwitu B działa dokładnie tak, jak chcesz.

Badacze filtrów Real Bloom używają znacznie bardziej wydajnych sposobów przedstawiania usunięcia, patrz strona publikacji Mike'a Mitzenmachera .

Wędrująca logika
źródło
W tym pytaniu przetwarzamy elementy i nie ma żadnych usunięć. Nie ma sensownego sposobu na przechowywanie komplementu bez konieczności usuwania przedmiotów z filtra Bloom
Joe
1
@Joe: Zgadzam się, że problem jest ogólnie nierozwiązywalny, dlatego ograniczyłem moją odpowiedź do przypadku, gdy uzupełnienie było skończone i małe.
Wandering Logic
1

vi

Przykładem mogą być adresy IP i chcesz wiedzieć za każdym razem, gdy pojawia się coś, czego nigdy wcześniej nie widziałeś. Ale wciąż jest to zestaw skończony, więc wiesz, czego możesz się spodziewać.

Rzeczywiste rozwiązanie jest proste:

  1. Dodaj wszystkie elementy do filtra liczenia kwitnienia.
  2. 1
  3. Po zobaczeniu nowego elementu odejmij go z filtra.

Więc możesz mieć wartości „fałszywie dodatnie”, które były rzeczywiście stare, ale rozpoznane jako nowe. Jednak nigdy nie dostaniesz „nie nowego” dla nowej wartości, ponieważ jej wartość będzie nadal znajdować się we wszystkich gniazdach i nikt inny nie mógł jej zabrać.

Thomas Ahle
źródło