AMS Szkic: Szacowanie Skętu Przepływu w Fragmentie Pamięci

Co mierzy moment drugiej częstotliwości

Dla strumienia danych, niech m_i oznaczaj liczbę wystąpień przedmiotu i przez cały strumień. Zerowy moment częstotliwości, F0, liczy liczbę różnych przedmiotów. Pierwszy moment częstotliwości, F1, jest po prostu długością całkowitą strumienia, ponieważ sumuje wszystkie częstotliwości do potęgi pierwszej. Drugi moment częstotliwości, F2, sumuje kwadrat częstotliwości każdego przedmiotu: jest to suma ze wszystkich różnych przedmiotów m_i podniesionych do kwadratu. Kwotowanie częstotliwości przed sumowaniem ma zaskakujący wpływ: nagradza koncentrację i karze rozproszenie. Rozważ dwa strumienie o tej samej całkowitej długości. W jednym milion przedmiotów pojawia się dokładnie raz, więc F2 wynosi milion. W drugim jeden przedmiot pojawia się milion razy, a wszystko inne jest ciche, więc F2 wynosi milion podniesiony do kwadratu, czyli trilion. Oba strumienie mają identyczną długość, ale F2 różni się o sześć rzędów wielkości, ponieważ F2 jest wrażliwy na to, w jaki sposób masa strumienia jest nierównomiernie rozłożona na przedmiotach. To właśnie dlatego F2 nazywa się miarą skośności lub koncentracji: dzieląc F2 przez F1 podniesiony do kwadratu lub porównując F2 z tym, co wytworzyłoby idealnie jednorodne rozłożenie, otrzymujemy znormalizowany poczucie, jak bardzo nierównomierne są częstotliwości przedmiotów. Statyści rozpoznają F2 jako blisko związany z indeksem Herfindala-Hirschmana używanym w ekonomii do pomiaru koncentracji rynku i z ideą prawdopodobieństwa kolizji w teorii informacji, ponieważ F2 podzielone przez kwadrat długości strumienia jest równe prawdopodobieństwu, że dwa losowo wybrane przedmioty ze strumienia są tym samym przedmiotem. Ponieważ F2 nagradza kilka dużych częstotliwości tak bardzo, działa jako wczesny sygnał ostrzegawczy: gdy normalnie sieć rozprasza pakiety na tysiącach przepływów a F2 nagle wzrasta, jest to silna ilościowa wskazówka, że niewielka liczba przepływów, być może atak odmowy usługi lub wadliwa aplikacja, zaczęła dominować ruch, nawet zanim ktokolwiek ręcznie zbadał logi na poziomie przepływu.

Dlaczego F2 ma znaczenie dla rzeczywistych systemów

Poza wykrywaniem anomalii w sieci, F2 pojawia się wszędzie tam, gdzie inżynierowie potrzebują taniego proxy do określania stopnia skośności rozkładu bez tworzenia pełnego rozkładu. Sieć dostarczania treści chce wiedzieć, czy żądania są rozproszone na miliony plików, czy skoncentrowane na kilku wirusowych, ponieważ ta koncentracja determinuje strategię buforowania: silnie skośny wzorzec żądań, czyli wysokie F2 w stosunku do kwadratu F1, oznacza, że mały bufor przechowujący najgorętsze elementy pochłonie większość ruchu, podczas gdy płaski rozkład oznacza, że ​​buforowanie oferuje niewielką korzyść. Optymalizator zapytań baz danych korzystający z F2, ponieważ koszt samołączenia na kolumnie jest dokładnie F2 tego rozkładu wartości kolumny, więc optymalizatory kolejności łączy wykorzystują szacunki F2 do określenia, który kolejność łączy będzie produkować najmniej pośrednich wierszy. Systemy wykrywania oszustw monitorują F2 na oknach przesuwnych źródeł transakcji w celu wychwytywania wybuchu aktywności z niewielkiej liczby kont. Wszystkie te ustawienia mają to samo ograniczenie: strumień jest ogromny, przychodzi raz i nie może być odtworzony tanio, a nie ma miejsca na przechowywanie tabeli bazy danych mapującej każdy unikalny element na jego dokładną liczbę, ponieważ liczba unikalnych elementów, niezależnie od tego, czy są to przepływy, pliki lub identyfikatory kont, może wynosić miliony lub miliardy. Dokładne obliczenie F2 jest trywialne przy nieograniczonym pamięci - utrzymaj licznik na każdy element, zwiększaj go za każdym razem, gdy dotrze, i zsumuj kwadraty na końcu. Całą wartość koncepcji rysunku AMS polega na tym, że szacuje to ilość do ostatecznego błędu względnego, używając pamięci, która jest podliniowa w stosunku do liczby unikalnych elementów, a w praktyce całkowicie niezależna od tej liczby, co czyni go możliwym do wdrażania na kartach linii routerów, przetwarzaczach strumieniowych wbudowanych i innych miejscach, gdzie pamięć jest najcenniejszym zasobem w systemie.

