LogLog: Sådan estimerer du antallet af unikke værdier
Efter de foregående dele om Linear Counting og Min Value er vi endelig nået frem til den næsten allerbedste probabilistiske algoritme til at estimere antallet af unikke værdier i et datasæt, LogLog. Bedre er kun dens lillebror HyperLogLog, som bygger på LogLog, men om den fortæller vi næste gang.
Vi opfrisker opgaven. Som input har vi et datasæt/en multimængde, fx et array/en generator af ID'er. I dette array er nogle værdier med flere gange, og vi vil beregne antallet af unikke værdier i arrayet. Dette antal kalder vi kardinalitet. Vi forventer, at kardinaliteten er rigtig stor, ellers kan vi bruge konventionelle algoritmer.
Grundidéen i LogLog-algoritmen
Lad os forestille os, at vi har et sæt binære vektorer. Bare rolig, fx er 0001011001001100 en binær vektor af længden 16. Lad os sige, at vi har binære vektorer af længden 32, og at vi har en million af dem i alt, alle helt tilfældigt genereret. Hvor mange vektorer ender på et nul?
Det kan vi selvfølgelig ikke vide præcist, men hvis vi virkelig har genereret vektorerne tilfældigt, bør cirka halvdelen af dem ende på nul, dvs. 500 tusind. Hvor mange vektorer ender på 00? En fjerdedel. På 000? En ottendedel. Og så videre. Det kan vi illustrere nogenlunde sådan her:
vektormønster andel af alle vektorer
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Hvis vi spørger efter et suffiks (et suffiks er en streng, som en anden streng ender på — det modsatte af et præfiks) af længden d, forventer vi at finde v vektorer, der ender på dette suffiks. Værdien v beregner vi som:
hvor N er antallet af alle vektorer i datasættet. Et suffiks af længden 3 (fx …010) bør forekomme i 1/2^3 N = 1/8 N vektorer, dvs. 12,5 % af alle vektorer.
Nu laver vi et lille mindfuck. Lad os tage en multimængde med 1024 unikke vektorer. Hvor mange vektorer bør ende på suffikset 0000000000? (ti nuller) Vi indsætter i formlen og får
Huh, én! Blandt tusind tilfældigt genererede binære vektorer bør der være præcis én vektor, der ender på ti nuller. Og hvordan bruger vi den information til at estimere antallet af unikke elementer? Vi kan nemlig gå den modsatte vej. Hvad nu, hvis vi gennemgår alle de binære vektorer, vi har som input, og finder ud af, at der i datasættet findes én eneste vektor, der ender på ti nuller? Så kan vi vel estimere, at der var 1024 vektorer i datasættet!
Vi generaliserer og bygger algoritmen op
Målet bør være at finde et suffiks, som kun er indeholdt i én enkelt vektor, og hvor dette suffiks er så kort som muligt. Det er dog meget svært at gøre, for for at finde sådan en vektor ville vi skulle gemme alle suffikser, hvilket vi ikke vil, fordi det ville optage for meget hukommelse. I stedet nøjes vi med at lede efter den længste række af nuller i slutningen af en vektor.
Vi gennemgår altså alle vektorer, for hver vektor tæller vi, hvor mange nuller den har til sidst, og i én variabel gemmer vi maksimum af disse værdier. Når vi har gennemgået alle vektorer, kender vi længden af det længste suffiks, der kun består af nuller. Denne længde betegner vi med bogstavet d. Nu omskriver vi den foregående formel, så vi isolerer variablen N, dvs. så det er output fra algoritmen og ikke input. I den forbindelse kan vi indsætte én i stedet for v, fordi vi forventer at finde præcis én sådan vektor, dvs. vi forventer, at v=1 gælder.
Når vi finder længden d af det længste nulsuffiks, estimerer vi kardinaliteten med formlen N=2d.
Hvordan får vi tilfældige binære vektorer?
Med tilfældige binære vektorer virker algoritmen allerede, men hvordan anvender vi fremgangsmåden på rigtige data? Som sædvanligt bruger vi også her en passende hashfunktion. Hvis vi har et datasæt som input, fx ID'er (strenge), hasher vi dem først. Outputtet fra en n-bit hashfunktion er n bit, som set fra et praktisk synspunkt ligner tilfældigt genererede binære vektorer.
Nu kan vi skrive vores algoritme ned:
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
Funktionen trailing_zeroes returnerer antallet af nuller i slutningen af et tal. Hvordan gør den det? Hvis du ikke forstod det ud fra koden, så lad være med at spørge. Og hvor god er funktionen? For en mængde, der indeholdt hundrede tusind unikke elementer, returnerede funktionen estimatet 524.288.
Tjaa…
Altså, det er ikke helt godt, vel? Men det gør ikke noget! Vi prøver at forbedre algoritmen på præcis samme måde som den foregående Min Value. Vi deler inputdata op i flere disjunkte grupper, for hver gruppe beregner vi det maksimale nulsuffiks, og til sidst beregner vi den gennemsnitlige længde af nulsuffikset og bruger den til at estimere antallet af unikke værdier.
Vi kan fx sige, at de to sidste bit i hver vektor bestemmer nummeret på den gruppe, som vektoren hører til. Disse seks vektorer
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
kan vi dele op i fire grupper efter deres endelse:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Dernæst beregner vi længden af det længste nulsuffiks i hver vektor, men springer de bit over, som vi brugte som gruppenummer. Nulsuffikserne markerer vi med grønt:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Til sidst har vi længderne af de længste nulsuffikser fra de enkelte grupper. Af disse længder kan vi beregne det aritmetiske gennemsnit, som bliver 2,75. Værdien indsætter vi i formlen og får
Vi får det gennemsnitlige antal unikke elementer i hver gruppe. Hvilket selvfølgelig slet ikke passer, men det tager vi os ikke af, for små mængder giver LogLog-algoritmen rædselsfulde resultater.
For at estimere kardinaliteten af hele mængden skal vi endnu gange denne værdi med antallet af grupper: 6,727 · 4 = 26,908. Algoritmen regnede ud, at der i datasættet er cirka 27 unikke værdier. Der var seks, så det er helt ved siden af, men det gør faktisk ikke noget lige nu.
Implementering af algoritmen
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
Parameteren k bestemmer, hvor mange bit der bruges som gruppeindeks. Denne parameter bestemmer algoritmens præcision — jo højere k, desto større præcision. I variablen bucket_index er gruppens nummer gemt. Hvordan virker den magi på højre side af lighedstegnet?
I variablen num_buckets er antallet af grupper, som altid er en potens af to. Hvis fx k = 3, så er num_buckets=8. Tallet 8 har i det binære talsystem formen 1000. Trækker vi én fra, får vi tallet 7, som har formen 0111. Når vi trækker én fra num_buckets, får vi altid et tal, der til sidst har k ettaller og før dem udelukkende nuller. Dernæst foretager vi et logisk produkt (det er operatoren &). For vektoren 1110110010100101 ville denne operation se sådan her ud:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Formålet med al den magi er, at vi får et tal, som i begyndelsen indeholder udelukkende nuller, og hvis sidste k bit er de samme som i den givne hash h.
Dernæst beregner vi bucket_hash, som er den oprindelige hash, hvor vi har fjernet de sidste k bit ved at forskyde hele hashen k bit til højre. Forskydningen virker sådan, at den simpelthen flytter alle bit i tallet k bit til højre, og tallet fyldes op med nuller fra venstre. (Et bitskift til højre med én virker på samme måde, som hvis du dividerede tallet med to og kasserede resten.) Af vektoren 1110110010100101 ville vi efter et skift med tre få 0001110110010100. Denne vektor ville blive gemt i variablen bucket_hash.
Dernæst beregner vi antallet af nuller i slutningen af denne vektor, og hvis værdien er større end den nuværende maksimale værdi gemt i arrayet max_zeroes på indeks bucket_index, overskriver vi værdien.
Til sidst beregner vi blot det gennemsnitlige antal nuller i alle grupper og regner ud, hvad det gennemsnitlige antal unikke elementer i hver gruppe er (2 ** average_max_zeros). Da vi har num_buckets grupper i alt, ganger vi denne værdi med netop antallet af grupper og får det endelige estimat af antallet af unikke elementer. Pyha, og det gjorde ikke engang ondt. Resultater for nogle datasæt, der indeholder 250.000 unikke værdier, og k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Nejjj, stadig forkert :-(. Men vi er allerede ret tæt på, bare rolig. Læg mærke til, at alle resultaterne er større end det rigtige resultat. Under algoritmen ophobes der nemlig forskellige fejl, og estimatet er derfor mærkbart større end det rigtige resultat. Disse fejl er dog ret stabile, og man kan estimere, hvor stor fejlen er. Når vi ganger estimatet med korrektionskonstanten 0,79402, får vi resultater, der er markant bedre:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Jeg prøvede også en multimængde med kardinaliteten en million, resultaterne:
Resultat Fejl
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Dejligt! Fejlen ligger under 2,5 %, hvilket er en fin præstation. Og det er, mine damer og herrer, algoritmen LogLog. Den endelige implementering med korrektionskonstanten ser sådan her ud:
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
Hvordan man ændrer denne algoritme, så vi får den sagnomspundne og allerbedste HyperLogLog, fortæller vi næste gang. Indtil videre ser vi på, hvor hukommelseskrævende algoritmen er.
Hukommelsesforbrug
Algoritmen er meget effektiv med hensyn til optaget hukommelse. Det eneste, vi skal huske, er arrayet med maksima. Længden af dette array afhænger af værdien k, dvs. antallet af bit fra vektoren, som vi tager som gruppeindeks. For et givet k har vi i alt 2k forskellige grupper, og arrayet med maksima har derfor længden 2k. Denne værdi kaldte vi i implementeringen num_buckets.
Hvor stor skal én celle i arrayet være? Vi gemmer længder af nulsuffikser i den. Jeg kan på forhånd afsløre, at en 64-bit hash nok rækker til alle tænkelige multimængder i verden, så i dette array skal vi kunne gemme tal fra 0 (en vektor bestående af udelukkende ettaller) til 64 (en vektor bestående af udelukkende nuller). Hvis vi desuden antager, at k altid er større end nul, rækker det, at vi gemmer tal fra 0 til 63. Til det rækker 6 bit, bare du ved det, fordi 26 = 64.
Ja, vi har kun brug for et »array«, hvor én celle har størrelsen 6 bit. Desuden kan jeg afsløre, at værdien k=10 rækker til at estimere kardinaliteten helt fint op til størrelsesordenen hundreder af millioner. En algoritme indstillet på den måde ville oprette et array af størrelsen 210 = 1024, hvor hver celle fylder 6 bit. I alt ville dette array fylde 6144 bit, hvilket er 768 byte. Ikke engang et kilobyte.
Og det er alt.
Andet behøver vi ikke gemme, de beregnede hashes kan vi igen straks smide væk, det er nok at kende antallet af nuller i slutningen af vektoren.
Læg mærke til, at hvis du brugte en større hashfunktion, som fx returnerede 128 bit, ville hukommelsesforbruget ikke ændre sig meget. Vi ville nemlig skulle gemme tal fra 0 til 127, og til det rækker 7 bit. Hukommelsesforbruget bestemmes altså først og fremmest af parameteren k, dvs. antallet af grupper.
LogLog egner sig først og fremmest der, hvor vi skal tælle multimængder med en virkelig stor kardinalitet. Som man også kunne se på det enkle eksempel ovenfor, klarer LogLog sig ikke helt ideelt med multimængder, der har en lille kardinalitet. Det kan man dog også afhjælpe, fx ved at bruge en anden algoritme til estimatet, hvis vi finder ud af, at multimængden har en lav kardinalitet, for eksempel den tidligere beskrevne Linear Counting. Det vender vi også tilbage til næste gang.
Kilder:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (herfra er koden til LogLog mere eller mindre stjålet)
Kapitler: Linear counting: Sådan estimerer du antallet af unikke værdier, Min Value: Sådan estimerer du antallet af unikke værdier, LogLog: Sådan estimerer du antallet af unikke værdier, HyperLogLog: Sådan estimerer du meget præcist antallet af unikke værdier
