LogLog: miten arvioidaan uniikkien arvojen lukumäärä

Aiempien osien Linear Countingista ja Min Valuesta päästään vihdoin melkein kaikkein parhaaseen todennäköisyysalgoritmiin uniikkien arvojen lukumäärän arvioimiseksi dataryhmässä, LogLogiin. Sitä parempi on enää sen pikkuveli HyperLogLog, joka perustuu LogLogiin, mutta siitä taas ensi kerralla.

Kerrataan tehtävänanto. Syötteenä on jokin dataryhmä/multijoukko, esimerkiksi jokin tunnisteiden taulukko/generaattori. Tässä taulukossa on joitakin arvoja useammin kuin kerran, ja haluamme laskea uniikkien arvojen lukumäärän tässä taulukossa. Tätä lukumäärää kutsumme kardinaliteetiksi. Odotamme, että tämä kardinaliteetti on todella suuri, muuten voimme käyttää tavanomaisia algoritmeja.

LogLog-algoritmin ajatus

Kuvitellaan, että meillä on joukko binäärivektoreita. Älä säiky, esimerkiksi tämä 0001011001001100 on binäärivektori, jonka pituus on 16. Oletetaan, että meillä on binäärivektoreita, joiden pituus on 32, ja että niitä on yhteensä miljoona, kaikki täysin satunnaisesti generoituja. Kuinka monta vektoria päättyy nollaan?

Sitä emme tietenkään voi tietää tarkasti, mutta jos olemme todella generoineet vektorit satunnaisesti, noin puolen pitäisi päättyä nollaan, eli 500 tuhatta. Kuinka monta vektoria päättyy merkkijonoon 00? Neljännes. Merkkijonoon 000? Kahdeksasosa. Ja niin edelleen. Sen voi havainnollistaa suunnilleen näin:

vektorin muoto    osuus kaikista vektoreista
...xxxxxx0        50 %
...xxxxx00        25 %
...xxxx000        12,5 %
...xxx0000        6,25 %
     ...          ...

Jos kysymme loppuosaa (suffiksi on merkkijono, johon toinen merkkijono päättyy — etuliitteen eli prefiksin vastakohta), jonka pituus on d, odotamme löytävämme v vektoria, jotka päättyvät tähän loppuosaan. Arvon v laskemme kaavalla:

$v = \frac{1}{2^{d}} \cdot N$

jossa N on kaikkien dataryhmän vektoreiden lukumäärä. Pituutta 3 olevan loppuosan (esimerkiksi …010) pitäisi esiintyä 1/2^3 N = 1/8 N vektorissa, eli 12,5 % kaikista vektoreista.

Nyt teemme pienen aivopähkinän. Olkoon meillä multijoukko, jossa on 1024 uniikkia vektoria. Kuinka monen vektorin pitäisi päättyä loppuosaan 0000000000? (kymmenen nollaa) Sijoitamme kaavaan ja saamme

$v = \frac{1}{2^{10}} \cdot 1024 = \frac{1}{1024} \cdot 1024 = 1$

Huh, yksi! Tuhannessa satunnaisesti generoidussa binäärivektorissa pitäisi olla täsmälleen yksi vektori, joka päättyy kymmeneen nollaan. Ja miten tätä tietoa käytetään uniikkien alkioiden lukumäärän arvioimiseen? Voimme nimittäin edetä päinvastoin. Entä jos käymme läpi kaikki syötteenä olevat binäärivektorit ja havaitsemme, että dataryhmässä on yksi ainoa vektori, joka päättyy kymmeneen nollaan? Silloinhan voimme arvioida, että dataryhmässä oli 1024 vektoria!

Yleistetään ja rakennetaan algoritmi