Triki z Losowym Znakiem: Jak Pojedynczy Licznik Szacuje F2

Serce AMS Szkicu jest zaskakująco proste. Przed rozpoczęciem strumienia, ustali się losową funkcję, która przypisuje każdy możliwy element albo do plus jeden, albo do minus jeden, z równą prawdopodobieństwem, i kluczowe jest to, że cztery takie znaki są wzajemnie niezależne – właściwość nazywana czterokrotną niezależnością. Taką funkcję można wygenerować i przechowywać kompaktowo przy użyciu małego haszowania wielomianowego zamiast tabeli wyszukiwania dla każdego elementu, co utrzymuje schemat w efektywności pamięciowej. Utrzymuj pojedynczy, bieżący licznik, nazwijmy go Z, zainicjalizowany zerem. Za każdym razem, gdy element pojawia się w strumieniu, sprawdź jego znak za pomocą haszowania i dodaj ten znak do Z. Po przejściu całego strumienia oblicz Z podniesione do kwadratu jako szacunek. Dlaczego to działa? Rozwiń Z jako sumę wszystkich unikalnych elementów, pomnożoną przez częstotliwość danego elementu i jego losowy znak, a następnie podnieś tę sumę do kwadratu. Kwadrat sumy wyrażeń o znaku daje dwa rodzaje składników: wyrażenia kwadratowe, w których element mnoży się sam ze sobą, oraz wyrażenia krzyżowe, w których dwa różne elementy mnożą się ze sobą. Każde wyrażenie kwadratowe przyczynia się dokładnie do częstotliwości elementu podniesionej do kwadratu, ponieważ znak plus jeden lub minus jeden podnosi się do dokładnie jednego, niezależnie od tego, który znak został wyciągnięty. Każde wyrażenie krzyżowe przyczynia się do iloczynu częstotliwości dwóch różnych elementów pomnożonego przez iloczyn ich dwóch niezależnych losowych znaków, a ponieważ te dwa znaki są niezależne i każdy jest równie prawdopodobny, aby wynosił plus jeden lub minus jeden, oczekiwana wartość ich iloczynu wynosi dokładnie zero. Biorąc oczekiwanie wartości Z podniesionego do kwadratu względem przypadkowości znaków, wyrażenia krzyżowe zanikają i pozostają tylko wyrażenia kwadratowe, co daje dokładnie sumę częstotliwości każdego elementu podniesioną do kwadratu, czyli F2 zgodnie z definicją. Dlatego algorytm nazywany jest obciążonym – średnio, w wyniku przypadkowości haszowania, pojedyncza liczba Z podniesiona do kwadratu równa się dokładnie F2, nawet jeśli pojedyncze uruchomienie wypadnie powyżej lub poniżej prawdziwej wartości ze względu na losowe fluktuacje.”]} 4186.

Kontrola Zmienności: Uśrednianie i Mediana Średnich

