Sarja algoritmeista, joilla arvioidaan uniikkien arvojen lukumäärää multijoukossa, jatkuu artikkelilla state of the art -algoritmista HyperLogLog. Kaikki tämän algoritmin takana olevat ajatukset kuitenkin perustuvat aiemmin kuvattuun LogLogiin, joten jos haluat lukea eteenpäin, varmista, että tunnet LogLogin hyvin.

LogLog-algoritmilla oli kaksi pääongelmaa:

Poikkeavat havainnot

LogLogin tuloksena saatava arvio on hyvin herkkä poikkeaville havainnoille (outlier), arvoille, jotka ovat hyvin kaukana muista arvoista. Tavallisesti nimittäin käy niin, että suurin osa jokaisen ryhmän nollapäätteiden maksimipituuksista on suunnilleen samoja, esimerkiksi 12:n ja 15:n välillä, mutta sitten pam — ja yhden nollapäätteen pituus on 27. Tämä suuri ero sotkee uniikkien lukumäärän lopullisen arvion, koska tavallinen aritmeettinen keskiarvo ei selviä siitä kovin hyvin. Kyse on samasta ilmiöstä kuin silloin, kun muutama huippujohtaja ja toimitusjohtaja nostaa maan keskipalkkaa suurilla palkoillaan.

Algoritmin tekijät yrittivät ratkaista tämän niin, että he pääsivät eroon poikkeavista havainnoista jättämällä keskiarvosta pois muutaman suurimman maksimin, mutta se ei ollut kovin hyvä ratkaisu. Myöhemmin he kokeilivat toista tapaa — aritmeettisen keskiarvon sijasta he käyttivät harmonista keskiarvoa, jolla on paljon paremmat ominaisuudet silloin, kun meillä on arvoja, jotka ovat kaukana keskiarvosta.

Hyvin huonot tulokset pienille kardinaliteeteille

LogLogin tulokset ovat hirvittäviä, kun sen pitäisi arvioida pienten multijoukkojen kardinaliteettia. Jos multijoukossa on vain muutama uniikki alkio, LogLog palauttaa järjettömän suuren arvion. Tekijät ratkaisivat tämän kikkailemalla — jos syötteenä on multijoukko, jonka kardinaliteetti on pieni, LogLog-algoritmia ei käytetäkään, vaan käytetään kokonaan toista algoritmia, nimittäin vanhaa tuttua Linear countingia. No joo, mutta miten tunnistamme, että syötteenä on multijoukko, jonka kardinaliteetti on pieni, kun kardinaliteettia emme nimenomaan tiedä?

Annamme LogLogin arvioida uniikkien alkioiden lukumäärän, ja kun havaitsemme, että tämä arvio on suhteellisen pieni, hylkäämme arvion ja laskemme sen uudelleen Linear counting -algoritmilla. Kerrataan nopeasti, miten Linear counting toimii. Alussa varaamme nollia sisältävän (bitti)taulukon, jolla on jokin ennalta annettu koko, tyypillisesti kakkosen potenssi. Käymme läpi kaikki multijoukon alkiot, laskemme niiden tiivisteen ja muunnamme sen kokonaisluvuksi i väliltä 0 – taulukon pituus miinus 1. Tallennamme sitten taulukkoon indeksiin i ykkösen. Lopuksi laskemme nollien ja ykkösten lukumäärän taulukossa ja arvioimme kardinaliteetin yksinkertaisella kaavalla.

LogLog-algoritmi ei kuitenkaan käytä mitään bittitaulukkoa, johon se ”tallentaisi” lasketut tiivisteet. Sen sijaan se käyttää taulukkoa, johon se tallentaa loppuosien maksimipituudet. Taulukko voi näyttää esimerkiksi tältä:

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

