De serie over algoritmen om het aantal unieke waarden in een multiverzameling te schatten gaat verder met een artikel over het state of the art-algoritme HyperLogLog. Alle ideeën achter dit algoritme zijn echter gebaseerd op het eerder beschreven LogLog, dus als je verder wilt lezen, zorg dan dat je LogLog goed kent.

Het LogLog-algoritme had twee grote problemen:

Uitschieters

De uiteindelijke schatting van LogLog is erg gevoelig voor uitschieters (outliers), waarden die heel ver van de andere waarden liggen. Meestal gebeurt het namelijk dat de meeste maximale lengtes van suffixen van nullen voor elke groep ongeveer gelijk zijn, bijvoorbeeld tussen 12 en 15, maar dan, boem — één suffix van nullen heeft lengte 27. Dit grote verschil maakt een puinhoop van de uiteindelijke schatting van het aantal unieke waarden, want het gewone rekenkundig gemiddelde kan daar niet zo goed mee omgaan. In feite werkte hetzelfde principe als wanneer een paar topmanagers en directeuren met hun hoge salarissen het gemiddelde salaris in een land omhoogtrekken.

De auteurs van het algoritme probeerden dat op te lossen door zich van de uitschieters te ontdoen en de hoogste maxima niet in het gemiddelde mee te nemen, maar dat was geen erg goede oplossing. Later probeerden ze een andere aanpak — in plaats van het rekenkundig gemiddelde gebruikten ze het harmonisch gemiddelde, dat veel betere eigenschappen heeft als we waarden hebben die ver van het gemiddelde af liggen.

Zeer slechte resultaten voor kleine kardinaliteiten

LogLog geeft vreselijke resultaten als het de kardinaliteit van kleine multiverzamelingen moet schatten. Als we in de multiverzameling maar een paar unieke elementen hebben, geeft LogLog ons een onzinnig grote schatting. De auteurs hebben dat slim opgelost — als de invoer een multiverzameling met een lage kardinaliteit is, wordt niet het LogLog-algoritme gebruikt, maar een heel ander algoritme, namelijk het oude bekende linear counting. Ja, maar hoe merken we dat de invoer een multiverzameling met een kleine kardinaliteit is, als we de kardinaliteit nu juist niet kennen?

We laten LogLog het aantal unieke elementen schatten en als we merken dat deze schatting relatief laag is, gooien we de schatting weg en berekenen we haar opnieuw met het algoritme linear counting. We herhalen kort hoe linear counting werkt. Aan het begin maken we een (bit)array vol nullen van een vooraf bepaalde grootte, meestal een macht van twee. We lopen alle elementen van de multiverzameling door, berekenen hun hash en zetten die om in een geheel getal i uit het bereik van 0 tot de lengte van de array min 1. Op index i slaan we dan in de array een één op. Ten slotte tellen we het aantal nullen en enen in de array en schatten we met een eenvoudige formule de kardinaliteit.

Het LogLog-algoritme gebruikt echter geen bitarray waarin het de berekende hashes “opslaat”. In plaats daarvan gebruikt het een array waarin het de maximale lengtes van suffixen bewaart. De array kan er bijvoorbeeld zo uitzien:

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

waarbij elk getal de maximale lengte van het suffix van nullen in de betreffende groep van berekende hashes aangeeft. Een waarde ongelijk aan nul op de i-de positie betekent dan echter noodzakelijkerwijs dat er onder de waarden in de multiverzameling een element bestaat waarvan de (driebits) hash gelijk is aan i. Met andere woorden: we kunnen deze array omzetten in een bitarray voor linear counting door de nullen te laten staan en elk positief getal om te zetten in een één. Uit de vorige array zouden we zo de bitarray krijgen:

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

Nu kunnen we het algoritme linear counting toepassen en daarmee de kardinaliteit schatten.

Er zit echter een addertje onder het gras. We slaan in de array het maximale suffix van nullen op, maar wat als in een bepaalde groep alle hashes op een één eindigen? Als we bijvoorbeeld de laatste drie bits gebruiken als identificatie van de groep waartoe de hash behoort, dan zou de lengte van het suffix van nullen van deze hash “01001100” nul zijn — omdat de vector “01001” op een één eindigt. In de array met maxima zouden we dan op index 4 (100₂=4₁₀) een nul opslaan. In het algoritme linear counting zou dat er echter toe leiden dat we geen waarde hebben gevonden die als hash vier heeft, en dat is niet waar.

Daarom passen we het algoritme zo aan dat het in de array met maxima niet de lengte van het langste suffix van nullen opslaat, maar de index van de “eerste één van rechts” (voor de duidelijkheid — we indexeren vanaf één), en dat is hetzelfde als bij de lengte van het suffix van nullen één op te tellen. Daarmee bereiken we dat een nul op index i betekent dat geen enkele waarde hash i heeft, en zo'n array kunnen we dan gebruiken voor linear counting.

Implementatie van HyperLogLog

Netjes stap voor stap:

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

De functie alpha geeft de correctie voor de berekende schatting terug, dat kennen we al van de vorige keer, alleen heeft alpha bij HyperLogLog een andere waarde, afhankelijk van het aantal groepen.

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

