✖

HyperLogLog: jak bardzo dokładnie oszacować liczbę unikalnych wartości

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

Seria o algorytmach do szacowania liczby unikalnych wartości w multizbiorze toczy się dalej artykułem o algorytmie HyperLogLog, który jest state of the art. Wszystkie idee stojące za tym algorytmem wywodzą się jednak z opisanego wcześniej LogLogu, więc jeśli chcesz czytać dalej, upewnij się, że dobrze znasz LogLog.

Algorytm LogLog miał dwa główne problemy:

Wartości odstające

Końcowe oszacowanie LogLogu jest bardzo wrażliwe na wartości odstające (outliery), czyli wartości, które są bardzo odległe od pozostałych wartości. Typowo zdarza się bowiem, że większość maksymalnych długości zerowych sufiksów dla każdej grupy jest mniej więcej taka sama, na przykład mieści się między 12 a 15, ale potem bum — i jeden zerowy sufiks ma długość 27. Ta duża różnica robi bałagan w końcowym oszacowaniu liczby unikalnych wartości, bo klasyczna średnia arytmetyczna nie radzi sobie z tym zbyt dobrze. W zasadzie działa tu ta sama zasada, co kiedy kilku topowych menedżerów i dyrektorów swoimi wysokimi pensjami podnosi przeciętne wynagrodzenie w całym kraju.

Autorzy algorytmu próbowali to rozwiązać tak, że pozbywali się wartości odstających i nie wliczali do średniej kilku najwyższych maksimów, ale nie było to zbyt dobre rozwiązanie. Później spróbowali innego podejścia — zamiast średniej arytmetycznej użyli średniej harmonicznej, która ma znacznie lepsze własności w przypadku, gdy mamy wartości odległe od średniej.

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

LogLog ma okropne wyniki, kiedy ma szacować liczność małych multizbiorów. Jeśli w multizbiorze mamy tylko kilka unikalnych elementów, LogLog zwróci nam absurdalnie duże oszacowanie. Autorzy rozwiązali to sprytnie — w przypadku, gdy na wejściu mamy multizbiór o niskiej liczności, nie używa się algorytmu LogLog, ale zupełnie innego algorytmu, a mianowicie starego dobrego Linear Counting. No tak, ale jak poznamy, że na wejściu mamy multizbiór o małej liczności, skoro liczności właśnie nie znamy?

Pozwolimy LogLogowi oszacować liczbę unikalnych elementów i kiedy stwierdzimy, że to oszacowanie jest względnie niskie, wyrzucimy je i obliczymy je ponownie algorytmem Linear Counting. Szybko przypomnijmy sobie, jak działa Linear Counting. Na początku alokujemy zerową (bitową) tablicę o jakimś z góry ustalonym rozmiarze, typowo potędze dwójki. Przechodzimy przez wszystkie elementy multizbioru, obliczamy ich hasz i zamieniamy go na liczbę całkowitą i z zakresu od 0 do długości tablicy minus 1. Na indeksie i zapisujemy w tablicy jedynkę. Na koniec policzymy liczbę zer i jedynek w tablicy i za pomocą prostego wzoru oszacujemy liczność.

Algorytm LogLog nie używa jednak żadnej tablicy bitowej, do której by „zapisywał” obliczone hasze. Zamiast tego używa tablicy, w której przechowuje maksymalne długości sufiksów. Tablica może wyglądać na przykład tak:

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

przy czym każda liczba oznacza maksymalną długość zerowego sufiksu w danej grupie obliczonych haszy. Niezerowa wartość na i-tej pozycji oznacza jednak koniecznie, że wśród wartości w multizbiorze istnieje element, którego (trzybitowy) hasz jest równy i. Innymi słowy, tę tablicę możemy zamienić na tablicę bitową dla Linear Counting tak, że zera zostawimy, a każdą liczbę dodatnią zamienimy na jedynkę. Z poprzedniej tablicy dostalibyśmy więc tablicę bitową:

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

Teraz możemy zastosować algorytm Linear Counting i za jego pomocą oszacować liczność.

Ma to jednak jeden haczyk. Do tablicy zapisujemy maksymalny zerowy sufiks, tylko co jeśli w jakiejś grupie wartości wszystkie hasze kończą się jedynką? Jeśli na przykład użyjemy trzech ostatnich bitów jako identyfikatora grupy, do której hasz należy, to długość zerowego sufiksu haszu „01001100” byłaby równa zero — bo wektor „01001” kończy się jedynką. Do tablicy maksimów zapisalibyśmy więc pod indeksem 4 (1002=410) zero. W algorytmie Linear Counting objawiłoby się to jednak tak, że nie znaleźliśmy wartości, której haszem byłaby czwórka, a to nieprawda.

Dlatego zmienimy algorytm tak, żeby nie zapisywał do tablicy maksimów długości najdłuższego zerowego sufiksu, ale żeby zapisywał indeks „pierwszej jedynki od prawej” (dla porządku — indeksujemy od jedynki), co jest tym samym, jakbyśmy do długości zerowego sufiksu dodali jedynkę. Dzięki temu zero pod indeksem i oznacza, że żadna wartość nie ma haszu równego i, i takiej tablicy możemy potem użyć w Linear Counting.

Implementacja HyperLogLogu

Po kolei:

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