jolloin jokainen luku tarkoittaa nollapäätteen maksimipituutta kyseisessä laskettujen tiivisteiden ryhmässä. Nollasta poikkeava arvo i:nnessä kohdassa tarkoittaa kuitenkin välttämättä sitä, että multijoukon arvojen joukossa on alkio, jonka (kolmibittinen) tiiviste on i. Toisin sanoen tämän taulukon voi muuntaa linear countingin bittitaulukoksi niin, että nollat jätetään ja mikä tahansa positiivinen luku muunnetaan ykköseksi. Edellisestä taulukosta saisimme siis bittitaulukon:

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

Nyt voimme soveltaa Linear counting -algoritmia ja arvioida kardinaliteetin sen avulla.

Tässä on kuitenkin yksi koukku. Tallennamme taulukkoon pisimmän nollapäätteen, mutta entä jos jossakin arvoryhmässä kaikki tiivisteet päättyvät ykköseen? Jos esimerkiksi käytämme kolmea viimeistä bittiä sen ryhmän tunnisteena, johon tiiviste kuuluu, tämän tiivisteen ”01001100” nollapäätteen pituus olisi nolla — koska vektori ”01001” päättyy ykköseen. Maksimien taulukkoon tallentaisimme siis indeksiin 4 (100₂=4₁₀) nollan. Linear countingissa se näkyisi niin, ettemme löytäneet arvoa, jonka tiiviste olisi neljä, mikä ei pidä paikkaansa.

Siksi muokkaamme algoritmia niin, ettei se tallenna maksimien taulukkoon pisimmän nollapäätteen pituutta, vaan ”oikealta ensimmäisen ykkösen” indeksin (täsmällisyyden vuoksi — indeksoimme ykkösestä), mikä on sama asia kuin lisäisimme nollapäätteen pituuteen yhden. Näin saavutamme sen, että nolla indeksissä i tarkoittaa, ettei yhdenkään arvon tiiviste ole i, ja sellaista taulukkoa voi sitten käyttää linear countingiin.

HyperLogLogin toteutus

Kauniisti vaihe vaiheelta:

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

Funktio alpha palauttaa lasketun arvion korjauksen, se on jo tuttu viime kerralta, vain HyperLogLogin tapauksessa alphalla on eri arvo ryhmien lukumäärän mukaan.

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

Funktio, joka palauttaa nollabittien lukumäärän luvun lopussa.

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

Funktio, joka käy läpi kaikki arvot, jakaa ne num_buckets ryhmään ja laskee jokaiselle ryhmälle oikealta ensimmäisen ykkösen indeksin (pisimmän nollapäätteen pituus plus yksi).

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

Hieman muokattu funktio Linear counting -algoritmin laskemiseen.

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

Pääfunktio, joka kokoaa kaiken yhteen. Ensin se laskee arvion muokatulla LogLogilla, käyttää neljännellä rivillä aritmeettisen keskiarvon sijasta harmonista keskiarvoa ja lopuksi soveltaa korjauksen Linear countingin muodossa, jos laskettu arvio on pienempi kuin 2,5-kertainen ryhmien lukumäärä (tässä vaiheessa odotamme, että LogLogin tavallinen arvio on huonompi kuin jos käytettäisiin Linear countingia) ja jos maksimien taulukossa on ainakin yksi nolla (taulukkoa, jossa on pelkkiä ykkösiä, ei voi käyttää Linear countingissa, katso edellinen artikkeli). Ja millaisia ovat HyperLogLogin tulokset?

Ajamme testikoodin, joka arvioi sellaisten joukkojen kardinaliteetin, joiden kardinaliteetti on vuorotellen 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)

Tulokset:

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

Näemme, että tulokset poikkeavat oikeasta tuloksesta aina alle prosentin. Ja se on hyvä!

HyperLogLogin muita parannuksia

