LogLog: het aantal unieke waarden schatten
Na de vorige delen over linear counting en min value komen we eindelijk bij het bijna allerbeste probabilistische algoritme om het aantal unieke waarden in een dataset te schatten: LogLog. Beter is alleen zijn broertje HyperLogLog, dat op LogLog is gebaseerd, maar daarover de volgende keer meer.
We herhalen de opgave. De invoer is een dataset/multiverzameling, bijvoorbeeld een array/generator van id's. In deze array komen sommige waarden vaker voor en wij willen het aantal unieke waarden in deze array tellen. Dat aantal noemen we de kardinaliteit. We verwachten dat deze kardinaliteit echt heel groot is, anders kunnen we conventionele algoritmen gebruiken.
Het idee van het LogLog-algoritme
Stel je voor dat we een verzameling binaire vectoren hebben. Schrik niet, bijvoorbeeld deze 0001011001001100 is een binaire vector van lengte 16. Stel dat we binaire vectoren van lengte 32 hebben en dat we er in totaal een miljoen hebben, allemaal volledig willekeurig gegenereerd. Hoeveel vectoren eindigen op een nul?
Dat kunnen we natuurlijk niet exact weten, maar als we die vectoren echt willekeurig hebben gegenereerd, zou ongeveer de helft eindigen op een nul, dus 500 duizend. Hoeveel vectoren eindigen op 00? Een kwart. Op 000? Een achtste. En zo verder. We kunnen dat ongeveer zo weergeven:
patroon van de vector aandeel van alle vectoren
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Als we vragen naar een suffix (een suffix is een string waarmee een andere string eindigt — het tegenovergestelde van een prefix) van lengte d, verwachten we v vectoren te vinden die met dit suffix eindigen. De waarde v berekenen we als:
waarbij N het aantal vectoren in de dataset is. Een suffix van lengte 3 (bijvoorbeeld …010) zou voor 1/2^3 N = 1/8 N van de vectoren moeten voorkomen, dus voor 12,5% van alle vectoren.
Nu doen we iets geks. Stel dat we een multiverzameling van 1024 unieke vectoren hebben. Hoeveel vectoren zouden moeten eindigen op het suffix 0000000000? (tien nullen) We vullen in de formule in en krijgen
Huh, één! Onder duizend willekeurig gegenereerde binaire vectoren zou precies één vector moeten zitten die op tien nullen eindigt. En hoe gebruiken we deze informatie om het aantal unieke elementen te schatten? We kunnen namelijk ook omgekeerd te werk gaan. Wat als we alle binaire vectoren van de invoer doorlopen en vaststellen dat er in de dataset één enkele vector is die op tien nullen eindigt? Dan kunnen we toch schatten dat er 1024 vectoren in de dataset zaten!
We veralgemenen en bouwen het algoritme op
Het doel zou moeten zijn een suffix te vinden dat in slechts één vector voorkomt, waarbij dit suffix zo kort mogelijk is. Dat gaat echter heel moeilijk, want om zo'n vector echt te vinden zouden we alle suffixen moeten opslaan, en dat willen we niet, omdat het te veel geheugen zou kosten. In plaats daarvan stellen we ons tevreden met het zoeken naar de langste rij nullen aan het einde van een vector.
We lopen dus alle vectoren door, tellen bij elke vector hoeveel nullen er aan het einde staan en bewaren in één variabele het maximum van deze waarden. Als we alle vectoren hebben doorlopen, kennen we de lengte van het langste suffix dat alleen uit nullen bestaat. Die lengte noemen we d. Nu passen we de vorige formule aan zodat we de variabele N vrijmaken, dus zodat dat de uitvoer van het algoritme is en niet de invoer. Daarbij kunnen we in plaats van v één invullen, omdat we verwachten dat we precies één zo'n vector vinden, dus we verwachten dat v=1 geldt.
Als we de lengte d van het langste suffix van nullen vinden, schatten we de kardinaliteit dus met de formule N=2d.
Hoe krijg je willekeurige binaire vectoren?
Met willekeurige binaire vectoren werkt het algoritme al, maar hoe passen we deze werkwijze toe op echte gegevens? Zoals gewoonlijk gebruiken we ook hier een geschikte hashfunctie. Als de invoer een dataset is, bijvoorbeeld id's (strings), hashen we ze eerst. De uitvoer van een n-bits hashfunctie is n bits, die er vanuit praktisch oogpunt uitzien als willekeurig gegenereerde binaire vectoren.
Nu kunnen we ons algoritme opschrijven:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
De functie trailing_zeroes geeft het aantal nullen aan het einde van een getal terug. Hoe doet ze dat? Als je het niet uit de code hebt begrepen, vraag er dan maar liever niet naar. En hoe succesvol is de functie? Voor een verzameling met honderdduizend unieke elementen gaf de functie de schatting 524 288 terug.
Nou…
Dus, het is niet echt goed, hè? Maar dat geeft niet! We proberen het algoritme op precies dezelfde manier te verbeteren als het vorige, min value. We splitsen de invoergegevens in een aantal disjuncte groepen, berekenen voor elke groep het maximale suffix van nullen en berekenen ten slotte de gemiddelde lengte van het suffix van nullen en gebruiken die om het aantal unieke waarden te schatten.
We kunnen bijvoorbeeld zeggen dat de laatste twee bits van elke vector het nummer bepalen van de groep waartoe de vector behoort. Deze zes vectoren
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
kunnen we in vier groepen verdelen op basis van hun eindstuk:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Vervolgens berekenen we de lengte van het langste suffix van nullen in elke vector, waarbij we de bits overslaan die we als groepsnummer hebben gebruikt. De “suffixen” van nullen markeren we groen:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Onderaan staan de lengtes van de langste suffixen van nullen uit de betreffende groep. Uit deze suffixen kunnen we het rekenkundig gemiddelde berekenen, dat is 2,75. De waarde vullen we in de formule in en we krijgen
We krijgen het gemiddelde aantal unieke elementen in elke groep. Dat klopt natuurlijk helemaal niet, maar daar piekeren we niet over, want voor kleine verzamelingen geeft het LogLog-algoritme vreselijke resultaten.
Om de kardinaliteit van de hele verzameling te schatten, moeten we deze waarde nog met het aantal groepen vermenigvuldigen: 6,727 · 4 = 26,908. Het algoritme heeft berekend dat er ongeveer 27 unieke waarden in de dataset zitten. Het waren er zes, dus het zit er helemaal naast, maar dat maakt nu echt niet uit.
Implementatie van het algoritme
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
De parameter k bepaalt hoeveel bits als groepsindex worden genomen. Deze parameter bepaalt de nauwkeurigheid van het algoritme — hoe hoger k, hoe groter de nauwkeurigheid. In de variabele bucket_index staat het groepsnummer (bucket). Hoe werkt die magie aan de rechterkant van het gelijkteken?
In de variabele num_buckets staat het aantal groepen, dat altijd een macht van twee is. Als bijvoorbeeld k = 3, dan is num_buckets=8. Het getal 8 heeft in het tweetallig stelsel de vorm 1000. Trekken we er één af, dan krijgen we het getal 7, dat de vorm 0111 heeft. Als we één aftrekken van num_buckets, krijgen we altijd een getal dat aan het einde k enen heeft en daarvoor allemaal nullen. Vervolgens voeren we de bewerking logische en uit (dat is de operator &). Voor de vector 1110110010100101 zou deze bewerking er zo uitzien:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Het doel van al die magie is dat we een getal krijgen dat vooraan allemaal nullen heeft en waarvan de laatste k bits gelijk zijn aan die van de gegeven hash h.
Vervolgens berekenen we bucket_hash, dat is de oorspronkelijke hash waarvan we de laatste k bits hebben verwijderd door de hele hash k bits naar rechts te schuiven. Het schuiven werkt zo dat alle bits in het getal gewoon k bits naar rechts opschuiven en dat links het getal met nullen wordt aangevuld. (Een bitverschuiving naar rechts met één werkt hetzelfde als wanneer je het getal door twee deelt en de rest weggooit.) Uit de vector 1110110010100101 zouden we na een verschuiving met drie 0001110110010100 krijgen. Deze vector zou in de variabele bucket_hash worden opgeslagen.
Vervolgens berekenen we het aantal nullen aan het einde van deze vector en als die waarde groter is dan de huidige maximale waarde die in de array max_zeroes op index bucket_index is opgeslagen, overschrijven we de waarde.
Aan het einde berekenen we alleen nog het gemiddelde aantal nullen in alle groepen en bepalen we wat het gemiddelde aantal unieke elementen in elke groep is (2 ** average_max_zeros). Omdat we in totaal num_buckets groepen hebben, vermenigvuldigen we deze waarde met het aantal groepen, waarmee we de uiteindelijke schatting van het aantal unieke elementen krijgen. Poeh, en dat deed niet eens pijn. De resultaten voor een paar datasets die 250 000 unieke waarden bevatten, met k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neeeee, nog steeds fout :-(. Maar we zijn al best dichtbij, geen zorgen. Merk op dat alle resultaten groter zijn dan het juiste resultaat. Tijdens het algoritme stapelen zich namelijk verschillende fouten op en de schatting is daardoor merkbaar groter dan het juiste resultaat. Die fouten zijn echter vrij constant en je kunt inschatten hoe groot de fout is. Als we de schatting met de correctieconstante 0,79402 vermenigvuldigen, krijgen we resultaten die aanzienlijk beter zijn:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Ik heb ook een multiverzameling met kardinaliteit een miljoen geprobeerd, de resultaten:
Resultaat Fout
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Mooi zo! De fout blijft onder 2,5%, en dat is een behoorlijke prestatie. En dat is, dames en heren, het LogLog-algoritme. De uiteindelijke implementatie, inclusief de correctieconstante, ziet er zo uit:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Hoe we dit algoritme aanpassen om het legendarische en allerbeste HyperLogLog te krijgen, vertellen we de volgende keer. Voorlopig kijken we naar het geheugengebruik van het algoritme.
Geheugengebruik
Het algoritme is erg efficiënt wat betreft gebruikt geheugen. Het enige wat we hoeven te onthouden is de array met de maxima. De lengte van deze array wordt bepaald door de waarde van k, dus het aantal bits van de vector dat we als groepsindex nemen. Voor een gegeven k hebben we in totaal 2k verschillende groepen en de array met maxima heeft daarom lengte 2k. Deze waarde noemden we in de implementatie num_buckets.
Hoe groot moet één cel van de array zijn? We gaan daarin de lengtes van de suffixen van nullen opslaan. Ik kan je vooraf verklappen dat een 64-bits hash waarschijnlijk volstaat voor alle denkbare multiverzamelingen ter wereld, dus we moeten in deze array getallen kunnen opslaan van 0 (een vector die alleen uit enen bestaat) tot 64 (een vector die alleen uit nullen bestaat). Als we verder aannemen dat k altijd groter dan nul is, dan geldt dat het volstaat getallen van 0 tot 63 op te slaan. Daarvoor hebben we, let wel, genoeg aan 6 bits, want 26 = 64.
Ja, we hebben genoeg aan een “array” waarin één cel 6 bits groot is. Verder kan ik je verklappen dat de waarde k=10 volstaat om de kardinaliteit redelijk behoorlijk te schatten tot in de honderden miljoenen. Een zo ingesteld algoritme zou een array van grootte 210 = 1024 maken, waarin elke cel 6 bits inneemt. In totaal zou deze array 6144 bits innemen, dat is 768 bytes. Nog geen kilobyte.
En dat is alles.
Verder hoeven we niets op te slaan, de berekende hashes kunnen we meteen weer weggooien, we hoeven alleen het aantal nullen aan het einde van de vector te kennen.
Merk op dat als je een grotere hashfunctie zou gebruiken, die bijvoorbeeld 128 bits teruggeeft, het geheugengebruik niet veel zou veranderen. We zouden dan namelijk getallen van 0 tot 127 moeten opslaan, en daarvoor volstaan 7 bits. Het geheugengebruik wordt dus vooral bepaald door de parameter k, dus het aantal groepen.
LogLog is vooral geschikt waar we multiverzamelingen met een echt grote kardinaliteit moeten tellen. Zoals ook in het eenvoudige voorbeeld hierboven te zien was, kan LogLog niet helemaal ideaal omgaan met multiverzamelingen die een kleine kardinaliteit hebben. Dat kan echter ook worden verholpen, bijvoorbeeld doordat we, als we merken dat de multiverzameling een lage kardinaliteit heeft, een ander algoritme gebruiken voor de schatting, bijvoorbeeld het eerder beschreven linear counting. Daarover de volgende keer meer.
Bronnen:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (de code van LogLog is er min of meer van overgenomen)
Hoofdstukken: Linear counting: het aantal unieke waarden schatten, Min value: het aantal unieke waarden schatten, LogLog: het aantal unieke waarden schatten, HyperLogLog: het aantal unieke waarden heel nauwkeurig schatten
