A multihalmazban lévő egyedi értékek számát becslő algoritmusokról szóló sorozat a HyperLogLog nevű state of the art algoritmussal folytatódik. Az algoritmus mögötti ötletek mind a korábban leírt LogLogból indulnak ki, ezért ha tovább akarsz olvasni, győződj meg róla, hogy jól ismered a LogLogot.

A LogLog algoritmusnak két fő problémája volt:

Kiugró értékek

A LogLog végső becslése nagyon érzékeny a kiugró értékekre, vagyis azokra az értékekre, amelyek nagyon messze esnek a többitől. Jellemzően ugyanis az történik, hogy a csoportonkénti maximális nullás utótaghosszak többsége nagyjából egyforma, mondjuk 12 és 15 között mozog, aztán hirtelen – bumm – az egyik nullás utótag hossza 27. Ez a nagy különbség felborítja az egyedi elemek számának végső becslését, mert a hagyományos számtani közép ezt nem kezeli jól. Lényegében ugyanaz az elv működött, mint amikor néhány felsővezető és igazgató a magas fizetésével megemeli az átlagfizetést az országban.

Az algoritmus szerzői ezt úgy próbálták megoldani, hogy megszabadultak a kiugró értékektől, és az átlagba nem számítottak bele néhány legnagyobb maximumot, de ez nem volt túl jó megoldás. Később másik eljárást próbáltak ki – a számtani közép helyett harmonikus közepet használtak, amelynek sokkal jobb tulajdonságai vannak, ha az átlagtól távoli értékek is vannak.

Nagyon rossz eredmények kis számosságnál

A LogLog borzalmas eredményeket ad, ha kis multihalmaz számosságát kell becsülnie. Ha a multihalmazban csak néhány egyedi elem van, a LogLog értelmetlenül nagy becslést ad. A szerzők ezt agyafúrtan oldották meg – ha a bemeneten kis számosságú multihalmaz van, nem a LogLog algoritmust használják, hanem egy egészen másikat, mégpedig a régi ismerőst, a Linear countingot. Na de honnan tudjuk, hogy a bemeneten kis számosságú multihalmaz van, ha éppen a számosságot nem ismerjük?

Hagyjuk, hogy a LogLog megbecsülje az egyedi elemek számát, és ha azt találjuk, hogy ez a becslés viszonylag alacsony, a becslést eldobjuk, és újraszámoljuk a Linear counting algoritmussal. Gyorsan idézzük fel, hogyan működik a Linear counting. Az elején létrehozunk egy nullákból álló (bit)tömböt valamilyen előre megadott méretben, ami jellemzően kettő hatványa. Végigmegyünk a multihalmaz összes elemén, kiszámoljuk a hash-üket, és ezt a 0 és a tömb hossza mínusz 1 közötti i egész számmá alakítjuk. Az i indexen aztán a tömbben egyest tárolunk. Végül megszámoljuk a nullákat és az egyeseket a tömbben, és az egyszerű képlet segítségével megbecsüljük a számosságot.

A LogLog algoritmus azonban nem használ semmilyen bittömböt, amelybe a kiszámolt hasheket „tárolná”. Helyette olyan tömböt használ, amelyben az utótagok maximális hosszát őrzi. A tömb kinézhet például így:

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

ahol minden szám a kiszámolt hashek adott csoportjában a maximális nullás utótag hosszát jelöli. Az i-edik pozíción álló nem nulla érték viszont szükségképpen azt jelenti, hogy a multihalmaz értékei között létezik olyan elem, amelynek a (hárombites) hash-e egyenlő i-vel. Más szóval ezt a tömböt úgy alakíthatjuk át a linear counting bittömbjévé, hogy a nullákat meghagyjuk, bármely pozitív számot pedig egyesre cseréljük. Az előző tömbből tehát ezt a bittömböt kapnánk:

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

Most már alkalmazhatjuk a Linear counting algoritmust, és vele megbecsülhetjük a számosságot.

Ennek azonban van egy bökkenője. Mi a maximális nullás utótagot tároljuk a tömbben, de mi van, ha valamelyik csoportban az összes hash egyesre végződik? Ha például az utolsó három bitet használjuk annak a csoportnak az azonosítójára, amelyhez a hash tartozik, akkor a „01001100” hash nullás utótagjának hossza nulla lenne – mert a „01001” vektor egyesre végződik. A maximumok tömbjében tehát a 4-es indexen (100₂=4₁₀) nullát tárolnánk. A linear countingban ez viszont úgy jelentkezne, hogy nem találtunk olyan értéket, amelynek a hash-e négy, ami nem igaz.

Ezért úgy alakítjuk át az algoritmust, hogy a maximumok tömbjébe ne a leghosszabb nullás utótag hosszát tárolja, hanem az „első egyes indexét jobbról” (a rend kedvéért – egytől indexelünk), ami ugyanaz, mintha a nullás utótag hosszához hozzáadnánk egyet. Ezzel elérjük, hogy az i indexen álló nulla azt jelenti, hogy egyetlen érték hash-e sem egyenlő i-vel, és az ilyen tömböt már használhatjuk a linear countinghoz.

A HyperLogLog megvalósítása

Szépen sorban:

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

Az alpha függvény a kiszámolt becslés korrekcióját adja vissza, ezt már ismerjük a múltkorról, csak a HyperLogLognál az alpha értéke a csoportok számától függően más.

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