Een functie die het aantal nulbits aan het einde van een getal teruggeeft.

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

Een functie die alle waarden doorloopt, ze in num_buckets groepen verdeelt en voor elke groep de index van de eerste één van rechts berekent (de lengte van het maximale suffix van nullen plus één).

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

Een licht aangepaste functie voor de berekening van het algoritme 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

De hoofdfunctie die alles samenbrengt. Eerst berekent ze de schatting met de aangepaste LogLog, in plaats van het rekenkundig gemiddelde gebruikt ze op de vierde regel het harmonisch gemiddelde, en ten slotte past ze de correctie in de vorm van linear counting toe als de berekende schatting kleiner is dan 2,5 keer het aantal groepen (op dat moment verwachten we dat de standaardschatting van LogLog slechter zal zijn dan wanneer we linear counting zouden gebruiken) en als er in de array met maxima minstens één nul zit (een array waarin alleen enen staan, kunnen we in linear counting niet gebruiken, zie het vorige artikel). En wat zijn de resultaten van HyperLogLog?

We voeren testcode uit die de kardinaliteit schat van verzamelingen met achtereenvolgens kardinaliteit 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)

Resultaten:

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

We zien dat de resultaten steeds minder dan een procent van het juiste resultaat afwijken. En dat is goed!

Verdere verbeteringen van HyperLogLog

HyperLogLog heeft nog een aantal andere interessante verbeteringen gekregen. Een van de resterende problemen is het hoge geheugengebruik. Dat klinkt nogal vreemd, want de vorige keer hebben we het geheugengebruik de hemel in geprezen en hebben we uitgerekend dat 768 bytes volstaan om de array met maxima op te slaan. Het probleem ontstaat echter als je de kardinaliteit niet van één enorme multiverzameling wilt berekenen, maar parallel van een paar miljoen kleine multiverzamelingen, of als je deze berekende arrays met maxima in een database wilt bewaren voor latere toverkunsten.

Als we bijvoorbeeld tegelijk de kardinaliteit van één miljard multiverzamelingen zouden berekenen, hadden we bij de huidige implementatie 1 000 000 000 keer 768 bytes nodig, dat is 768 GB. Aan de ene kant is dat niet slecht … maar aan de andere kant kunnen we HyperLogLog beter implementeren.

Sparse representatie

Stel dat we k=12 instellen, dus 12 bits gebruiken voor het identificeren van groepen en daarmee 2¹² verschillende groepen hashes krijgen. Aan het begin van het algoritme moeten we een array van lengte 4096 alloceren (zie regel 3 van de functie count_maxims). En stel dat onze multiverzameling drie verschillende elementen heeft. Dat betekent dat we op drie verschillende plaatsen in de array een waarde zetten en dat de overige 4093 waarden in de array nul blijven, die overige 4093 hebben we gewoon helemaal niet gebruikt. Dat is niet erg efficiënt, toch?

Om te voorkomen dat we een array hebben die grotendeels nul en ongebruikt is, maar toch een kostbaar stuk geheugen inneemt, kunnen we de waarden aan het begin opslaan als paren [index, waarde]. Een voorbeeld voor beter begrip. Deze array

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

kunnen we veel geheugenefficiënter weergeven als twee paren:

[0, 7], [4, 12]

In plaats van een hoop ongebruikte ruimte in het geheugen te alloceren, kunnen we stap voor stap alleen de ruimte alloceren die we echt nodig hebben. Deze representatie noemen we ijl (sparse). Op een zeker moment zou deze representatie echter meer geheugen kosten dan opslag in een array — dan kunnen we de sparse representatie zonder verlies van informatie omzetten in een gewone array.

Offsets

In de praktijk blijkt dat alle waarden in de array ongeveer gelijk zijn. De array met maxima ziet er gewoonlijk bijvoorbeeld zo uit:

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

Alle waarden liggen ergens rond het getal 13. Een andere strategie om de grootte van zo'n array te verkleinen, is van elk element een vaste waarde af te trekken en die te onthouden. We kunnen bijvoorbeeld acht aftrekken:

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

Op dit moment neemt elke waarde in de array minder geheugen in — in de eerste array moeten we getallen van 0 tot 15 opslaan, daarvoor hebben we 4 bits nodig, terwijl we voor de tweede array genoeg hebben aan 3 bits, want we slaan alleen getallen van 0 tot 7 op. Dat veronderstelt natuurlijk een implementatie van de array op het niveau van afzonderlijke bits. Als we de waarden uit de array willen lezen, moeten we er de genoteerde waarde weer bij optellen.

…en een hoop andere verbeteringen. Het onderzoek op dit gebied loopt nog steeds, dus we kunnen ons vast verheugen op nog meer interessante ideeën. De volgende keer vertellen we iets over de vereniging en de doorsnede van HyperLogLog-vectoren en ergens in de nabije toekomst vertellen we waarom het van pas kan komen om miljarden HyperLogLog-vectoren op te slaan.

Verwijzingen en bronnen

• Mijn hele implementatie kun je bekijken op GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — het oorspronkelijke artikel waarin HyperLogLog werd geïntroduceerd.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — een verbeterde versie van het oorspronkelijke HyperLogLog, bijvoorbeeld met de genoemde sparse representatie.