Serien om algoritmer til at estimere antallet af unikke værdier i en multimængde fortsætter med en artikel om state of the art-algoritmen HyperLogLog. Alle de idéer, der ligger bag denne algoritme, bygger dog på det tidligere beskrevne LogLog, så hvis du vil læse videre, så sørg for, at du kender LogLog godt.

LogLog-algoritmen havde to hovedproblemer:

Outliers

Det endelige estimat fra LogLog er meget følsomt over for outliers, værdier, der ligger meget langt fra de øvrige værdier. Typisk sker det nemlig, at de fleste maksimale længder af nulsuffikser for de enkelte grupper er nogenlunde ens, fx ligger de mellem 12 og 15, men så bum — og et nulsuffiks har længden 27. Denne store forskel laver rod i det endelige estimat af antallet af unikke værdier, fordi det klassiske aritmetiske gennemsnit ikke kan klare det særlig godt. Det er i bund og grund det samme princip, som når nogle få topchefer og direktører løfter gennemsnitslønnen i landet med deres høje lønninger.

Algoritmens forfattere forsøgte at løse det ved at skille sig af med outliers og ikke medregne nogle få af de højeste maksima i gennemsnittet, men det var ikke en særlig god løsning. Senere prøvede de en anden fremgangsmåde — i stedet for det aritmetiske gennemsnit brugte de det harmoniske gennemsnit, som har langt bedre egenskaber, når vi har værdier, der ligger langt fra gennemsnittet.

Meget dårlige resultater for små kardinaliteter

LogLog har rædselsfulde resultater, når den skal estimere kardinaliteten af små multimængder. Hvis vi har nogle få unikke elementer i multimængden, returnerer LogLog et meningsløst stort estimat. Forfatterne løste det snedigt — når vi har en multimængde med lav kardinalitet som input, bruges LogLog-algoritmen ikke, men en helt anden algoritme, nemlig den gamle bekendte Linear counting. Ja, men hvordan opdager vi, at vi har en multimængde med lille kardinalitet som input, når vi netop ikke kender kardinaliteten?

Vi lader LogLog estimere antallet af unikke elementer, og når vi finder ud af, at dette estimat er relativt lavt, kasserer vi estimatet og beregner det igen med algoritmen Linear counting. Vi minder kort om, hvordan Linear counting virker. I begyndelsen allokerer vi et (bit)array af nuller med en på forhånd given størrelse, typisk en toerpotens. Vi gennemgår alle elementer i multimængden, beregner deres hash og omdanner den til et heltal i fra intervallet 0 til arrayets længde minus 1. På indeks i gemmer vi så et ettal i arrayet. Til sidst tæller vi antallet af nuller og ettaller i arrayet og estimerer kardinaliteten ved hjælp af en enkel formel.

LogLog-algoritmen bruger dog intet bitfelt, hvor den ville »gemme« de beregnede hashes. I stedet bruger den et array, hvor den gemmer de maksimale længder af suffikser. Arrayet kan fx se sådan her ud:

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

hvor hvert tal angiver den maksimale længde af nulsuffikset i den pågældende gruppe af beregnede hashes. En værdi forskellig fra nul på den i-te plads betyder dog nødvendigvis, at der blandt værdierne i multimængden findes et element, hvis (tre-bit) hash er lig med i. Med andre ord kan vi omdanne dette array til et bitfelt til linear counting ved at lade nullerne stå og omdanne ethvert positivt tal til et ettal. Af det foregående array ville vi således få bitfeltet:

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

Nu kan vi anvende algoritmen Linear counting og estimere kardinaliteten med den.

Der er dog en hage. Vi gemmer det maksimale nulsuffiks i arrayet, men hvad nu, hvis alle hashes i en gruppe af værdier ender på et ettal? Hvis vi fx bruger de sidste tre bit som identifikator for den gruppe, som hashen hører til, ville længden af nulsuffikset i denne hash »01001100« være nul — fordi vektoren »01001« ender på et ettal. I arrayet med maksima ville vi altså på indeks 4 (100₂=4₁₀) gemme et nul. I algoritmen linear counting ville det slå igennem på den måde, at vi ikke fandt en værdi, der havde fire som hash, hvilket ikke er sandt.

Derfor ændrer vi algoritmen, så den ikke gemmer længden af det længste nulsuffiks i arrayet med maksima, men gemmer indekset for »det første ettal fra højre« (for en ordens skyld — vi indekserer fra et), hvilket er det samme, som hvis vi lagde et til længden af nulsuffikset. Dermed opnår vi, at et nul på indeks i betyder, at ingen værdi har hashen i, og sådan et array kan vi så bruge til linear counting.

Implementering af HyperLogLog

Pænt trin for trin:

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

Funktionen alpha returnerer korrektionen for det beregnede estimat, det kender vi fra sidste gang, bare at alpha i tilfældet HyperLogLog har en anden værdi afhængigt af antallet af grupper.

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