Niezawodny oszacowanie, które jest poprawne tylko średnio, nie jest jeszcze przydatne, ponieważ pojedyncza pętla Z kwadratowego może być znacznie odbiegać od F2 z powodu zmienności, a współczynniki krzyżowe mogą nie w pełni wygładzać się w żadnym losowym przebiegu. AMS Sketch kontroluje to w dwóch etapach, często opisywanych jako uśrednianie i następnie obliczanie mediany, znaną również jako mediana średnich. W pierwszym etapie uruchom wiele niezależnych kopii podstawowego oszacowania równolegle, każde z własnym niezależnie wygenerowanym hashem cztero-wyrazowym oraz własnym licznikiem, a także uśrednij ich kwadratowe wartości. Uśrednianie zestawu niezależnych, identycznie rozłożonych, bezstronnych oszacowań nie zmienia oczekiwanej wartości, ponieważ wartość oczekiwana średniej równa się średniej wartości oczekiwanych, ale zmniejsza wariancję o czynnik równy liczbie wykonywanych kopii, ponieważ wariancja średniej niezależnych ilości dzieli się przez liczbę wykonanych kopii. Wybór liczby równoległych kopii proporcjonalny do jednego podniesionego do kwadratu pożądanej względnej błędu epsilon kwadrat, wykorzystując nierówność Czebyszewa, gwarantuje, że uśrednione oszacowanie znajdzie się w małym błędzie względnym F2 z rozsądną pewnością, często przedstawianym jako przynajmniej siedemdziesięci pięć procent prawdopodobieństwa. Drugi etap wzmacnia to prawdopodobieństwo arbitralnie blisko pewności bez ponoszenia znacznych kosztów pamięci: utworzyć kilka niezależnych grup, każda wewnętrznie uśredniona zgodnie z powyższym, a raportować medianę między tymi grupami. Ponieważ średnia każdej grupy jest poprawna z prawdopodobieństwem co najmniej trzech czwartych, prawdopodobieństwo, że większość grup jednocześnie się myli, szybko spada wraz ze wzrostem liczby grup, dzięki granicznemu twierdzeniu Chernoffa, więc podwojenie lub potrójnie zwiększenie liczby grup zmniejsza prawdopodobieństwo niepowodzenia do pomijalnego poziomu, przy jednoczesnym pomnożeniu całkowitej pamięci przez ten sam mały czynnik.

Dlaczego Pamięć Pozostaje Subliniowa

Kluczową obietnicą rysunku AMS Sketch jest to, że jego ślad pamięciowy nie rośnie wraz z n – liczbą unikalnych elementów możliwych do wystąpienia w strumieniu – która może być astronomiczna, ale zamiast tego rośnie tylko z pożądaną dokładnością i pewnością. Każdy pojedynczy licznik Z jest pojedynczą liczbą całkowitą, a ponieważ jest to suma bieżąca z dodawania i odejmowania w ciągu strumienia o długości m, jego wartość nigdy nie przekracza m, więc jej reprezentacja wymaga tylko O(log m) bitów – liczba bitów logarytmiczna względem długości strumienia, zamiast liniowej względem liczby unikalnych elementów. Funkcja haszująca czterokrotnym niezależnym sposobem potrzebna do generowania znaków nie wymaga przechowywania jawnej tabeli z jednym wpisem na każdy możliwy element; zamiast tego może być zbudowana z wielomianu stopnia niskiego nad skończonym polem zdefiniowanym przez kilka losowo wybranych współczynników, więc cała funkcja haszująca opisana jest O(1) słowami pamięci na kopię, niezależnie od liczby unikalnych elementów występujących. Mnożąc przez liczbę równoległych liczników potrzebną do uzyskania pożądanej tolerancji błędu epsilon i przez liczbę grup potrzebną dla pożądanej pewności delta, całkowite wykorzystanie pamięci wynosi O(1 / epsilon kwadrat razy log(1 / delta) razy log m) bitów – ograniczenie to obejmuje tylko cel dokładności, cel pewności i logarytm długości strumienia, bez jakiejkolwiek zależności od liczby unikalnych elementów n. To sprawia, że wykorzystanie pamięci jest naprawdę podliniowe, a w zasadzie stałe względem n: niezależnie od tego, czy strumień zawiera tysiąc różnych przepływów, czy miliard, rysunek zajmuje dokładnie tyle samo pamięci, w starkim kontraście do dokładnej tabeli częstotliwości, której rozmiar rośnie liniowo z rzeczywistą liczbą obserwowanych elementów. Ten kompromis między przestrzenią a dokładnością, rygorystycznie sformalizowany w oryginalnym artykule AMS z 1996 roku, zapoczątkował szerszy obszar algorytmów strumieniowych i rysowania, a ta sama idea losnych znaków pojawia się w późniejszych rysunkach, takich jak Count-Sketch i elementy AMS oparte na niej, w wykrywaniu dominujących elementów.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz AMS Sketch: Estimating Stream Skew in a Sliver of Memory i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.