Tavoitteena pitäisi olla löytää sellainen loppuosa, joka sisältyy vain yhteen vektoriin, ja tämä loppuosa on mahdollisimman lyhyt. Se on kuitenkin hyvin vaikeaa, koska jotta todella löytäisimme sellaisen vektorin, meidän pitäisi tallentaa kaikki loppuosat, mitä emme halua, koska se veisi liikaa muistia. Sen sijaan tyydymme etsimään pisintä nollien jonoa vektorin lopussa.

Käymme siis läpi kaikki vektorit, jokaisesta vektorista laskemme, kuinka monta nollaa sen lopussa on, ja säilytämme yhdessä muuttujassa näiden arvojen maksimin. Kun olemme käyneet läpi kaikki vektorit, tiedämme pisimmän pelkistä nollista koostuvan loppuosan pituuden. Tätä pituutta merkitsemme kirjaimella d. Nyt muokkaamme edellistä kaavaa niin, että muuttuja N jää yksin, eli se on algoritmin tuloste eikä syöte. Samalla v:n tilalle voimme sijoittaa yhden, koska odotamme löytävämme täsmälleen yhden sellaisen vektorin, eli odotamme, että pätee v=1.

$\begin{array}{rcl} v & = & \frac{N}{2^{d}} \\ v \cdot 2^{d} & = & N \\ 2^{d} & = & N \end{array}$

Jos siis löydämme pisimmän nollapäätteen pituuden d, arvioimme kardinaliteetin kaavalla N=2^d.

Miten saadaan satunnaisia binäärivektoreita?

Satunnaisilla binäärivektoreilla algoritmi jo toimii, mutta miten tätä menetelmää sovelletaan oikeaan dataan? Kuten yleensä, tässäkin käytämme jotakin sopivaa tiivistefunktiota. Jos syötteenä on dataryhmä, esimerkiksi tunnisteet (merkkijonot), tiivistämme ne ensin. n-bittisen tiivistefunktion tuloste on n bittiä, jotka käytännön kannalta näyttävät satunnaisesti generoiduilta binäärivektoreilta.

Nyt voimme jo kirjoittaa algoritmimme:

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

Funktio trailing_zeroes palauttaa nollien lukumäärän luvun lopussa. Miten se sen tekee? Jos et ymmärtänyt sitä koodista, älä edes kysy. Ja kuinka hyvin funktio onnistuu? Joukolle, joka sisälsi satatuhatta uniikkia alkiota, funktio palautti arvion 524 288.

No…

Ei se ihan hyvä ole, vai mitä? Mutta ei se haittaa! Yritämme parantaa algoritmia täsmälleen samalla tavalla kuin edellisessä Min Valuessa. Jaamme syötedatan useaan erilliseen ryhmään, jokaiselle ryhmälle laskemme pisimmän nollapäätteen, ja lopuksi laskemme nollapäätteen keskimääräisen pituuden ja käytämme sitä uniikkien lukumäärän arviointiin.

Voimme esimerkiksi sanoa, että jokaisen vektorin kaksi viimeistä bittiä määräävät ryhmän numeron, johon vektori kuuluu. Nämä kuusi vektoria

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

voimme jakaa neljään ryhmään sen mukaan, mikä niiden pääte on:

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

Seuraavaksi laskemme jokaisen vektorin pisimmän nollapäätteen pituuden, mutta ohitamme ne bitit, joita käytimme ryhmän numerona. Nolla-”päätteet” merkitsemme vihreällä:

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

Lopussa ovat kunkin ryhmän pisimpien nollapäätteiden pituudet. Näistä pituuksista voimme laskea aritmeettisen keskiarvon, joksi saamme 2,75. Sijoitamme arvon kaavaan ja saamme

$2^{2, 75} \approx 6,727$

Saamme uniikkien alkioiden keskimääräisen lukumäärän kussakin ryhmässä. Se ei tietenkään täsmää lainkaan, mutta ei murehdita sitä, pienille joukoille LogLog-algoritmi antaa hirvittäviä tuloksia.