Funkcja alpha zwraca poprawkę dla obliczonego oszacowania, to już znamy z poprzedniej części, tylko w przypadku HyperLogLogu alpha ma różną 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, która zwraca 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 num_buckets grup i dla każdej grupy oblicza indeks pierwszej jedynki od prawej (długość maksymalnego zerowego sufiksu plus jeden).

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

Lekko zmieniona funkcja realizująca algorytm Linear Counting.

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 to wszystko składa w całość. Najpierw oblicza oszacowanie za pomocą zmienionego LogLogu, zamiast średniej arytmetycznej używa w czwartym wierszu średniej harmonicznej, a na koniec stosuje poprawkę w postaci Linear Counting, jeśli obliczone oszacowanie jest mniejsze niż 2,5-krotność liczby grup (w takiej sytuacji spodziewamy się, że standardowe oszacowanie LogLogu będzie gorsze, niż gdyby użyć Linear Counting) i jeśli w tablicy maksimów jest co najmniej jedno zero (tablicy, w której są same jedynki, nie możemy w Linear Counting użyć, zob. poprzedni artykuł). A jakie są wyniki HyperLogLogu?

Uruchomimy kod testowy, który oszacuje nam liczność zbiorów, które mają kolejno liczność 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:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Widzimy, że wyniki zawsze odbiegają od prawidłowego wyniku o mniej niż procent. I to jest dobre!

Dalsze ulepszenia HyperLogLogu

HyperLogLog doczekał się kilku kolejnych ciekawych ulepszeń. Jednym z pozostałych problemów jest duże zużycie pamięci. Brzmi to dość dziwnie, skoro ostatnio wychwalaliśmy zużycie pamięci pod niebiosa i policzyliśmy, że do zapisania tablicy maksimów wystarczy nam 768 bajtów. Tyle że problem pojawia się, jeśli chcesz liczyć liczność nie jednego ogromnego multizbioru, ale równolegle kilku milionów małych multizbiorów, albo jeśli te obliczone tablice maksimów chcesz przechowywać w bazie danych na jakieś późniejsze kombinacje.

Gdybyśmy na przykład liczyli jednocześnie liczność miliarda multizbiorów, potrzebowalibyśmy przy obecnej implementacji 1 000 000 000 razy 768 bajtów, czyli 768 GB. Z jednej strony to nie jest źle… ale z drugiej strony potrafimy zaimplementować HyperLogLog lepiej.

Reprezentacja rzadka (sparse)

Wyobraźmy sobie, że ustawimy k=12, tzn. użyjemy 12 bitów do identyfikacji grup i dostaniemy w związku z tym 212 różnych grup haszy. Na początku algorytmu musimy zaalokować tablicę o długości 4096 (zob. wiersz 3 funkcji count_maxims). I powiedzmy, że nasz multizbiór ma trzy różne elementy. To oznacza, że w tablicy w trzech różnych miejscach ustawimy jakąś wartość, a pozostałe 4093 wartości w tablicy zostaną zerowe, pozostałych 4093 po prostu w żaden sposób nie wykorzystaliśmy. To niezbyt efektywne, prawda?

Żeby uniknąć tego, że będziemy mieć tablicę, która jest w większej części zerowa i niewykorzystana, a mimo to zajmuje cenny kawałek pamięci, możemy na początku zapisywać wartości jako pary [indeks, wartość]. Przykład dla lepszego zrozumienia. Tę tablicę

[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żemy znacznie oszczędniej pamięciowo przedstawić jako dwie pary:

[0, 7], [4, 12]

Zamiast mieć w pamięci zaalokowaną masę niewykorzystanego miejsca, możemy stopniowo alokować tylko to miejsce, którego naprawdę potrzebujemy. Taką reprezentację nazywamy rzadką (ang. sparse). W pewnym momencie taka reprezentacja byłaby jednak bardziej pamięciożerna niż właśnie zapisanie do tablicy — wtedy możemy reprezentację rzadką zamienić na klasyczną tablicę bez utraty informacji.

Przesunięcia (offsety)

Praktyka pokazała, ż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 kręcą się gdzieś wokół liczby 13. Kolejną ze strategii, jak zmniejszyć rozmiar takiej tablicy, jest odjęcie od każdego elementu jakiejś stałej wartości i zapamiętanie jej. Możemy odjąć na przykład ósemkę:

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

W tej chwili każda wartość w tablicy zużywa mniej pamięci — w pierwszej tablicy musimy zapisywać liczby od 0 do 15, do czego potrzebujemy 4 bitów, podczas gdy na drugą tablicę wystarczą nam 3 bity, bo zapisujemy tylko liczby od 0 do 7. Oczywiście zakłada to implementację tablicy na poziomie pojedynczych bitów. W chwili, kiedy będziemy chcieli odczytać wartości z tablicy, musimy do nich z powrotem dodać zapamiętaną wartość.

…i cała masa innych ulepszeń. Badania w tej dziedzinie wciąż trwają, więc na pewno możemy czekać na kolejne ciekawe pomysły. My następnym razem powiemy sobie coś o sumie i części wspólnej wektorów HyperLogLog, a kiedyś w niedalekiej przyszłości powiemy sobie, dlaczego może nam się przydać przechowywanie miliardów wektorów HyperLogLog.

Odnośniki i źródła