Serien om algoritmer som uppskattar antalet unika värden i en multimängd fortsätter med en artikel om state of the art-algoritmen HyperLogLog. Alla idéer bakom den här algoritmen bygger dock på det tidigare beskrivna LogLog, så om du vill läsa vidare bör du kunna LogLog väl.

Algoritmen LogLog hade två huvudproblem:

Avvikande värden

LogLogs slutliga uppskattning är mycket känslig för avvikande värden (outliers), alltså värden som ligger mycket långt från de andra värdena. Det är nämligen typiskt att de flesta maximala längderna på nollsuffix för varje hink är ungefär lika stora, till exempel mellan 12 och 15, men sedan — bom — har ett nollsuffix längden 27. Den stora skillnaden förstör den slutliga uppskattningen av antalet unika värden, eftersom ett vanligt aritmetiskt medelvärde inte klarar av det särskilt bra. I grund och botten gäller samma princip som när några få toppchefer och direktörer med sina höga löner höjer medellönen i landet.

Algoritmens upphovsmän försökte lösa det genom att göra sig av med de avvikande värdena och inte räkna med de högsta maxima i medelvärdet, men det var inte någon vidare bra lösning. Senare provade de ett annat sätt — i stället för det aritmetiska medelvärdet använde de det harmoniska medelvärdet, som har betydligt bättre egenskaper när vi har värden som ligger långt från medelvärdet.

Mycket dåliga resultat för små kardinaliteter

LogLog ger förskräckliga resultat när det ska uppskatta kardinaliteten hos små multimängder. Om vi har bara några få unika element i multimängden ger LogLog en absurt stor uppskattning. Upphovsmännen löste det listigt — när indata är en multimängd med låg kardinalitet används inte algoritmen LogLog, utan en helt annan algoritm, nämligen den gamla goda Linear counting. Ja, men hur vet vi att indata är en multimängd med liten kardinalitet, när vi just inte känner till kardinaliteten?

Vi låter LogLog uppskatta antalet unika element, och om vi ser att uppskattningen är relativt låg kastar vi den och räknar om den med algoritmen Linear counting. Vi påminner snabbt om hur Linear counting fungerar. I början allokerar vi en array av nollor (bitar) med en på förhand given storlek, typiskt en tvåpotens. Vi går igenom alla element i multimängden, räknar ut deras hash och omvandlar den till ett heltal i i intervallet från 0 till arrayens längd minus 1. På index i sparar vi sedan en etta i arrayen. Till sist räknar vi antalet nollor och ettor i arrayen och uppskattar kardinaliteten med hjälp av en enkel formel.

Algoritmen LogLog använder dock ingen bitarray där den ”sparar” de uträknade hashvärdena. I stället använder den en array där den lagrar de maximala suffixlängderna. Arrayen kan till exempel se ut så här:

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

där varje tal anger den maximala längden på nollsuffixet bland de uträknade hashvärdena i respektive hink. Ett nollskilt värde på position i betyder då nödvändigtvis att det i multimängden finns ett element vars (trebitars) hash är lika med i. Med andra ord kan vi omvandla den här arrayen till en bitarray för linear counting genom att behålla nollorna och göra om varje positivt tal till en etta. Av den föregående arrayen skulle vi alltså få bitarrayen:

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

Nu kan vi tillämpa algoritmen Linear counting och uppskatta kardinaliteten med den.

Det finns dock en hake. Vi sparar det maximala nollsuffixet i arrayen, men tänk om alla hashvärden i någon hink slutar på en etta? Om vi till exempel använder de tre sista bitarna som identifierare för hinken som hashvärdet tillhör, skulle längden på nollsuffixet för hashvärdet ”01001100” vara noll — eftersom vektorn ”01001” slutar på en etta. I arrayen av maxima skulle vi alltså spara en nolla på index 4 (100₂=4₁₀). I algoritmen linear counting skulle det visa sig som att vi inte hittade något värde som har fyra som hash, vilket inte är sant.

Därför ändrar vi algoritmen så att den i arrayen av maxima inte sparar längden på det längsta nollsuffixet, utan indexet för ”första ettan från höger” (för ordningens skull — vi indexerar från ett), vilket är samma sak som att addera ett till längden på nollsuffixet. Då uppnår vi att en nolla på index i betyder att inget värde har hashvärdet i, och en sådan array kan vi sedan använda för linear counting.

Implementation av HyperLogLog

Vi tar det steg för steg:

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

Funktionen alpha returnerar korrektionen för den uträknade uppskattningen, det känner vi redan till från förra gången, men för HyperLogLog har alpha ett annat värde beroende på antalet hinkar.

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

