Co to jest zliczanie strat?

Question

Czy ktoś może mi wytłumaczyć algorytm Lossy Counting? Jest to algorytm przesyłania strumieniowego dotyczący wyszukiwania częstotliwości elementów w strumieniu. Dzięki.

Answer 1

Załóżmy, że patrzysz na ruch w profilach na Facebooku. Masz miliardy odsłon. Chcesz dowiedzieć się, które profile są najczęściej odwiedzane. Możesz zachować liczbę dla każdego profilu, ale wtedy będziesz mieć bardzo dużą liczbę zliczeń do śledzenia, z których ogromna większość byłaby bez znaczenia.

W przypadku liczenia stratnego okresowo usuwa się z tabeli bardzo niskie liczby elementów. Najczęściej odwiedzane profile prawie nigdy nie miałyby niskiego poziomu, a gdyby tak się stało, prawdopodobnie nie pozostałyby tam zbyt długo.

Algorytm zasadniczo polega na grupowaniu wejść na bloki lub kawałki i liczeniu w obrębie każdej porcji. Następnie zmniejszasz liczbę każdego elementu o jeden, zrzucając wszystkie elementy, których liczba spada do zera.

Najczęściej odwiedzane profile będą liczone i pozostaną tam. Dowolne profile, które nie trafią zbyt często, spadną do zera w kilku blokach i nie będziesz już musiał ich śledzić.

Należy pamiętać, że ostateczne wyniki są zależne od zamówienia, co zwiększa wagę do ostatnio przetwarzanych liczb. W niektórych przypadkach ma to sens i jest raczej pozytywną stroną, niż wadą. (Jeśli chcesz wiedzieć, które profile są obecnie najbardziej popularne, teraz chcesz ważyc dostęp częściej niż dostęp w zeszłym miesiącu.)

Istnieje wiele udoskonaleń algorytmu. Ale podstawową ideą jest to, aby znaleźć ciężkie hitters bez konieczności śledzenia każdego elementu, okresowo oczyścić swoje liczby z wszelkich elementów, które nie wydają się być ciężkie hitters na podstawie danych do tej pory.

Answer 2

Możesz znaleźć wyjaśnienie, w jaki sposób liczenie strat (i lepkie próbkowanie) działa on this blog post i open-source version here.

Najczęściej oglądane przedmioty "przeżyją". Biorąc pod uwagę próg częstotliwości f, błąd częstotliwości e oraz całkowitą liczbę elementów N, dane wyjściowe można wyrazić w następujący sposób: Elementy z liczbą przekraczającą fN - eN.

Najgorszy przypadek jakiego potrzebujemy (1/e) * log (eN) liczników.

Na przykład, możemy chcieć wydrukować strony Facebooka osób, które dostały uderzenie ponad 20%, z progiem błędu 2% (zasada: błąd = 10% progu częstotliwości).

Dla częstotliwości f = 20%, e = 2%, wszystkie elementy o częstotliwości rzeczywistej przekraczającej f = 20% będą wyprowadzane - nie ma fałszywych negatywów. Ale zaniżamy. Częstotliwość wyjściowa elementu może być mniejsza od jego rzeczywistej częstotliwości o co najwyżej 2%. Fałszywe wyniki mogą pojawić się z częstością między 18% a 20%. Ostatni, żaden element z częstotliwością mniejszą niż 18% nie będzie wyprowadzany.

okno rozmiar 1/E Biorąc pod uwagę następujące gwarancje przytrzymanie:

• Częstotliwości są niedoszacowane przez co najwyżej E * N
• Brak wyników fałszywie ujemnych
• Fałszywe mieć prawdziwą częstotliwością co najmniej f N - e N