Artykuł ten twierdzi, że tradycyjna analiza poziomu błędu w filtrach Blooma jest nieprawidłowa, a następnie przedstawia długą i niepraktyczną analizę rzeczywistego poziomu błędu. Powiązany artykuł został opublikowany w 2010 r., Ale widziałem, że tradycyjna analiza filtrów Blooma jest nadal nauczana w ramach różnych kursów algorytmów i struktur danych.
Czy tradycyjna analiza filtrów Blooma jest rzeczywiście nieprawidłowa?
Dzięki!
Odpowiedzi:
Tradycyjna analiza jest w porządku. „Tradycyjna” analiza jest, jeśli jest właściwie wyjaśniona, przybliżeniem; opiera się na obliczeniu oczekiwanej liczby komórek, które są 0/1 po wpisaniu kluczy do filtra, a następnie analizie, jakby to była rzeczywista liczba. Chodzi o to, że liczba komórek, które są 0 (lub 1), są ściśle skoncentrowane wokół ich oczekiwań, więc jest to dobre przybliżenie. To było dobrze znane i myślę, że można je znaleźć nawet w moim artykule z Andrei Broderem.
Ten artykuł mówi, że tak naprawdę wydajność filtra Blooma jest zmienną losową (odpowiadającą faktycznemu ułamkowi wpisów 0/1), a jeśli chcesz dokładnie obliczyć tę wydajność z jakiegoś powodu, musisz wykonać kombinatorykę. W przypadku mniejszych filtrów zobaczysz prawdopodobnie nietrywialną różnicę.
Rozmawiałem z autorami tego artykułu. Ich analiza jest dobra i dobra (choć twierdzę, że nie jest głęboka ani nowa); motywacja, że „tradycyjna analiza jest błędna” była, jak sądzę, przesadzona.
Dodam do odpowiedzi Michaela, że w przypadku podzielonych filtrów Blooma, w których funkcje skrótu mają rozłączne zakresy, tradycyjna analiza jest rzeczywiście poprawna bez przybliżenia lub żadnych granic stężenia. Wynika to z faktu, że prawdopodobieństwo błędu dla różnych funkcji skrótu staje się niezależne, a nie skorelowane. Kompromis między spacją / błędem dla podzielonych filtrów Bloom jest zasadniczo taki sam, jak w przypadku tradycyjnych filtrów Bloom, więc myślę, że jest to dobry wariant do nauczania.