Szkic zliczania min

W informatyce szkic liczba -min ( szkic CM ) jest probabilistyczną strukturą danych , która służy jako tabela częstotliwości zdarzeń w strumieniu danych . Używa funkcji mieszających do mapowania zdarzeń na częstotliwości, ale w przeciwieństwie do tablicy mieszającej wykorzystuje tylko przestrzeń podliniową , kosztem przeliczenia niektórych zdarzeń z powodu kolizji . Szkic count-min został wymyślony w 2003 roku przez Grahama Cormode'a i S. Muthu Muthukrishnana i opisany przez nich w artykule z 2005 roku.

Szkice zliczania-minut są zasadniczo tą samą strukturą danych, co zliczające filtry Blooma wprowadzone w 1998 roku przez Fana i in. Jednak są one używane w różny sposób, a zatem mają różne rozmiary: szkic zliczania-min zazwyczaj ma podliniową liczbę komórek, związaną z pożądaną jakością przybliżenia szkicu, podczas gdy zliczający filtr Blooma jest częściej dobierany tak, aby pasował do liczby elementów w zbiór.

Struktura danych

Celem podstawowej wersji szkicu „count-min” jest konsumpcja strumienia zdarzeń, pojedynczo, i policzenie częstotliwości różnych typów zdarzeń w strumieniu. W dowolnym momencie szkic może zostać zapytany o częstotliwość określonego typu zdarzenia $i z$ $.$ typów zdarzeń i zwróci oszacowanie tej częstotliwości mieszczące się w pewnym zakresie odległość prawdziwej częstotliwości, z pewnym prawdopodobieństwem.

Rzeczywista struktura danych szkicu to dwuwymiarowa tablica złożona z $w$ kolumn i $d$ wierszy. Parametry $w$ i $d$ są ustalane podczas tworzenia szkicu i określają zapotrzebowanie na czas i miejsce oraz prawdopodobieństwo błędu, gdy szkic jest pytany o częstotliwość lub iloczyn wewnętrzny . Z każdym z $d$ jest powiązana oddzielna funkcja skrótu; funkcje skrótu muszą być parami niezależne . Parametry $w$ i $d$ można wybrać, ustawiając $w = ⌈ e / ε ⌉$ i $d = ⌈ ln 1/ δ ⌉$ , gdzie błąd odpowiedzi na zapytanie mieści się w współczynniku addytywnym $ε$ z prawdopodobieństwem $1 - δ$ (patrz poniżej) , a $e$ jest liczbą Eulera .

Kiedy pojawia się nowe zdarzenie typu $i$ , aktualizujemy je w następujący sposób: dla każdego wiersza $j$ tabeli zastosuj odpowiednią funkcję haszującą, aby uzyskać indeks kolumny $k = h j (i)$ . Następnie zwiększ wartość w wierszu $j$ , kolumnie $k$ o jeden.

W strumieniu dostępnych jest kilka rodzajów zapytań.

Najprostsze jest zapytanie punktowe , które pyta o liczbę zdarzeń typu $i$ . Szacowana liczba jest podana przez najmniejszą wartość w tabeli dla $ja$ , a mianowicie za $}} _ {i} =\ min _ {j} \ operatorname {liczba} [j, h_ {j} (i)]}$ , gdzie jest tabelą ${\ Displaystyle \ operatorname {liczba}} .$

Oczywiście dla każdego $ja$ , jeden ma , ${a}} _ {i}}$ $jest$ prawdą częstotliwość, z jaką $występowałem$ w strumieniu.

$a}} _ {i} \ równoważnik a_ {i} + \ varepsilon$ gwarancję, że prawdopodobieństwem za $} 1-\ delta }$ , gdzie $\ Displaystyle N = \ suma _ {i \ in {\ mathcal {U}}} a_ {i}}$ to rozmiar strumienia, tj. całkowita liczba elementy widoczne na szkicu.

Zapytanie $między$ iloczyn wewnętrzny pyta o wewnętrzny histogramami reprezentowanymi przez dwa szkice licząco- $\ matematyczna {liczba} _ {b}}$ u .

Niewielkie modyfikacje struktury danych można wykorzystać do naszkicowania innych różnych statystyk strumienia.

Podobnie jak szkic Count , szkic Count-min jest szkicem liniowym. Oznacza to, że mając dwa strumienie, utworzenie szkicu na każdym strumieniu i zsumowanie szkiców daje taki sam wynik, jak połączenie strumieni i utworzenie szkicu na połączonych strumieniach. To sprawia, że szkic można scalać i nadaje się do użycia w ustawieniach rozproszonych oprócz tych przesyłanych strumieniowo.

Redukcja stronniczości i błędów

Jednym z potencjalnych problemów związanych ze zwykłym estymatorem min dla szkiców liczba-min jest to, że są one stronniczymi estymatorami prawdziwej częstotliwości zdarzeń: mogą przeszacowywać, ale nigdy nie lekceważyć prawdziwej liczby w zapytaniu punktowym. Co więcej, chociaż estymator min działa dobrze, gdy rozkład jest silnie skośny, inne szkice, takie jak szkic zliczania oparty na średnich, są dokładniejsze, gdy rozkład nie jest wystarczająco skośny. Zaproponowano kilka odmian szkicu w celu zmniejszenia błędu i zmniejszenia lub wyeliminowania błędu systematycznego.

Aby usunąć obciążenie, estymator hCount* wielokrotnie losowo wybiera d losowych wpisów w szkicu i pobiera minimum, aby uzyskać nieobciążone oszacowanie obciążenia, i odejmuje je.

W Ting wyprowadzono estymator największej wiarygodności (MLE ) . Korzystając z MLE, estymator jest zawsze w stanie dopasować lub poprawić estymator min i działa dobrze, nawet jeśli rozkład nie jest skośny. W tym artykule pokazano również, że operacja debiasingu hCount* jest procedurą ładowania początkowego, którą można skutecznie obliczyć bez losowego próbkowania i którą można uogólnić na dowolny estymator.

Ponieważ błędy wynikają z kolizji mieszania z nieznanymi elementami wszechświata, kilka podejść koryguje kolizje, gdy znanych jest lub pytanych o wiele elementów wszechświata jednocześnie. W przypadku każdego z nich duża część wszechświata musi być znana, aby zaobserwować znaczące korzyści.

Konserwatywne aktualizowanie zmienia aktualizację, ale nie algorytmy zapytań. Aby policzyć $c$ przypadków typu zdarzenia $i$ , najpierw oblicza się oszacowanie ${\ Displaystyle {\ kapelusz {a}} _ {i} = \ min _{j}\mathrm {liczba} [j,h_{j}(i)]}$ , następnie uaktualnia ${\ Displaystyle \ operatorname {liczba} [j, h_ {j} (i)] \ lewa strzałka \ max \ {\ operatorname {liczba} [j, h_ {j$ dla każdego wiersza $j$ . Chociaż ta procedura aktualizacji sprawia, że szkic nie jest szkicem liniowym, nadal można go scalać.

Zobacz też

Notatki

Dalsza lektura

Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N.; Jechanin, Siergiej (2010). Pan-prywatne algorytmy przesyłania strumieniowego . proc. ICS. CiteSeerX 10.1.1.165.5923 .
Schechter, Stuart; Herley, Cormac; Mitzenmacher, Michael (2010). Popularność jest wszystkim: nowe podejście do ochrony haseł przed atakami opartymi na zgadywaniu statystycznym . Warsztaty USENIX na temat gorących tematów w bezpieczeństwie. CiteSeerX 10.1.1.170.9356 .

Linki zewnętrzne

Często zadawane pytania dotyczące liczby minut