Arvioidaksemme koko joukon kardinaliteetin meidän täytyy vielä kertoa tämä arvo ryhmien lukumäärällä: 6,727 · 4 = 26,908. Algoritmi laski, että dataryhmässä on noin 27 uniikkia arvoa. Niitä oli kuusi, joten se on aivan pielessä, mutta sillä ei nyt todella ole väliä.

Algoritmin toteutus

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

Parametri k määrää, kuinka monta bittiä otetaan ryhmän indeksiksi. Tämä parametri määrää algoritmin tarkkuuden — mitä suurempi k, sitä suurempi tarkkuus. Muuttujaan bucket_index tallentuu ryhmän numero. Miten se taikuus yhtäläisyysmerkin oikealla puolella toimii?

Muuttujassa num_buckets on ryhmien lukumäärä, joka on aina luvun kaksi potenssi. Jos esimerkiksi k = 3, niin num_buckets=8. Luku 8 on kaksijärjestelmässä muotoa 1000. Kun vähennämme siitä yhden, saamme luvun 7, joka on muotoa 0111. Kun luvusta num_buckets vähennetään yksi, saamme aina luvun, jonka lopussa on k ykköstä ja sitä ennen pelkkiä nollia. Seuraavaksi teemme loogisen JA-operaation (se on operaattori &). Vektorille 1110110010100101 tämä operaatio näyttäisi tältä:

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

Koko tämän taikuuden tarkoitus on saada luku, jonka alussa on pelkkiä nollia ja jonka viimeiset k bittiä ovat samat kuin annetussa tiivisteessä h.

Seuraavaksi laskemme bucket_hashin, joka on alkuperäinen tiiviste, josta poistamme viimeiset k bittiä siirtämällä koko tiivistettä k bittiä oikealle. Siirto toimii niin, että se yksinkertaisesti siirtää kaikkia luvun bittejä k bittiä oikealle, ja vasemmalta luku täytetään nollilla. (Bittisiirto oikealle yhdellä toimii samoin kuin jakaisit luvun kahdella ja hylkäisit jakojäännöksen.) Vektorista 1110110010100101 saisimme kolmen siirron jälkeen vektorin 0001110110010100. Tämä vektori tallentuisi muuttujaan bucket_hash.

Seuraavaksi laskemme tämän vektorin lopussa olevien nollien lukumäärän, ja jos tämä arvo on suurempi kuin taulukkoon max_zeroes indeksiin bucket_index tallennettu nykyinen maksimiarvo, kirjoitamme arvon yli.

Lopuksi laskemme enää nollien keskimääräisen lukumäärän kaikissa ryhmissä ja laskemme, mikä on uniikkien alkioiden keskimääräinen lukumäärä kussakin ryhmässä (2 ** average_max_zeros). Koska ryhmiä on yhteensä num_buckets, kerromme tämän arvon juuri ryhmien lukumäärällä, ja saamme lopullisen arvion uniikkien alkioiden lukumäärästä. Huh, eikä se edes sattunut. Tulokset muutamalle dataryhmälle, joissa on 250 000 uniikkia ja k=10:

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

