Zestaw probabilistyczny bez fałszywych trafień?

35

Tak więc filtry Bloom są całkiem fajne - są zestawami, które obsługują sprawdzanie członkostwa bez fałszywych negatywów, ale z niewielką szansą na fałszywy pozytyw. Ostatnio jednak chciałem mieć „filtr Blooma”, który gwarantuje coś przeciwnego: żadnych fałszywych alarmów, ale potencjalnie fałszywych negatywów.

Moja motywacja jest prosta: biorąc pod uwagę ogromny strumień przedmiotów do przetworzenia (z duplikatami), chcielibyśmy uniknąć przetwarzania przedmiotów, które widzieliśmy wcześniej. Przetwarzanie duplikatu nie zaszkodzi, to tylko strata czasu. Gdybyśmy jednak zaniedbali przetwarzanie elementu, byłoby to katastrofalne. Dzięki „odwrotnemu filtrowi Blooma” można przechowywać widoczne przedmioty przy niewielkim nakładzie miejsca i unikać przetwarzania duplikatów z dużym prawdopodobieństwem, testując członkostwo w zestawie.

Jednak nie mogę znaleźć czegoś takiego. Najbliższe, jakie znalazłem, to „ wyretuszowane filtry Blooma ”, które pozwalają handlować wybranymi fałszywie dodatnimi wynikami w celu uzyskania wyższego wskaźnika fałszywie ujemnych wyników. Nie wiem jednak, jak dobrze radzi sobie ich struktura danych, gdy chce się usunąć wszystkie fałszywe alarmy.

Ktoś widział coś takiego? :)

Christopher Monsanto
źródło
3
Uzupełnienie zestawu, którym jestem zainteresowany, jest nieskończone. Jak mam to przechowywać?
Christopher Monsanto
11
Widzę problem (współczesne dyski nie są jeszcze wystarczająco duże).
Dave Clarke
8
Jeśli posiadasz taką strukturę danych, możesz użyć jej do „oszukiwania”, używając jej w połączeniu z regularnym filtrem kwitnienia i przechowując dokładny zestaw członkostwa.
Mark Reitblatt
1
@ MarkReitblatt zarówno filtry Bloom, jak i pamięci podręczne są probabilistyczne, a każda ich kombinacja będzie probabilistyczna, tj. Nie będzie w stanie osiągnąć dokładnego zestawu testów członkostwa. :)
awdz9nld

Odpowiedzi:

25

Jedną z odpowiedzi jest użycie dużej tabeli skrótów, a kiedy się zapełni, zacznij zastępować w niej elementy zamiast znajdować (nieistniejące) puste miejsca w innych miejscach. Nie dostajesz ładnej stałej liczby fałszywych odpowiedzi, którą robisz z filtrami Bloom, ale jest to lepsze niż nic. Uważam, że jest to standard, np. W oprogramowaniu szachowym do śledzenia pozycji, które zostały już przeszukane.

David Eppstein
źródło
Dziękuję za odpowiedź. Tak, to oczywiste rozwiązanie - jeśli jest to również standardowe rozwiązanie, brzmi jak brak szczęścia. No cóż.
Christopher Monsanto
2
Nazywa się to pamięcią podręczną z mapowaniem bezpośrednim i jest powszechnie stosowane w procesorach. (Każdy zestaw pamięci podręcznej lub stratnego zestawu skrótów spełnia wymagania w różnym stopniu). Współczynnik błędów jest funkcją rozkładu funkcji skrótu (lawina) i liczby gniazd dostępnych w pamięci podręcznej / zestawie - odpowiednio dostosuj. :)
awdz9nld,
Zwróć też uwagę, że tylko klucze dosłowne można przechowywać bez wprowadzania fałszywych alarmów (np. Przechowywanie klucza mieszanego)
awdz9nld
20

Odpowiedź na to pytanie brzmi „nie”. Aby zrozumieć dlaczego, możemy pomyśleć o bardzo ekstremalnym przypadku i o tym, jak działałby zwykły filtr kwitnienia w porównaniu z teoretycznym filtrem kwitnienia „Bizzaro World”, który możemy nazwać „filtrem mroku”.