A függvény, amely a szám végén álló nulla bitek számát adja vissza.

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

A függvény, amely végigmegy az összes értéken, num_buckets csoportra osztja őket, és minden csoportra kiszámolja az első egyes indexét jobbról (a maximális nullás utótag hossza plusz egy).

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

A Linear counting algoritmus kiszámolására szolgáló, kissé módosított függvény.

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

A főfüggvény, amely mindezt összefogja. Először kiszámolja a becslést a módosított LogLoggal, a számtani közép helyett a negyedik sorban harmonikus közepet használ, végül alkalmazza a korrekciót a Linear counting formájában, ha a kiszámolt becslés kisebb, mint a csoportok számának 2,5-szerese (ilyenkor azt várjuk, hogy a LogLog szokásos becslése rosszabb lesz, mintha Linear countingot használnánk), és ha a maximumok tömbjében van legalább egy nulla (a csupa egyesből álló tömböt nem használhatjuk a Linear countingban, lásd az előző cikket). És milyen eredményeket ad a HyperLogLog?

Lefuttatunk egy tesztkódot, amely sorban 10, 100, …, 1 000 000 számosságú halmazok számosságát becsüli:

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)

Eredmények:

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

Látjuk, hogy az eredmények mindig kevesebb mint egy százalékkal térnek el a helyes eredménytől. És ez jó!

A HyperLogLog további továbbfejlesztései

A HyperLogLog még több érdekes továbbfejlesztést is kapott. Az egyik megmaradt probléma a nagy memóriaigény. Ez elég furcsán hangzik, hiszen múltkor az egekig dicsértük a memóriaigényt, és kiszámoltuk, hogy a maximumok tömbjének tárolásához 768 bájt elég. Csakhogy a probléma akkor jelentkezik, ha nem egyetlen óriási multihalmaz számosságát akarod kiszámolni, hanem párhuzamosan több millió kis multihalmazét, vagy ha ezeket a kiszámolt maximumtömböket valamilyen későbbi mutatványhoz adatbázisban akarod megőrizni.

Ha például egyszerre egymilliárd multihalmaz számosságát számolnánk, a jelenlegi megvalósítással 1 000 000 000-szer 768 bájtra lenne szükségünk, ami 768 GB. Egyrészt ez nem rossz … másrészt viszont a HyperLogLogot meg tudjuk valósítani jobban is.

Sparse reprezentáció

Képzeljük el, hogy beállítjuk k=12-t, vagyis 12 bitet használunk a csoportok azonosítására, így 2¹² különböző hash-csoportunk lesz. Az algoritmus elején 4096 hosszúságú tömböt kell létrehoznunk (lásd a count_maxims függvény 3. sorát). Tegyük fel, hogy a multihalmazunknak három különböző eleme van. Ez azt jelenti, hogy a tömbben három különböző helyre állítunk be valamilyen értéket, a maradék 4093 érték pedig nulla marad, ezt a maradék 4093-at egyszerűen semmire sem használtuk. Ez nem túl hatékony, ugye?

Hogy elkerüljük az olyan tömböt, amely nagyrészt nulla és használatlan, mégis értékes memóriát foglal, az elején az értékeket [index, érték] párokként tárolhatjuk. Egy példa a jobb megértéshez. Ezt a tömböt

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

sokkal memóriahatékonyabban ábrázolhatjuk két párként:

[0, 7], [4, 12]

Ahelyett, hogy a memóriában rengeteg kihasználatlan helyet foglalnánk le, fokozatosan csak azt a helyet foglaljuk le, amelyre valóban szükségünk van. Ezt az ábrázolást sparse-nak nevezzük. Egy ponton viszont ez az ábrázolás már memóriaigényesebb lenne, mint a tömbben való tárolás – ekkor a sparse reprezentációt információvesztés nélkül átalakíthatjuk klasszikus tömbbé.

Eltolások

A gyakorlat azt mutatta, hogy a tömb összes értéke nagyjából egyforma. A maximumok tömbje általában például így néz ki:

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

Az értékek mind valahol a 13 körül mozognak. A tömb méretének csökkentésére másik stratégia, hogy minden elemből levonunk egy rögzített értéket, és ezt megjegyezzük. Levonhatunk például nyolcat:

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

Ilyenkor a tömb minden értéke kevesebb memóriát igényel – az első tömbben 0-tól 15-ig kell számokat tárolnunk, amihez 4 bit kell, a második tömbhöz viszont 3 bit is elég, mert csak 0-tól 7-ig tárolunk számokat. Ez persze feltételezi, hogy a tömböt egyes bitek szintjén valósítjuk meg. Amikor az értékeket ki akarjuk olvasni a tömbből, vissza kell adnunk hozzájuk a megjegyzett értéket.

…és még egy csomó továbbfejlesztés. Ezen a területen a kutatás még mindig tart, ezért biztosan számíthatunk további érdekes ötletekre. Legközelebb a HyperLogLog-vektorok egyesítéséről és metszetéről lesz szó, és valamikor a közeljövőben arról is, miért jöhet jól, ha milliárdnyi HyperLogLog-vektort tárolunk.

Hivatkozások és források

• Az egész megvalósításomat megnézheted a GitHubon.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – az eredeti cikk, amelyben a HyperLogLogot bemutatták.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – az eredeti HyperLogLog továbbfejlesztett változata, például az említett sparse reprezentációval.