En funktion som returnerar antalet nollbitar i slutet av ett 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

En funktion som går igenom alla värden, delar in dem i num_buckets hinkar och för varje hink räknar ut indexet för den första ettan från höger (längden på det maximala nollsuffixet plus ett).

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

En lätt modifierad funktion för att beräkna 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

Huvudfunktionen som sätter ihop allt. Först räknar den ut uppskattningen med den modifierade LogLog, använder på fjärde raden det harmoniska medelvärdet i stället för det aritmetiska medelvärdet och tillämpar till sist korrektionen i form av Linear counting, om den uträknade uppskattningen är mindre än 2,5 gånger antalet hinkar (då förväntar vi oss att den vanliga LogLog-uppskattningen är sämre än om vi hade använt Linear counting) och om det finns minst en nolla i arrayen av maxima (en array som bara består av ettor kan vi inte använda i Linear counting, se föregående artikel). Och hur ser resultaten för HyperLogLog ut?

Vi kör en testkod som uppskattar kardinaliteten hos mängder vars kardinalitet i tur och ordning är 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)

Resultat:

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 att resultaten alltid avviker från det rätta resultatet med mindre än en procent. Och det är bra!

Fler förbättringar av HyperLogLog

HyperLogLog har fått flera andra intressanta förbättringar. Ett av de återstående problemen är det höga minnesbehovet. Det låter ganska konstigt, eftersom vi förra gången prisade minnesbehovet i skyarna och räknade ut att 768 byte räcker för att spara arrayen av maxima. Problemet uppstår dock om du vill räkna kardinaliteten inte för en enda enorm multimängd, utan parallellt för flera miljoner små multimängder, eller om du vill spara de här uträknade arrayerna av maxima i en databas för något senare trixande.

Om vi till exempel räknade kardinaliteten för en miljard multimängder samtidigt skulle vi med den nuvarande implementationen behöva 1 000 000 000 gånger 768 byte, vilket är 768 GB. Å ena sidan är det inte illa … men å andra sidan kan vi implementera HyperLogLog bättre.

Gles representation

Låt oss föreställa oss att vi sätter k=12, dvs. vi använder 12 bitar för att identifiera hinkarna och får därmed 2¹² olika hinkar för hashvärden. I början av algoritmen måste vi allokera en array med längden 4096 (se rad 3 i funktionen count_maxims). Låt oss säga att vår multimängd har tre olika element. Det betyder att vi sätter något värde på tre olika ställen i arrayen, och de övriga 4093 värdena i arrayen förblir nollor, de 4093 har vi helt enkelt inte använt till något. Det är inte särskilt effektivt, eller hur?

För att slippa en array som till största delen består av oanvända nollor men ändå tar upp en värdefull bit minne kan vi i början spara värdena som par [index, värde]. Ett exempel för att det ska bli lättare att förstå. Den här arrayen

[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 representera mycket mer minnessnålt som två par:

[0, 7], [4, 12]

I stället för att ha en hög oanvänd plats allokerad i minnet kan vi efter hand allokera bara den plats som vi verkligen behöver. Den här representationen kallar vi gles (sparse). Vid något tillfälle skulle den här representationen dock kräva mer minne än att spara i en array — då kan vi omvandla den glesa representationen till en vanlig array utan att förlora information.

Offsets

Praktiken har visat att alla värden i arrayen är ungefär lika stora. Arrayen av maxima brukar se ut till exempel så här:

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

Alla värden ligger någonstans kring talet 13. En annan strategi för att göra en sådan array mindre är att dra ifrån varje element ett fast värde och komma ihåg det. Vi kan till exempel dra ifrån åtta:

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

Nu går det åt mindre minne för varje värde i arrayen — i den första arrayen måste vi spara tal från 0 till 15, och för det behöver vi 4 bitar, medan 3 bitar räcker för den andra arrayen, eftersom vi bara sparar tal från 0 till 7. Det förutsätter förstås en implementation av arrayen på nivån för enskilda bitar. När vi vill läsa värdena ur arrayen måste vi lägga tillbaka det antecknade värdet till dem.

…och en hög andra förbättringar. Forskningen inom området pågår fortfarande, så vi kan säkert se fram emot fler intressanta idéer. Nästa gång pratar vi om union och snitt av HyperLogLog-vektorer, och någon gång i en nära framtid pratar vi om varför det kan vara bra att spara miljarder HyperLogLog-vektorer.

Länkar och källor

• Hela min implementation kan du se på GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — den ursprungliga artikeln där HyperLogLog presenterades.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — en förbättrad version av det ursprungliga HyperLogLog, till exempel med den nämnda glesa representationen.