Wspaniałe w filtrze Bloom jest to, że można wykonywać jednostronne testy przynależności do elementów (z fałszywymi trafieniami) przy użyciu struktury danych o ustalonym rozmiarze w odniesieniu do prawdopodobieństwa błędu i liczby przechowywanych elementów. Te rozmiary tych elementów sami nie mają znaczenia w ogóle. Na przykład, gdybyśmy skonfigurowali filtr Blooma do przechowywania do 1000 elementów z mniejszym niż 3% błędem, wówczas moglibyśmy przechowywać 1000 nieco różnych wersji całego korpusu Wikipedii, z jedną literą zmienioną w każdej, i nadal byśmy uzyskamy potrzebne mi dane, a struktura danych byłaby bardzo mała (mniej niż kilobajt). Oczywiście obliczenie tych skrótów będzie wyzwaniem, ale zasada nadal obowiązuje.

Teraz rozważ przechowywanie tych samych masywnych strun w filtrze mroku! Teraz możemy mieć tylko fałszywe negatywy. Jeśli więc powiemy „tak, ta wersja całego korpusu Wikipedii znajduje się w tym zestawie”, musimy mieć całkowitą rację. Oznacza to, że haszowanie nam nie pomoże, ponieważ zawsze będzie jakiś inny ciąg hashujący do tej samej wartości. Jedynym sposobem, aby powiedzieć „tak” i mieć pewność, jest zapisanie całego łańcucha lub niektórych równoważnych danych o tej samej długości. Zawsze nie mogliśmy tego zapisać i powiedzieć „nie”, ale ostatecznie poziom błędu nas dogoni. Najlepsze, co mogliśmy zrobić, to kompresja, sprowadzenie rozmiaru struktury do iloczynu entropii przechowywanych danych i pożądanej dokładności.

Więc niestety filtr mroku nie istnieje. Buforowanie jest jedynym rozwiązaniem, ale tak naprawdę nie jest przeciwieństwem filtra Blooma, ponieważ jego rozmiar będzie proporcjonalny do iloczynu ilości przechowywanych informacji i pożądanego stopnia dokładności filtra. Oczywiście w wielu rzeczywistych sytuacjach duże dane mogą być reprezentowane przez identyfikator, więc buforowanie może być nadal całkiem akceptowalne. Ale zasadniczo różni się od potężnego filtra kwitnienia.

pents90
źródło
Zamówienie somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - co jest złego w tym realizacja /
Yehosef
@ Yehosef jest w porządku i może działać na twoje potrzeby, ale zauważysz, że autor mówi o istnieniu „kilku identyfikatorów, które całkowicie identyfikują zdarzenie”. Tak więc to, co zostaje zaimplementowane, nadal skutecznie przechowuje cały obiekt. Jest to wariant pamięci podręcznej. Prawdziwe „przeciwieństwo filtru kwitnienia”, jeśli istniałoby, nie musiałoby przechowywać całych obiektów.
pents90
Wspomniał o kilku identyfikatorach identyfikujących zdarzenie - nie o całym obiekcie. Muszę tylko zachować „pamięć podręczną” na session_id - nie cały rekord interakcji. Ale słyszę, że to nie jest ten sam rodzaj podejścia, co rozkwit lub hiperlog.
Yehosef,
W swoim „dowodzie” zakładasz, że istnieje nieograniczona liczba możliwych wpisów. Są jednak przypadki, w których zestaw możliwych wpisów jest znany z góry. Na przykład, w przypadku wyrzucania elementów bezużytecznych ze strony pamięci: wiesz, które wpisy w niej zawierają. Teraz tworzysz „filtr mroku”, który mapuje każdy możliwy wpis na indeks 0..n. Teraz, gdy pozycja zostanie usunięta, ustaw bit na ten indeks. Po ustawieniu wszystkich bitów możesz wyrzucić śmieci do strony. „Filtr mrokowy” to MPHF. Aby zezwolić na fałszywe negatywy, zmień MPHF tak, aby niektóre wpisy były mapowane na n + 1.
Thomas Mueller
@ThomasMueller Zgadza się, zakładam przypadek najgorszy / przeciwny, który jest standardowym punktem widzenia teorii CS. Prawdą jest, że jeśli masz tylko stały zestaw N możliwych wpisów, istnieje wiele prostych rozwiązań, przy czym tylko log N wymaga miejsca na każdy element. Jednak filtr Bloom nie ma takich ograniczeń.
pents90
13

