Seria despre algoritmii de estimare a numărului de valori unice dintr-o multimulțime continuă cu un articol despre algoritmul state of the art HyperLogLog. Totuși, toate ideile din spatele acestui algoritm pornesc de la LogLog, descris mai devreme, așa că, dacă vrei să citești mai departe, asigură-te că știi bine LogLog.

Algoritmul LogLog avea două probleme principale:

Valorile aberante (outlieri)

Estimarea finală a LogLog-ului este foarte sensibilă la valorile aberante (outlieri), adică valori care sunt foarte departe de celelalte valori. De obicei se întâmplă ca majoritatea lungimilor maxime ale sufixelor nule pentru fiecare grup să fie aproximativ aceleași, de exemplu între 12 și 15, dar apoi bum – și un sufix nul are lungimea 27. Această diferență mare strică estimarea finală a numărului de valori unice, pentru că media aritmetică clasică nu se descurcă prea bine cu așa ceva. În fond a funcționat același principiu ca atunci când câțiva top manageri și directori ridică salariul mediu din țară cu salariile lor mari.

Autorii algoritmului au încercat să rezolve asta scăpând de valorile aberante și nepunând în medie câteva dintre cele mai mari maxime, dar nu a fost o soluție prea bună. Mai târziu au încercat un alt procedeu – în loc de media aritmetică au folosit media armonică, care are proprietăți mult mai bune atunci când avem valori îndepărtate de medie.

Rezultate foarte proaste pentru cardinalități mici

LogLog are rezultate îngrozitoare atunci când trebuie să estimeze cardinalitatea unor multimulțimi mici. Dacă într-o multimulțime avem câteva elemente unice, LogLog ne returnează o estimare absurd de mare. Autorii au rezolvat asta ingenios – în cazul în care avem la intrare o multimulțime cu cardinalitate mică, nu se folosește algoritmul LogLog, ci un cu totul alt algoritm, anume vechiul și bine-cunoscutul Linear Counting. Numai că, cum ne dăm seama că avem la intrare o multimulțime cu cardinalitate mică, dacă tocmai nu știm cardinalitatea?

Lăsăm LogLog-ul să estimeze numărul de elemente unice și, dacă constatăm că această estimare este relativ mică, o aruncăm și o calculăm din nou cu algoritmul Linear Counting. Să ne reamintim pe scurt cum funcționează Linear Counting. La început alocăm un vector de biți nul, de o dimensiune dată dinainte, de obicei o putere a lui doi. Parcurgem toate elementele multimulțimii, calculăm hash-ul lor și îl convertim într-un număr întreg i din intervalul 0 până la lungimea vectorului minus 1. Apoi, în vector la indexul i stocăm un unu. La final numărăm zerourile și unu din vector și, cu ajutorul formulei simple, estimăm cardinalitatea.

Algoritmul LogLog nu folosește însă niciun vector de biți în care să „stocheze” hash-urile calculate. În schimb folosește un tablou în care păstrează lungimile maxime ale sufixelor. Tabloul poate arăta, de exemplu, așa:

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

unde fiecare număr indică lungimea maximă a sufixului nul din grupul respectiv de hash-uri calculate. O valoare nenulă pe poziția i înseamnă însă obligatoriu că între valorile din multimulțime există un element al cărui hash (de trei biți) este egal cu i. Cu alte cuvinte, putem converti acest tablou într-un vector de biți pentru Linear Counting păstrând zerourile și transformând orice număr pozitiv în unu. Din tabloul anterior am obține astfel vectorul de biți:

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

Acum putem aplica algoritmul Linear Counting și estima cardinalitatea cu ajutorul lui.

Are însă o problemă. Noi stocăm în tablou sufixul nul maxim, dar ce se întâmplă dacă într-un grup toate hash-urile se termină cu unu? Dacă, de exemplu, folosim ultimii trei biți ca identificator al grupului din care face parte hash-ul, atunci lungimea sufixului nul al acestui hash „01001100” ar fi zero – pentru că vectorul „01001” se termină cu unu. În tabloul de maxime am stoca astfel zero la indexul 4 (100₂=4₁₀). În algoritmul Linear Counting acest lucru s-ar manifesta ca și cum nu am fi găsit nicio valoare care să aibă hash-ul patru, ceea ce nu este adevărat.

De aceea modificăm algoritmul astfel încât să nu stocheze în tabloul de maxime lungimea celui mai lung sufix nul, ci indexul „primului unu de la dreapta” (pentru ordine – indexăm de la unu), ceea ce este același lucru cu a adăuga unu la lungimea sufixului nul. Astfel obținem că un zero la indexul i înseamnă că nicio valoare nu are hash-ul egal cu i, iar un astfel de tablou poate fi folosit apoi pentru Linear Counting.

Implementarea HyperLogLog

Frumos, pe rând:

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

Funcția alpha returnează corecția pentru estimarea calculată, asta o știm de data trecută, doar că în cazul HyperLogLog alpha are o altă valoare, în funcție de numărul de grupuri.

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

O funcție care returnează numărul de biți nuli de la sfârșitul numărului.

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