Eiiii, yhä väärin :-(. Mutta olemme jo melko lähellä, älä huoli. Huomaa, että kaikki tulokset ovat suurempia kuin oikea tulos. Algoritmin aikana nimittäin kertyy erilaisia virheitä, ja arvio on siksi selvästi suurempi kuin oikea tulos. Nämä virheet ovat kuitenkin melko pysyviä, ja niiden suuruuden voi arvioida. Kun kerromme arvion taikaluvulla 0.79402, saamme tuloksia, jotka ovat huomattavasti parempia:

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

Kokeilin vielä multijoukkoa, jonka kardinaliteetti on miljoona, tulokset:

Tulos                 Virhe
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

Oikein mainiota! Virhe on alle 2,5 %, mikä on kelvollinen suoritus. Ja tämä, hyvät naiset ja herrat, on LogLog-algoritmi. Lopullinen toteutus taikaluvun kanssa näyttää tältä:

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

Miten tätä algoritmia muokataan, jotta saamme tuon legendaarisen ja kaikkein parhaan HyperLogLogin, kerromme ensi kerralla. Toistaiseksi katsomme, kuinka muistiraskas algoritmi on.

Muistivaatimus

Algoritmi on erittäin tehokas varatun muistin kannalta. Ainoa, mitä meidän täytyy muistaa, on maksimit säilyttävä taulukko. Tämän taulukon pituuteen vaikuttaa arvo k, eli niiden vektorin bittien lukumäärä, jotka otamme ryhmän indeksiksi. Annetulla k:lla meillä on yhteensä 2^k eri ryhmää, ja maksimien taulukon pituus on siksi 2^k. Tätä arvoa kutsuimme toteutuksessa nimellä num_buckets.

Kuinka suuri yhden taulukon solun täytyy olla? Tallennamme siihen nollapäätteiden pituuksia. Voin paljastaa jo etukäteen, että 64-bittinen tiiviste riittää luultavasti kaikille maailman kuviteltavissa oleville multijoukoille, joten tähän taulukkoon täytyy pystyä tallentamaan luvut 0:sta (pelkistä ykkösistä koostuva vektori) 64:ään (pelkistä nollista koostuva vektori). Lisäksi, jos oletamme, että k on aina suurempi kuin nolla, riittää tallentaa luvut 0:sta 63:een. Siihen riittää, kas vain, 6 bittiä, koska 2⁶ = 64.

Kyllä, meille riittää ”taulukko”, jossa yhden solun koko on 6 bittiä. Voin lisäksi paljastaa, että arvo k=10 riittää siihen, että arvioimme kardinaliteetin melko kelvollisesti satojen miljoonien suuruusluokkaan asti. Tällä tavalla asetettu algoritmi loisi taulukon, jonka koko on 2¹⁰ = 1024 ja jossa jokainen solu vie 6 bittiä. Yhteensä tämä taulukko veisi 6 144 bittiä, eli 768 tavua. Ei edes kilotavua.

Ja siinä kaikki.

Mitään muuta emme tarvitse tallentaa, lasketut tiivisteet voimme heti taas hylätä, riittää että tiedämme nollien lukumäärän vektorin lopussa.

Huomaa, että jos käyttäisit isompaa tiivistefunktiota, joka palauttaisi esimerkiksi 128 bittiä, muistivaatimus ei muuttuisi kovin paljon. Meidän pitäisi nimittäin tallentaa luvut 0:sta 127:ään, mihin riittää 7 bittiä. Muistivaatimuksen määrää siis ennen kaikkea parametri k, eli ryhmien lukumäärä.

LogLog sopii ennen kaikkea sinne, missä meidän täytyy laskea todella suuren kardinaliteetin multijoukkoja. Kuten yllä olevasta yksinkertaisesta esimerkistä näkyi, LogLog ei selviä ihan ihanteellisesti multijoukoista, joiden kardinaliteetti on pieni. Tähänkin voi kuitenkin auttaa esimerkiksi niin, että jos havaitsemme multijoukon kardinaliteetin olevan pieni, käytämme arvioon jotakin toista algoritmia, esimerkiksi aiemmin kuvattua Linear Countingia. Siitäkin puhutaan ensi kerralla.

Lähteet:

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation (täältä LogLogin koodi on enemmän tai vähemmän varastettu)

Luvut: Linear counting: miten arvioidaan uniikkien arvojen lukumäärä, Min Value: miten arvioidaan uniikkien arvojen lukumäärä, LogLog: miten arvioidaan uniikkien arvojen lukumäärä, HyperLogLog: miten uniikkien arvojen lukumäärä arvioidaan hyvin tarkasti

« Edellinen: Min Value: miten arvioidaan uniikkien arvojen lukumäärä

Seuraava: HyperLogLog: miten uniikkien arvojen lukumäärä arvioidaan hyvin tarkasti »