Count-Min Sketch: Szacowanie Częstotliwości Bez Przechowywania Wszystkiego

Dlaczego Dokładne Liczenie Zawodzi w Dużej Skali

Dokładne liczenie, jak często pojawia się każdy element w strumieniu, wydaje się proste: utrzymuj mapę skojarzeniową z elementu do liczby wystąpień i zwiększaj odpowiedni wpis na każde zdarzenie. Problem polega na pamięci. Jeśli strumień zawiera setki milionów unikalnych elementów, takich jak unikalne adresy IP trafiające do serwera, unikalne zapytania wyszukiwania lub unikalne identyfikatory produktów w strumieniu handlowym, mapa skojarzeniowa sama w sobie rośnie, aby przechowywać każdy pojedynczy klucz, a także dodatkowe koszty związane z wskaźnikami, pojemnościami i łańcuchami kolizji. W wielu systemach rzeczywistych liczba unikalnych elementów jest nieograniczona lub nieznana z góry, a strumień nigdy się nie kończy, więc nie ma punktu, w którym można byłoby po prostu przestać rozszerzać mapy. Gorsze jeszcze, wiele aplikacji interesuje się jedynie przybliżonymi odpowiedziami: czy ten adres IP jest ciężkim użytkownikiem, czy to zapytanie jest niezwykle popularne, czy ten produkt jest trendujący. W tych przypadkach marnowaniem gigabajtów pamięci RAM byłoby wydawanie pieniędzy na uzyskanie idealnie dokładnej liczby, gdy wystarczająca przybliżona odpowiedź obliczona przy kilku kilobajtach mogłaby być równie dobra. To właśnie tę lukę wypełnia Count-Min Sketch. Oddaje on dokładność w zamian za stały, regulowany budżet pamięci, który nie rośnie wraz z liczbą unikalnych elementów, tylko z pożądanego poziomu dokładności i poziomu ufności, co czyni go praktycznym dla strumieni o zasadniczo nieograniczonym rozmiarze i kardynalności.

Struktura: Siatka Liczników i Kilka Funkcji Hashujących

Count-Min Sketch w swojej istocie jest dwuwymiarową siatką liczników, składającą się z d rzędów i w kolumn, wszystkie początkowo ustawione na zero. Każdy rząd posiada niezależną funkcję hashującą, która mapuje każdy przychodzący element na jedną z w kolumn w tym rzędzie. Kluczowe jest to, że rzędy nie reprezentują różnych elementów ani różnych okresów czasu; są one równoległe i niezależne od siebie widokami tego samego strumienia, każdy używający innej funkcji hashującej do rozproszenia elementów na swoich kolumnach. Ponieważ funkcje hashujące są niezależne, element, który przypadkowo koliduje z innym elementem w funkcji hashującego jednego rzędu, bardzo prawdopodobnie nie koliduje z tym samym elementem w innym rzędzie. Ta redundancja jest całą zasadą działania tej struktury: żaden pojedynczy rząd nie może być traktowany jako niezawodny, ponieważ kolizje zawyżają jego liczniki, ale łączenie informacji we wszystkich d rzędach pozwala na wyeliminowanie większości tego szumu. Rozmiar siatki, czyli liczba rzędów i kolumn, jest dobierany z góry w oparciu o poziom akceptowalnego błędu oraz pewność, że ten błąd pozostanie w tym zakresie, a rozmiar ten pozostaje niezmieniony, niezależnie od liczby rozróżnionych elementów, które ostatecznie przejdą przez strumień.

Aktualizacja Szkicu: Hashowanie, Następnie Zwiększanie Licznika

Przetwarzanie nowej wystąpienia elementu jest niezwykle tanie. Dla każdej z d wierszy element jest przekazywany przez funkcję hash tego wiersza, aby obliczyć indeks kolumny, a licznik znajdujący się w tym wierszu i tej kolumnie jest zwiększany o jeden. Dzieje się to raz na wiersz, więc pojedyncze uaktualnienie dotyka dokładnie d liczników łącznie, niezależnie od tego, ile różnych elementów występuje w strumieniu lub jak duża jest siatka. Nie ma wyszukiwania istniejącej wpisy, nie ma powiększania, nie ma łańcuchów i nie ma potrzeby nawet wiedzieć, czy element został wcześniej widziany. Dwa zupełnie różne elementy mogą, a często będą, lądować w tej samej kolumnie w danym wierszu wyłącznie z powodu przypadkowego hashowania, a gdy to się stanie, ich liczby są mieszane w tej komórce. Jest to oczekiwane i akceptowane, ponieważ szkic jest zaprojektowany tak, że nawet jeśli pojedyncze komórki mogą być skażone przez kolizje z innymi elementami, kombinacja wszystkich wierszy podczas zapytania nadal może odzyskać ciasny i niezawodny oszacowanie. Koszt operacji aktualizacji pozostaje stały na przestrzeni życia strumienia, co dokładnie sprawia, że ​​struktura jest odpowiednia dla środowisk o wysokiej przepustowości i czasie rzeczywistym, w których każde zdarzenie musi być przetworzone w stałym, niewielkim czasie.

