Czy jest filtr przeciw Bloomowi?

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) = 1$$x$$b(x) = 0$$n(x) = 1$$x$$n(x) = 0$

Następnie ; ; ; , dla niektórych .$Pr[b(x) = 0 | n(x) = 0] = 1$$Pr[b(x) = 0 | n(x) = 1] = \alpha$$Pr[b(x) = 1 | n(x) = 0] = 0$$Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$$0 < \alpha < 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 ( $b'$$0 < \beta < 1$$Pr[b'(x) = 0 | n(x) = 0] = \beta$$Pr[b'(x) = 0 | n(x) = 1] = 0$P r [ b ′ ( x ) = 1 | n ( x ) = 1 ] = $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$$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$

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 + $n$$k$$n = 128$$k = 16$$H$$n+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 $a$$2^k$ $n$$n2^k$

• Aby dodać nową wartość do filtra, oblicz , gdzie oznacza pierwsze bitów, a oznacza kolejne bitów . Niech .$x$i k j n H ( x ) a i = $i \,\|\, j = H(x)$$i$$k$$j$$n$$H(x)$$a_{i} = 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 $x'$a i ′ = j $i' \,\|\, j' = H(x')$$a_{i'} = 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 ≥ $1/2^{n+k}$$n$$n \ge 128$

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 $N$$(N^2-N) / 2^{n+k+1}$$n=128$$k=16$$2^{(n+k)/2} = 2^{72}$

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).$1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$$N$

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 = $n+k=128$$n=128$$k=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 = 256$n=256$$n=256$

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.

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”.

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 .

$v_i$

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. $\ge1$
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ć.