Seria o algorytmach szacowania liczby unikalnych wartości w multizbiorze jest kontynuowana artykułem o najnowocześniejszym algorytmie HyperLogLog. Jednak wszystkie pomysły stojące za tym algorytmem opierają się na wcześniej opisanym LogLog, więc jeśli chcesz czytać dalej, upewnij się, że dobrze znasz LogLog.

Algorytm LogLog miał dwa główne problemy:

Wartości odstające

Wynikowe oszacowanie LogLog jest bardzo podatne na wartości odstające, które są bardzo odległe od innych wartości. Dzieje się tak, ponieważ zazwyczaj większość maksymalnych długości prefiksów null dla każdej grupy jest mniej więcej taka sama, na przykład między 12 a 15, ale potem bum - i jeden sufiks null ma długość 27. Ta duża różnica spowoduje bałagan w wynikowym oszacowaniu liczby unikatów, ponieważ klasyczna średnia arytmetyczna nie radzi sobie z tym zbyt dobrze. Zasadniczo ta sama zasada zadziałała, gdy kilku najlepszych menedżerów i dyrektorów podniosło średnią płacę w kraju swoimi wysokimi pensjami.

Autorzy algorytmu próbowali sobie z tym poradzić, pozbywając się wartości odstających i nie uwzględniając kilku najwyższych szczytów w średniej, ale nie było to zbyt dobre rozwiązanie. Później wypróbowali inne podejście - zamiast używać średniej arytmetycznej, użyli średniej harmonicznej, która ma znacznie lepsze właściwości, gdy mamy wartości dalekie od średniej.

Bardzo złe wyniki dla małych kardynalności

LogLog ma fatalne wyniki, gdy musi oszacować kardynalność małych wielokrotności. Jeśli mamy kilka unikalnych elementów w multizbiorze, LogLog zwróci bezsensownie duże oszacowanie. Autorzy rozwiązali to w fantazyjny sposób - w przypadku, gdy jako dane wejściowe mamy multizbiór o niskiej kardynalności, nie używamy LogLog, ale używamy zupełnie innego algorytmu, a mianowicie starego znanego zliczania liniowego. No tak, ale skąd mamy wiedzieć, że na wejściu mamy multizbiór o niskiej kardynalności, skoro nie znamy jego kardynalności?

Pozwalamy LogLog oszacować liczbę unikalnych elementów, a gdy stwierdzimy, że oszacowanie to jest stosunkowo niskie, odrzucamy oszacowanie i ponownie obliczamy je za pomocą algorytmu liczenia liniowego. Przypomnijmy szybko, jak działa liczenie liniowe. Zaczynamy od przydzielenia zerowej (bitowej) tablicy o pewnym z góry określonym rozmiarze, zazwyczaj potędze dwójki. Przeszukujemy wszystkie elementy multizbioru, obliczamy ich hash i konwertujemy go na liczbę całkowitą i z przedziału od 0 do długości tablicy minus 1. Następnie przechowujemy jedynkę w indeksie i w tablicy. Na koniec zliczamy liczbę zer i jedynek w tablicy i używamy prostego wzoru do oszacowania jej kardynalności.

Algorytm LogLog nie używa jednak żadnej tablicy bitów do "przechowywania" obliczonych skrótów. Zamiast tego używa tablicy, w której przechowuje maksymalne długości sufiksów. Na przykład, tablica może wyglądać następująco:

[2, 5, 9, 0, 5, 4, 4, 0]

gdzie każda liczba wskazuje maksymalną długość sufiksu null w tej grupie obliczonych skrótów. Jednak niezerowa wartość na i-tej pozycji musi oznaczać, że wśród wartości w multizbiorze znajduje się element, którego (trzybitowy) hash jest równy i. Innymi słowy, możemy przekonwertować tę tablicę na tablicę bitów do liczenia liniowego, zachowując zera i konwertując każdą liczbę dodatnią na jedynkę. W ten sposób otrzymalibyśmy tablicę bitów z poprzedniej tablicy:

[1, 1, 1, 0, 1, 1, 1, 0]

Teraz możemy zastosować algorytm zliczania liniowego i oszacować jego kardynalność.