Zapytanie o Szkic: Dlaczego Minimum Jest Poprawną Odpowiedzią

Aby oszacować, ile razy dany element się pojawił, szkic hashuje ten element za pomocą funkcji hashowej każdej kolumny dokładnie tak, jak podczas aktualizacji, wyszukuje wartość licznika w każdym uzyskanym miejscu i następnie raportuje minimum tych *d* wartości jako szacunek częstotliwości. Powód wyboru minimum zamiast średniej lub maksimum wynika z jednokierunkowego charakteru błędu zaangażowanego. Każdy licznik w siatce może być jedynie powiększony przez kolizje z innymi elementami współdzielącymi tę samą komórkę; kolizja nigdy nie powoduje, że licznik będzie niedoszacowywany, ponieważ liczniki są zawsze inkrementowane, nigdy zdekrementowane. Oznacza to, że w każdej pojedynczej kolumnie wartość licznika na pozycji elementu haszowanego jest gwarantowana jako większa lub równa prawdziwej liczbie wystąpień tego elementu, ponieważ równa się prawdziwej liczbie plus wszelkie dodatkowe inkrementy pochodzące z kolizji. Ponieważ prawdziwa liczba wystąpień jest dolnym ograniczeniem w każdej kolumnie, a różne kolumny tendencją do cierpią na różne, zasadniczo niezależne kolizje, kolumna o najmniejszym stopniu zanieczyszczenia wygeneruje wartość najbliższą prawdy. Wezwanie minimum we wszystkich kolumnach zatem wybiera najbardziej precyzyjną, najmniej zniekształconą szacunkową wartość dostępną i matematycznie gwarantuje, że prawdziwa liczba wystąpień jest zawsze mniejsza lub równa tej minimalnej wartości, więc szacunek nigdy nie spada poniżej rzeczywistości, może być tylko równy lub nieco powyżej niej.

Wymiana Pamięci na Dokładność i Gdzie Jest Używana

Dokładność Count-Min Sketch jest bezpośrednio uwarunkowana jego wymiarami. Zwiększenie liczby kolumn, w, rozprasza elementy bardziej równomiernie po każdym rzędzie, zmniejszając szansę na kolizję między dwoma elementami i tym samym redukując typowe nadmierne liczenie. Zwiększenie liczby wierszy, d, dodaje więcej niezależnych okazji do znalezienia wiersza, w którym dany element uniknął poważnej kolizji, co zwiększa pewność, że zwrócona minimalna wartość jest bliska rzeczywistej wartości. Podwajanie jakiejkolwiek z tych wymiarów przybliżone podwoja zużycie pamięci, ale przyniesie odpowiedni wzrost w granicach błędu lub poziomie ufności, dając inżynierom prosty regulator do handlu pamięcią z precyzją, w oparciu o to, co ich aplikacja może znieść. W praktyce ta struktura pojawia się stale w systemach, które muszą tanio podsumowywać ogromne strumienie danych. Operatorzy sieci używają jej do monitorowania ruchu i oznaczania dominujących graczy, czyli adresów IP lub połączeń zużywających nieproporcjonalną przepustowość, bez utrzymywania stanu dla każdego możliwego adresu. Optymalizatory zapytań bazodanowych wykorzystują szkice zbudowane na kolumnach tabel do szacowania liczby wierszy, które pasuje filtr lub łączenie, co wpływa na wybór planu wykonania bez skanowania całej tabeli. Platformy analityki strumieniowej używają jej do odpowiadania na pytania dotyczące tego, które zdarzenia, użytkownicy lub hashtagi są trendem w czasie rzeczywistym, przetwarzając miliony zdarzeń na sekundę przy jednoczesnym utrzymaniu stałego i przewidywalnego zużycia pamięci.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Count-Min Sketch: Estimating Frequencies Without Storing Everything i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.