O funcție care parcurge toate valorile, le împarte în num_buckets grupuri și pentru fiecare grup calculează indexul primului unu de la dreapta (lungimea sufixului nul maxim plus unu).

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

O funcție ușor modificată pentru calculul algoritmului 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

Funcția principală, care le leagă pe toate. Mai întâi calculează estimarea cu ajutorul LogLog-ului modificat, în locul mediei aritmetice folosește pe rândul al patrulea media armonică și, în final, aplică corecția sub forma Linear Counting, dacă estimarea calculată este mai mică decât de 2,5 ori numărul de grupuri (în acest caz ne așteptăm ca estimarea standard a LogLog-ului să fie mai slabă decât dacă s-ar folosi Linear Counting) și dacă în tabloul de maxime există cel puțin un zero (un tablou în care sunt numai unu nu îl putem folosi în Linear Counting, vezi articolul precedent). Și care sunt rezultatele HyperLogLog-ului?

Rulăm un cod de test care ne estimează cardinalitatea unor mulțimi cu cardinalitatea, pe rând, 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)

Rezultate:

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

Vedem că rezultatele se abat întotdeauna de la rezultatul corect cu mai puțin de un procent. Și asta e bine!

Alte îmbunătățiri ale HyperLogLog

HyperLogLog a primit câteva alte îmbunătățiri interesante. Una dintre problemele rămase este consumul mare de memorie. Sună destul de ciudat, după ce data trecută am lăudat consumul de memorie până la cer și am calculat că pentru stocarea tabloului de maxime ne ajung 768 de octeți. Problema apare însă dacă vrei să calculezi cardinalitatea nu pentru o singură multimulțime uriașă, ci în paralel pentru câteva milioane de multimulțimi mici, sau dacă vrei să păstrezi aceste tablouri de maxime calculate într-o bază de date pentru niște manevre ulterioare.

Dacă am calcula, de exemplu, simultan cardinalitatea unei miliarde de multimulțimi, ar trebui, cu implementarea actuală, 1.000.000.000 de ori 768 de octeți, adică 768 GB. Pe de o parte nu e rău… dar pe de altă parte putem implementa HyperLogLog mai bine.

Reprezentarea sparse

Să ne imaginăm că setăm k=12, adică folosim 12 biți pentru identificarea grupurilor și obținem deci 2¹² grupuri diferite de hash-uri. La începutul algoritmului trebuie să alocăm un tablou de lungime 4096 (vezi rândul 3 al funcției count_maxims). Și să zicem că multimulțimea noastră are trei elemente diferite. Asta înseamnă că în tablou setăm o valoare în trei locuri diferite, iar celelalte 4093 de valori din tablou rămân nule, cele 4093 pur și simplu nu le-am folosit deloc. Nu e prea eficient, nu-i așa?

Ca să evităm să avem un tablou care este în cea mai mare parte nul și nefolosit, dar care ocupă totuși o bucată prețioasă de memorie, putem stoca la început valorile ca perechi [index, valoare]. Un exemplu pentru o înțelegere mai bună. Acest tablou

[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]

îl putem reprezenta mult mai eficient din punct de vedere al memoriei ca două perechi:

[0, 7], [4, 12]

În loc să avem alocată în memorie o grămadă de spațiu nefolosit, putem aloca treptat doar spațiul de care avem cu adevărat nevoie. Această reprezentare o numim sparse. Totuși, la un moment dat această reprezentare ar deveni mai costisitoare ca memorie decât stocarea într-un tablou – atunci putem converti reprezentarea sparse într-un tablou clasic, fără pierdere de informație.

Offseturi

Practica a arătat că toate valorile din tablou sunt aproximativ egale. Tabloul de maxime arată de obicei, de exemplu, așa:

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

Toate valorile se află pe undeva în jurul numărului 13. O altă strategie pentru a micșora dimensiunea unui astfel de tablou este să scădem din fiecare element o valoare fixă și să o memorăm. Putem scădea, de exemplu, opt:

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

Acum fiecare valoare din tablou consumă mai puțină memorie – în primul tablou trebuie să stocăm numere de la 0 la 15, pentru care avem nevoie de 4 biți, în timp ce pentru al doilea tablou ne ajung 3 biți, pentru că stocăm doar numere de la 0 la 7. Desigur, asta presupune o implementare a tabloului la nivelul biților individuali. Când vrem să citim valorile din tablou, trebuie să adăugăm înapoi valoarea memorată.

…și o grămadă de alte îmbunătățiri. Cercetarea în acest domeniu este încă în desfășurare, așa că ne putem aștepta cu siguranță la alte idei interesante. Data viitoare vom vorbi despre reuniunea și intersecția vectorilor HyperLogLog, iar cândva în viitorul apropiat vom vedea de ce ne poate fi util să stocăm miliarde de vectori HyperLogLog.

Trimiteri și surse

• Întreaga mea implementare o poți vedea pe GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – articolul original în care a fost prezentat HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – versiunea îmbunătățită a HyperLogLog-ului original, de exemplu cu reprezentarea sparse menționată.