Chcesz tylko pamięci podręcznej , ale zastanawiasz się nad tym w dziwny sposób.

Craig Gidney
źródło
1
... Możesz rozwinąć temat? Oczywiście pamięć podręczna działałaby, ale nie jest to idealne, stąd pytanie o aktualny stan wiedzy w probabilistycznych strukturach danych. Mówiąc dokładniej: znane mi techniki buforowania wymagają dużo pamięci. Im więcej poziomów pamięci podręcznej, tym więcej zajętego miejsca. Można umieścić ograniczenie na elementach przechowywanych w pamięci podręcznej, wykonywać sztuczki z wzorcami użycia itp., Ale to wciąż nie zbliża się do współczynnika wydajności miejsca do fałszywej odpowiedzi zapewnianego przez filtr Bloom.
Christopher Monsanto
1
(ciąg dalszy) Powiedziawszy to, mogę zapomnieć o oczywistej technice buforowania, która rozwiązuje wszystkie moje problemy. W takim razie możesz podać tę technikę zamiast podawać link do ogólnej kategorii na Wikipedii?
Christopher Monsanto
2

ZASTRZEŻENIE: Nie jestem ekspertem w dziedzinie pamięci podręcznych, więc może to być naiwny pomysł, a także może być znany pomysł, o którym nigdy wcześniej nie słyszałem. Więc przepraszam, jeśli nie przytoczę jego odniesienia (jeśli istnieje); i poinformuj mnie, czy istnieje odniesienie do edycji postu i dodania go. (Podejrzewam, że może mieć referencję, ponieważ jest tak intuicyjna).

Szybkie rozwiązanie, zainspirowane Strilanc, może po prostu zachować asocjacyjną mapę maksymalnych wpisów (gdzie jest stałe), kojarząc element z liczbą wyświetleń. Gdy mapa asocjacyjna jest pełna i napotkasz nowy przedmiot, którego nie ma na mapie, odwróć monetę, aby ją dodać lub nie. Jeśli chcesz go dodać, usuń element z prawdopodobieństwem odwrotnie proporcjonalnym do liczby wyświetleń.ccc

M. Alaggan
źródło
0

Użyłem drzew AVL (a czasem czerwono-czarnych) z częściowymi elementami, które działają jak filtr bez fałszywych negatywów. Używaj tylko pierwszych X bajtów elementu podczas wstawiania lub zapytania drzewa. Ponieważ struktura danych nie ma postaci probabilistycznej, nie ma ryzyka fałszywie dodatniego wyniku kolizji bitów. I w przeciwieństwie do buforowania całego przedmiotu, to podejście daje obliczalne maksymalne miejsce. Możesz dostroić liczbę fałszywych alarmów, biorąc pod uwagę różne długości prefiksów / głębokości drzewa w porównaniu do kosztu fałszywych alarmów i przestrzeni.

JRideout
źródło
Chciałem też spróbować prób z danymi ciągowymi, ale moje dane są zwykle zapakowane w struktury binarne.
JRideout
0

Myślę, że można udowodnić dolną granicę, stwierdzając, że powyższa struktura danych nie może istnieć. Zasadniczo, jeśli struktura danych wykorzystuje m bitów, to ustalony wektor bitowy (reprezentacja wejścia) może odpowiadać co najwyżej (((un) + n eps) \ select (un)) zestawom przez argument zliczający. Biorąc pod uwagę, że 2 ^ m razy liczba ta musi być co najmniej (u \ wybierz n) (wszystkie zbiory muszą być reprezentowane), otrzymujemy dolną granicę, która jest zasadniczo bardzo bliska dokładnego przechowywania zbioru S.

Mayank
źródło