Jest jednak jeden haczyk. Przechowujemy maksymalny sufiks zerowy w tablicy, ale co, jeśli wszystkie skróty w jakimś zestawie wartości kończą się na jeden? Na przykład, jeśli użyjemy ostatnich trzech bitów jako identyfikatora grupy, do której należy hash, wówczas długość zerowego sufiksu tego hasha "01001100" wyniesie zero - ponieważ wektor "01001" kończy się na jeden. W ten sposób zapisalibyśmy zero w tablicy maksimów w indeksie 4 _(1002=410). Jednak w algorytmie liczenia liniowego pokazałoby to, że nie znaleźliśmy wartości, która miałaby czwórkę po hashu, co nie jest prawdą.

Dlatego modyfikujemy algorytm tak, aby nie przechowywał długości najdłuższego sufiksu zera w polu max, ale przechowywał indeks "pierwszego od prawej" (dla jasności - indeksujemy od jednego), co jest równoznaczne z dodaniem jednego do długości sufiksu zera. Oznacza to, że zero w indeksie i oznacza, że żadna wartość nie ma hasha równego i, a następnie możemy użyć takiej tablicy do liczenia liniowego.

Implementacja HyperLogLog

Jeden krok na raz:

def alpha(num_buckets): return (0.7213 / (1 + 1.079 / num_buckets))

Funkcja alpha zwraca poprawkę dla obliczonego oszacowania, wiemy to już od ostatniego razu, tylko w opcji HyperLogLog alpha ma inną wartość w zależności od liczby grup.

def trailing_zeroes(number): if number == 0: return 0 zeroes = 0 while (number & 1) == 0: zeroes += 1 number = number >> 1 return zeroes

Funkcja zwracająca liczbę zerowych bitów na końcu liczby.

def count_maxims(values, k): num_buckets = 2 ** k max_zeroes = [0] * num_buckets for value in values:
        h = hash(value) bucket_index = h & (num_buckets - 1) bucket_hash = h >> k num_zeros = trailing_zeroes(bucket_hash) + 1 max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros) return max_zeroes

Funkcja, która przechodzi przez wszystkie wartości, dzieli je na grupy num_buckets i oblicza indeks pierwszego od prawej (długość maksymalnego sufiksu zera plus jeden) dla każdej grupy.

def linear_counting(number_of_ones, num_buckets): number_of_zeros = num_buckets - number_of_ones Z = float(number_of_zeros) / num_buckets p = (-num_buckets) * log(Z) return p

Nieco zmodyfikowana funkcja do obliczania algorytmu zliczania liniowego.

def estimate_cardinality(values, k): num_buckets = 2 ** k max_zeroes = count_maxims(values, k) estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes) number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes) if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets): return linear_counting(number_of_ones, num_buckets) else: return estimate

Główna funkcja, która łączy to wszystko razem. Najpierw oblicza oszacowanie przy użyciu zmodyfikowanego LogLog, używa średniej harmonicznej zamiast średniej arytmetycznej w czwartym wierszu, a na koniec stosuje korektę w postaci liczenia liniowego, jeśli obliczone oszacowanie jest mniejsze niż 2,5-krotność liczby grup (w tym momencie spodziewamy się, że standardowe oszacowanie LogLog będzie gorsze niż gdyby zastosowano liczenie liniowe) i jeśli w polu maksimów znajduje się co najmniej jedno zero (nie możemy użyć pola zawierającego wszystkie jedynki w liczeniu liniowym, patrz poprzedni artykuł). A jakie są wyniki HyperLogLog?

Uruchamiamy kod testowy, który szacuje kardynalność zbiorów o kardynalności kolejno 10, 100, ..., 1 000 000:

for x in range(1, 7): num_values = 10**x values = (str(uuid4()) for _ in xrange(num_values)) cardinality = estimate_cardinality(values, 14) print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Wyniki:

Kardynalność: 10.0030530001, błąd względny: 0.999694793165 Kardynalność: 100.306423257, błąd względny: 0.996945128268 Kardynalność: 1003.0892434, błąd względny: 0.99692027063 Kardynalność: 10013.1348931, błąd względny: 0.998688233677 Kardynalność: 100520.045562, błąd względny: 0.994826449206 Kardynalność: 998088.420332, błąd względny: 1.0019152408

Widzimy, że wyniki zawsze różnią się o mniej niż jeden procent od prawidłowego wyniku. I to jest dobre!

Inne ulepszenia HyperLogLog