HyperLogLog sai useita muita kiinnostavia parannuksia. Yksi jäljellä olevista ongelmista on suuri muistivaatimus. Se kuulostaa melko oudolta, kun viime kerralla kehuimme muistivaatimusta taivaisiin ja laskimme, että maksimien taulukon tallentamiseen riittää 768 tavua. Ongelma syntyy kuitenkin silloin, kun haluat laskea kardinaliteetin yhden valtavan multijoukon sijasta rinnakkain miljoonille pienille multijoukoille, tai jos haluat säilyttää nämä lasketut maksimien taulukot tietokannassa myöhempiä temppuja varten.

Jos laskisimme esimerkiksi samanaikaisesti miljardin multijoukon kardinaliteetin, tarvitsisimme nykyisellä toteutuksella 1 000 000 000 kertaa 768 tavua, eli 768 GB. Toisaalta se ei ole huono … mutta toisaalta pystymme toteuttamaan HyperLogLogin paremmin.

Harva esitys

Kuvitellaan, että asetamme k=12, eli käytämme 12 bittiä ryhmien tunnistamiseen, ja saamme siis 2¹² eri tiivisteryhmää. Algoritmin alussa meidän täytyy varata taulukko, jonka pituus on 4096 (katso funktion count_maxims rivi 3). Ja oletetaan, että multijoukossamme on kolme eri alkiota. Se tarkoittaa, että taulukkoon asetetaan jokin arvo kolmeen eri paikkaan ja loput 4093 arvoa taulukossa jäävät nolliksi, loput 4093 emme siis käyttäneet millään tavalla. Se ei ole kovin tehokasta, vai mitä?

Jotta vältämme sen, että taulukko on suurimmaksi osaksi nollia ja käyttämätön mutta silti vie arvokkaan palan muistia, voimme alussa tallentaa arvot pareina [indeksi, arvo]. Esimerkki ymmärtämisen avuksi. Tämän taulukon

[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]

voi esittää paljon muistitehokkaammin kahtena parina:

[0, 7], [4, 12]

Sen sijaan, että muistissa olisi varattuna kasa käyttämätöntä tilaa, voimme varata vähitellen vain sen tilan, jota todella tarvitsemme. Tätä esitystä kutsutaan harvaksi (sparse). Jossakin vaiheessa tämä esitys olisi kuitenkin muistin kannalta raskaampi kuin tallentaminen taulukkoon — silloin voimme muuntaa harvan esityksen tavalliseksi taulukoksi menettämättä tietoa.

Offsetit

Käytäntö on osoittanut, että kaikki taulukon arvot ovat suunnilleen samoja. Maksimien taulukko näyttää tavallisesti esimerkiksi tältä:

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

Kaikki arvot liikkuvat jossakin luvun 13 tienoilla. Toinen strategia tällaisen taulukon koon pienentämiseen on vähentää jokaisesta alkiosta jokin kiinteä arvo ja muistaa se. Voimme vähentää esimerkiksi kahdeksan:

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

Tässä vaiheessa jokainen taulukon arvo vie vähemmän muistia — ensimmäiseen taulukkoon täytyy tallentaa luvut 0:sta 15:een, mihin tarvitaan 4 bittiä, kun taas toiseen taulukkoon riittää 3 bittiä, koska tallennamme vain luvut 0:sta 7:ään. Tämä edellyttää tietenkin taulukon toteutusta yksittäisten bittien tasolla. Kun haluamme lukea arvot taulukosta, meidän täytyy lisätä niihin takaisin muistiin merkitty arvo.

…ja kasa muita parannuksia. Tutkimus tällä alalla on yhä käynnissä, joten voimme varmasti odottaa uusia kiinnostavia ideoita. Seuraavalla kerralla kerromme jotakin HyperLogLog-vektorien yhdisteestä ja leikkauksesta, ja joskus lähitulevaisuudessa kerromme, miksi voi olla hyödyllistä tallentaa miljardeja HyperLogLog-vektoreita.

Linkit ja lähteet

• Koko toteutukseni voit katsoa GitHubissa.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — alkuperäinen artikkeli, jossa HyperLogLog esiteltiin.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — alkuperäisen HyperLogLogin parannettu versio, jossa on esimerkiksi mainittu harva esitys.