LogLog: slik anslår du antall unike verdier
Etter de forrige delene om Linear Counting og Min Value kommer vi endelig til nesten den aller beste probabilistiske algoritmen for å anslå antall unike verdier i en datamengde, LogLog. Bedre enn den er bare lillebroren HyperLogLog, som bygger på LogLog, men om den skal vi snakke neste gang.
Vi repeterer problemstillingen. Som input har vi en datamengde/multimengde, for eksempel en tabell/generator av ID-er. I denne tabellen finnes noen verdier flere ganger, og vi vil telle antall unike verdier i tabellen. Dette antallet kaller vi kardinalitet. Vi forventer at kardinaliteten er virkelig stor, ellers kan vi bruke konvensjonelle algoritmer.
Tanken bak LogLog-algoritmen
La oss tenke oss at vi har et sett med binære vektorer. Ikke bli redd, for eksempel er dette 0001011001001100 en binær vektor av lengde 16. La oss si at vi har binære vektorer av lengde 32 og at vi har en million av dem, alle helt tilfeldig generert. Hvor mange vektorer ender på sifferet null?
Det kan vi selvfølgelig ikke vite nøyaktig, men hvis vi virkelig genererte vektorene tilfeldig, bør omtrent halvparten av dem ende på null, altså 500 tusen. Hvor mange vektorer ender på 00? En fjerdedel. På 000? En åttedel. Og så videre. Vi kan vise det omtrent slik:
vektormønster andel av alle vektorene
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Hvis vi spør om et suffiks (et suffiks er en streng som en annen streng ender på — det motsatte av et prefiks) med lengde d, forventer vi å finne v vektorer som ender på dette suffikset. Verdien v regner vi ut som:
der N er antall vektorer i settet. Et suffiks med lengde 3 (for eksempel …010) bør forekomme i 1/2^3 N = 1/8 N vektorer, altså 12,5 % av alle vektorene.
Nå gjør vi en liten mindfuck. La oss ha en multimengde med 1024 unike vektorer. Hvor mange vektorer bør ende på suffikset 0000000000? (ti nuller) Vi setter inn i formelen, og får
Huh, én! Blant tusen tilfeldig genererte binære vektorer bør det være akkurat én vektor som ender på ti nuller. Og hvordan bruker vi denne informasjonen til å anslå antall unike elementer? Vi kan nemlig gå motsatt vei. Hva om vi går gjennom alle de binære vektorene vi har som input og finner ut at det i settet finnes én eneste vektor som ender på ti nuller? Da kan vi vel anslå at det var 1024 vektorer i settet!
Vi generaliserer og bygger opp algoritmen
Målet bør være å finne et suffiks som bare finnes i én eneste vektor, og der dette suffikset er så kort som mulig. Det er imidlertid veldig vanskelig, for for å virkelig finne en slik vektor måtte vi lagre alle suffiksene, og det vil vi ikke, for det ville tatt for mye minne. I stedet nøyer vi oss med å lete etter den lengste følgen av nuller på slutten av vektoren.
Vi går altså gjennom alle vektorene, for hver vektor teller vi hvor mange nuller den har på slutten, og i én variabel lagrer vi maksimum av disse verdiene. Når vi har gått gjennom alle vektorene, kjenner vi lengden av det lengste suffikset som bare består av nuller. Denne lengden betegner vi med bokstaven d. Nå skriver vi om den forrige formelen slik at variabelen N står alene, altså slik at den er output fra algoritmen, ikke input. Samtidig kan vi sette inn én i stedet for v, for vi forventer å finne akkurat én slik vektor, altså forventer vi at v=1.
Hvis vi finner lengden d av det lengste nullsuffikset, anslår vi kardinaliteten med formelen N=2d.
Hvordan får vi tilfeldige binære vektorer?
Med tilfeldige binære vektorer fungerer algoritmen allerede, men hvordan bruker vi denne framgangsmåten på virkelige data? Som vanlig bruker vi også her en passende hashfunksjon. Hvis vi har et sett med data som input, for eksempel ID-er (strenger), hasher vi dem først. Outputen fra en n-bits hashfunksjon er n bits som fra et praktisk synspunkt ser ut som tilfeldig genererte binære vektorer.
Nå kan vi skrive opp algoritmen vår:
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
Funksjonen trailing_zeroes returnerer antall nuller på slutten av tallet. Hvordan gjør den det? Hvis du ikke skjønte det av koden, er det bedre å ikke spørre. Og hvor bra fungerer funksjonen? For en mengde som inneholdt hundre tusen unike elementer, ga funksjonen anslaget 524 288.
Tja…
Altså, det er ikke helt bra, ikke sant? Men det gjør ingenting! Vi prøver å forbedre algoritmen på akkurat samme måte som den forrige, Min Value. Vi deler inputdataene i flere disjunkte grupper, for hver gruppe regner vi ut det maksimale nullsuffikset, og til slutt regner vi ut gjennomsnittlig lengde på nullsuffikset og bruker den til å anslå antall unike verdier.
Vi kan for eksempel bestemme at de to siste bitene i hver vektor avgjør nummeret på gruppen vektoren tilhører. Disse seks vektorene
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
kan vi dele i fire grupper etter hvilken endelse de har:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Videre regner vi ut lengden av det lengste nullsuffikset i hver vektor, men der hopper vi over de bitene vi brukte som gruppenummer. Nullsuffiksene markerer vi med grønt:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Til slutt har vi lengdene av de lengste nullsuffiksene fra hver gruppe. Av disse suffiksene kan vi regne ut gjennomsnittet, og det blir 2,75. Vi setter verdien inn i formelen, og får
Vi får det gjennomsnittlige antallet unike elementer i hver gruppe. Det stemmer selvfølgelig ikke i det hele tatt, men det bryr vi oss ikke om, for små mengder gir LogLog-algoritmen fæle resultater.
For å anslå kardinaliteten til hele mengden må vi i tillegg multiplisere denne verdien med antall grupper: 6,727 · 4 = 26,908. Algoritmen regnet ut at det er omtrent 27 unike verdier i settet. Det var seks, så det er helt på jordet, men det gjør egentlig ingenting nå.
Implementasjon av 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 bits som brukes som gruppeindeks. Denne parameteren bestemmer nøyaktigheten til algoritmen — jo høyere k, jo større nøyaktighet. I variabelen bucket_index ligger gruppenummeret. Hvordan fungerer magien på høyre side av likhetstegnet?
I variabelen num_buckets ligger antall grupper, som alltid er en potens av to. Hvis for eksempel k = 3, er num_buckets=8. Tallet 8 har i totallsystemet formen 1000. Når vi trekker fra én, får vi tallet 7, som har formen 0111. Når vi trekker én fra num_buckets, får vi alltid et tall som har k enere på slutten og bare nuller foran. Videre utfører vi et logisk og (det er operatoren &). For vektoren 1110110010100101 ville denne operasjonen se slik ut:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Hensikten med hele denne magien er at vi får et tall som bare har nuller først, og der de siste k bitene er de samme som i den gitte hashen h.
Videre regner vi ut bucket_hash, som er den opprinnelige hashen der vi har fjernet de siste k bitene ved å skyve hele hashen k bits til høyre. Skiftet fungerer slik at alle bitene i tallet rett og slett flyttes k bits til høyre og tallet fylles opp med nuller fra venstre. (En bitforskyvning til høyre med én virker på samme måte som om du delte tallet på to og kastet resten.) Fra vektoren 1110110010100101 ville vi etter å ha skiftet med tre fått 0001110110010100. Denne vektoren ville vært lagret i variabelen bucket_hash.
Videre regner vi ut antall nuller på slutten av denne vektoren, og hvis denne verdien er større enn den nåværende maksimale verdien som er lagret i tabellen max_zeroes på indeksen bucket_index, overskriver vi verdien.
Til slutt regner vi bare ut gjennomsnittlig antall nuller i alle gruppene og regner ut hva det gjennomsnittlige antallet unike elementer i hver gruppe er (2 ** average_max_zeros). Siden vi har num_buckets grupper til sammen, multipliserer vi denne verdien med antall grupper, og da får vi det endelige anslaget på antall unike elementer. Uff, og det gjorde ikke engang vondt. Resultater for noen datasett som inneholder 250 000 unike verdier og k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neeei, fortsatt galt :-(. Men vi er allerede ganske nær, ikke vær redd. Legg merke til at alle resultatene er større enn det riktige resultatet. Underveis i algoritmen hoper det seg nemlig opp ulike feil, og anslaget blir derfor merkbart større enn det riktige resultatet. Likevel er disse feilene ganske stabile, og det går an å anslå hvor stor feilen er. Når vi multipliserer anslaget med tommelfingerkonstanten 0,79402, får vi resultater som er vesentlig bedre:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Jeg prøvde også en multimengde som har kardinalitet en million, resultater:
Resultat Feil
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Nydelig! Feilen ligger under 2,5 %, og det er en habil prestasjon. Og dette, mine damer og herrer, er algoritmen LogLog. Den endelige implementasjonen med tommelfingerkonstanten ser slik ut:
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 vi endrer denne algoritmen for å få den sagnomsuste og aller beste HyperLogLog, forteller vi om neste gang. Foreløpig ser vi på hvor minnekrevende algoritmen er.
Minnebruk
Algoritmen er veldig effektiv når det gjelder brukt minne. Det eneste vi må huske, er tabellen som holder maksimumene. Lengden på denne tabellen påvirkes av verdien k, altså antall bits fra vektoren som vi bruker som gruppeindeks. For en gitt k har vi til sammen 2k ulike grupper, og tabellen med maksimumene har derfor lengde 2k. Denne verdien kalte vi num_buckets i implementasjonen.
Hvor stor må én celle i tabellen være? Vi skal lagre lengdene av nullsuffiksene i den. Jeg kan røpe på forhånd at en 64-bits hash sannsynligvis er nok for alle tenkelige multimengder i verden, så vi må kunne lagre tall fra 0 (en vektor som bare består av enere) til 64 (en vektor som bare består av nuller) i denne tabellen. Hvis vi videre antar at k alltid er større enn null, er det nok å lagre tall fra 0 til 63. Til det holder det faktisk med 6 bits, for 26 = 64.
Ja, vi trenger bare en «tabell» der én celle har størrelse 6 bits. Videre kan jeg røpe at verdien k=10 er nok til å anslå kardinaliteten ganske bra opp til noen hundre millioner. En slik innstilt algoritme ville laget en tabell med størrelse 210 = 1024 der hver celle tar 6 bits. Til sammen ville denne tabellen tatt 6144 bits, altså 768 byte. Ikke engang en kilobyte.
Og det er alt.
Vi trenger ikke å lagre noe annet, de utregnede hashene kan vi kaste med en gang igjen, det er nok å kjenne antall nuller på slutten av vektoren.
Legg merke til at hvis du brukte en større hashfunksjon som for eksempel ga 128 bits, ville minnebruken ikke endret seg særlig. Vi ville nemlig trengt å lagre tall fra 0 til 127, og til det er det nok med 7 bits. Minnebruken bestemmes altså først og fremst av parameteren k, altså antall grupper.
LogLog passer først og fremst der vi trenger å telle multimengder med virkelig stor kardinalitet. Som vi også så i det enkle eksempelet ovenfor, takler LogLog multimengder med liten kardinalitet ikke helt ideelt. Det kan imidlertid også hjelpes, for eksempel ved at vi bruker en annen algoritme til anslaget hvis vi finner ut at multimengden har lav kardinalitet, for eksempel den tidligere beskrevne Linear Counting. Også det kommer vi tilbake til neste gang.
Kilder:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (koden til LogLog er mer eller mindre lånt derfra)
Kapitler: Linear counting: slik anslår du antall unike verdier, Min Value: slik anslår du antall unike verdier, LogLog: slik anslår du antall unike verdier, HyperLogLog: slik anslår du antall unike verdier svært nøyaktig