HyperLogLog doczekał się kilku innych interesujących ulepszeń. Jednym z pozostałych problemów jest wysokie zapotrzebowanie na pamięć. Brzmi to dość dziwnie, ponieważ ostatnim razem wychwalaliśmy zużycie pamięci pod niebiosa i obliczyliśmy, że potrzebujemy tylko 768 bajtów do przechowywania tablicy maksimów. Problem pojawia się tylko wtedy, gdy chcemy obliczyć kardynalność nie jednego ogromnego multizbioru, ale kilku milionów małych multizbiorów równolegle, lub jeśli chcemy przechowywać te obliczone tablice maksimów w bazie danych dla późniejszej machiny szachowej.

Na przykład, gdybyśmy chcieli obliczyć kardynalność miliarda multizbiorów w tym samym czasie, potrzebowalibyśmy 1 000 000 razy 768 bajtów, czyli 768 GB w obecnej implementacji. Z jednej strony nie jest to złe... ale z drugiej strony, jesteśmy w stanie lepiej zaimplementować HyperLogLog.

Rzadka reprezentacja

Wyobraźmy sobie, że ustawiamy k=12, tj. używamy 12 bitów do identyfikacji grup, a tym samym otrzymujemy²¹² różnych grup hashy. Na początku algorytmu musimy przydzielić tablicę o długości 4096 (patrz linia 3 funkcji count_maxims). Załóżmy, że nasz multiset ma trzy różne elementy. Oznacza to, że ustawiamy wartość w trzech różnych miejscach w tablicy, a pozostałe 4093 wartości w tablicy pozostają zerowe; po prostu nie wykorzystaliśmy pozostałych 4093 w żaden sposób. Nie jest to zbyt wydajne, prawda?

Aby uniknąć posiadania tablicy, która jest w większości pusta i nieużywana, ale nadal zajmuje cenny kawałek pamięci, możemy przechowywać wartości jako pary [indeks, wartość] na początku. Przykład dla lepszego zrozumienia. Tablica

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

może być reprezentowany znacznie bardziej efektywnie pamięciowo jako dwie pary:

[0, 7], [4, 12]

Zamiast alokować w pamięci mnóstwo niewykorzystanego miejsca, możemy przyrostowo alokować tylko przestrzeń, której naprawdę potrzebujemy. Taką reprezentację nazywamy rzadką. Jednak w pewnym momencie taka reprezentacja będzie wymagała więcej pamięci niż po prostu przechowywanie jej w tablicy - wtedy możemy przenieść rzadką reprezentację do klasycznej tablicy bez utraty informacji.

Przesunięcia

Praktyka pokazuje, że wszystkie wartości w tablicy są mniej więcej takie same. Tablica maksimów zwykle wygląda na przykład tak:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ..., 13, 14, 11]

Wszystkie wartości są gdzieś w okolicach liczby 13. Inną strategią zmniejszenia rozmiaru takiej tablicy jest odjęcie pewnej stałej wartości od każdego elementu i zapamiętanie tej wartości. Na przykład, możemy odjąć 8:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

W tym momencie każda wartość w tablicy zużywa mniej pamięci - w pierwszej tablicy musimy przechowywać liczby od 0 do 15, na co potrzebujemy 4 bitów, podczas gdy w drugiej tablicy potrzebujemy tylko 3 bitów, ponieważ przechowujemy liczby od 0 do 7. Oczywiście zakłada to implementację tablicy na poziomie bitowym. W momencie, gdy chcemy odczytać wartości z tablicy, musimy z powrotem dodać do nich odnotowaną wartość.

wiele innych ulepszeń. Badania w tym obszarze wciąż trwają, więc z pewnością możemy spodziewać się kolejnych ciekawych pomysłów. Następnym razem porozmawiamy o ujednolicaniu i przecinaniu wektorów HyperLogLog, a w niedalekiej przyszłości omówimy, dlaczego przechowywanie miliardów wektorów HyperLogLog może być przydatne.

Linki i zasoby

• Całą moją implementację można zobaczyć na GitHub.
• HyperLogLog: analiza niemal optymalnego algorytmu szacowania kardynalności [PDF] - oryginalny artykuł wprowadzający HyperLogLog.
• HyperLogLogin Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [ PDF] - ulepszona wersja oryginalnego HyperLogLog, na przykład poprzez dodanie wspomnianej wcześniej rzadkiej reprezentacji.