Funktionen, der returnerer antallet af nul-bit i slutningen af et tal.

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

Funktionen, der gennemgår alle værdier, deler dem i num_buckets grupper og for hver gruppe beregner indekset for det første ettal fra højre (længden af det maksimale nulsuffiks plus et).

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

Let ændret funktion til beregning af algoritmen 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

Hovedfunktionen, der samler det hele. Først beregner den estimatet med den ændrede LogLog, i stedet for det aritmetiske gennemsnit bruger den på den fjerde linje det harmoniske gennemsnit, og til sidst anvender den korrektionen i form af Linear counting, hvis det beregnede estimat er mindre end 2,5 gange antallet af grupper (her forventer vi, at LogLogs standardestimat vil være dårligere, end hvis man brugte Linear counting), og hvis der i arrayet med maksima er mindst ét nul (et array, hvor der kun er ettaller, kan vi ikke bruge i Linear counting, se den foregående artikel). Og hvad er resultaterne af HyperLogLog?

Vi kører testkode, der estimerer kardinaliteten af mængder, som efter tur har kardinaliteten 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)

Resultater:

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

Vi ser, at resultaterne altid afviger fra det rigtige resultat med mindre end en procent. Og det er godt!

Yderligere forbedringer af HyperLogLog

HyperLogLog har fået flere andre interessante forbedringer. Et af de resterende problemer er højt hukommelsesforbrug. Det lyder ret mærkeligt, når vi sidste gang roste hukommelsesforbruget til skyerne og regnede ud, at 768 byte rækker til at gemme arrayet med maksima. Men problemet opstår, hvis du vil beregne kardinaliteten ikke af én gigantisk multimængde, men parallelt af flere millioner små multimængder, eller hvis du vil gemme de beregnede arrays med maksima i en database til senere brug.

Hvis vi fx samtidig beregnede kardinaliteten af en milliard multimængder, ville vi med den nuværende implementering skulle bruge 1.000.000.000 gange 768 byte, hvilket er 768 GB. På den ene side er det ikke dårligt … men på den anden side kan vi implementere HyperLogLog bedre.

Sparse repræsentation

Lad os forestille os, at vi sætter k=12, dvs. bruger 12 bit til at identificere grupper og dermed får 2¹² forskellige grupper af hashes. I begyndelsen af algoritmen skal vi allokere et array af længden 4096 (se linje 3 i funktionen count_maxims). Og lad os sige, at vores multimængde har tre forskellige elementer. Det betyder, at vi i arrayet sætter en værdi på tre forskellige steder, og de resterende 4093 værdier i arrayet forbliver nul, de resterende 4093 har vi simpelthen ikke brugt. Det er ikke særlig effektivt, vel?

For at undgå at have et array, der for størstedelens vedkommende er nul og ubrugt, men alligevel optager et værdifuldt stykke hukommelse, kan vi i begyndelsen gemme værdierne som par [indeks, værdi]. Et eksempel for bedre forståelse. Dette 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]

kan vi langt mere hukommelseseffektivt repræsentere som to par:

[0, 7], [4, 12]

I stedet for at have en bunke ubrugt plads allokeret i hukommelsen kan vi gradvist allokere kun den plads, vi virkelig har brug for. Denne repræsentation kalder vi sparse. På et tidspunkt ville denne repræsentation dog være mere hukommelseskrævende end netop at gemme i et array — så kan vi omdanne den sparse repræsentation til et klassisk array uden tab af information.

Offsets

Praksis har vist, at alle værdierne i arrayet er nogenlunde ens. Arrayet med maksima ser normalt fx sådan her ud:

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

Alle værdier ligger et sted omkring tallet 13. En anden strategi til at gøre sådan et array mindre er at trække en fast værdi fra hvert element og huske den. Vi kan fx trække otte fra:

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

Nu bruger hver værdi i arrayet mindre hukommelse — i det første array skal vi gemme tal fra 0 til 15, hvortil vi har brug for 4 bit, mens vi i det andet array nøjes med 3 bit, fordi vi kun gemmer tal fra 0 til 7. Det forudsætter selvfølgelig en implementering af arrayet på niveau med de enkelte bit. Når vi vil læse værdierne fra arrayet, skal vi lægge den noterede værdi til dem igen.

…og en bunke andre forbedringer. Forskningen på området er stadig i gang, så vi kan helt sikkert glæde os til flere interessante idéer. Næste gang fortæller vi lidt om forening og fællesmængde af HyperLogLog-vektorer, og i en nær fremtid fortæller vi, hvorfor det kan være nyttigt at gemme milliarder af HyperLogLog-vektorer.

Links og kilder

• Min egen fulde implementering kan du se på GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — den oprindelige artikel, hvor HyperLogLog blev præsenteret.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — En forbedret version af den oprindelige HyperLogLog, fx med den nævnte sparse repræsentation.