29. 10. 2014

LogLog: Jak odhadnout počet unikátních hodnot

Po předchozích dílech o Linear Countingu a Min Value se konečně dostáváme ke skoro nejvíc nejlepšímu pravděpodobnostnímu algoritmu na odhadování počtu unikátních hodnot v sadě dat, LogLogu. Lepší už je jen jeho bratříček HyperLogLog, který z LogLogu vychází, ale o něm zase příště.

Zopakujeme si zadání problému. Na vstupu máme nějakou sadu dat/multimnožinu, například nějaké pole/generátor idéček. V tomto poli jsou nějaké hodnoty vícekrát a my chceme spočítat počet unikátních hodnot v tomto poli. Tomuto počtu budeme říkat kardinalita. Očekáváme, že tato kardinalita bude opravdu velká, jinak můžeme použít konvenční algoritmy.

Myšlenka LogLog algoritmu

Představme si, že máme sadu binárních vektorů. Nelekejte se, například toto 0001011001001100 je binární vektor délky 16. Dejme tomu, že máme binární vektory délky 32 a že jich máme celkem jeden milion, všechny zcela náhodně vygenerované. Kolik vektorů bude končit číslem nula?

To samozřejmě nemůžeme vědět přesně, ale pokud jsme ty vektory opravdu generovali náhodně, měla by jich nulou končit přibližně polovina, tj. 500 tisíc. Kolik vektorů bude končit na 00? Čtvrtina. Na 000? Osmina. A tak dále. Znázornit to můžeme zhruba takto:

1	vzor vektoru podíl mezi všemi vektory ...xxxxxx0 50 % ...xxxxx00 25 % ...xxxx000 12,5 % ...xxx0000 6,25 % ... ...

Pokud se zeptáme na suffix (suffix je řetězec, kterým končí jiný řetězec – opak prefixu) o délce d, očekáváme, že nalezneme v vektorů, které tímto suffixem končí. Hodnotu v vypočteme jako:

kde N je počet všech vektorů v sadě. Suffix délky 3 (například …010) by se měl vyskytovat v 1/2^3 N = 1/8 N vektorů, tj. 12,5 % ze všech vektorů.

Teď provedeme takový malý mindfuck. Mějme multimnožinu 1024 unikátních vektorů. Kolik vektorů by mělo končit suffixem 0000000000? (deset nul) Dosadíme do vzorce a vyjde nám

Huh, jeden! V tisíci náhodně vygenerovaných binárních vektorů by měl být právě jeden vektor, který končí deseti nulami. A jak tuhle informaci použít k tomu, abychom odhadli počet unikátních prvků? My totiž můžeme postupovat opačně. Co když projdeme všechny binární vektory, které máme na vstupu a zjistíme, že v sadě existuje jediný vektor, který končí deseti nulami? Pak přece můžeme odhadnout, že v sadě bylo 1024 vektorů!

Zobecňujeme a sestavujeme algoritmus

Cílem by mělo být najít takový suffix, který je obsažen pouze v jediném vektoru, přičemž tento suffix je co možná nejkratší. To jde ovšem jen velmi těžko, protože abychom opravdu nalezli takový vektor, museli bychom si všechny suffixy ukládat, což nechceme, protože by to zabralo příliš paměti. Místo toho se spokojíme s tím, že budeme hledat nejdelší posloupnost nul na konci vektoru.

Projdeme tedy všechny vektory, u každého vektoru spočítáme, kolik nul obsahuje na konci a v jedné proměnné si budeme uchovávat maximum z těchto hodnot. Až projdeme všechny vektory, budeme znát délku nejdelšího suffixu, který je tvořen jen nulami. Tuto délku označujeme písmenem d. Nyní upravíme předchozí vzorec tak, abychom osamostatnili proměnnou N, tj. aby to byl výstup algoritmu, ne vstup. Přitom místo v můžeme dosadit jedna, protože očekáváme, že nalezneme právě jeden takový vektor, tj. očekáváme, že bude platit v=1.

Najdeme-li tak délku d nejdelšího nulového suffixu, odhadneme kardinalitu pomocí vzorce N=2^d.

Jak získat náhodné binární vektory?

S náhodnými binárními vektory už nám algoritmus funguje, ale jak tento postup aplikavat na reálná data? Jako obvykle, i zde použijeme nějakou vhodnou hashovací funkci. Máme-li na vstupu sadu dat, například idéčka (stringy), tak je nejprve zahashujeme. Výstupem n-bitové hashovací funkce je n bitů, které z praktického pohledu vypadají jako náhodně vygenerované binární vektory.

V tuto chvíli už můžeme sepsat náš algoritmus:

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(zeros_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

Funkce trailing_zeroes vrací počet nul na konci čísla. Jak to dělá? Jestli jste to nepochopili z kódu, tak se radši ani neptejte. A jakou úspěšnost funkce má? Pro množinu, která obsahovala sto tisíc unikátních prvků vrátila funkce odhad 524 288.

No…

Tak jako není to úplně dobré, že? Ale to nevadí! Zkusíme algoritmus vylepšit úplně stejně, jako předchozí Min Value. Rozdělíme vstupní data na několik disjunktních skupin a pro každou skupinu spočítáme maximální nulový suffix a nakonec spočítáme průměrnou délku nulového suffixu a ten použijeme pro odhad počtu unikátů.

Můžeme si například říci, že poslední dva bity každého vektoru budou určovat číslo skupiny, do které vektor patří. Těchto šest vektorů

1	1101110111111011 1110110010100101 1011001111110010 1111101100000011 1010101000100000 0110010110011000

můžeme rozdělit do čtyř skupin podle toho, jakou mají koncovku:

00                 |  01                |   10                 |  11
---------------------------------------------------------------------------------
10101010001000<span style="color: red">00</span>   |  11101100101001<span style="color: red">01</span>  |  10110011111100<span style="color: red">10</span>    | 11011101111110<span style="color: red">11</span>
01100101100110<span style="color: red">00</span>   |                    |                      | 11111011000000<span style="color: red">11</span>

Dále spočítáme délku nejdelšího nulového suffixu v každém vektoru, přitom ale přeskočíme ty bity, které jsme použili jako číslo skupiny. Nulové “suffixy” označíme zeleně:

00                 |  01                |   10                 |  11
---------------------------------------------------------------------------------
10101010001<span style="color: green">000</span><span style="color: red">00</span>   |  11101100101001<span style="color: red">01</span>  |  101100111111<span style="color: green">00</span><span style="color: red">10</span>    | 1101110111111<span style="color: green">0</span><span style="color: red">11</span>
0110010110011<span style="color: green">0</span><span style="color: red">00</span>   |                    |                      | 11111011<span style="color: green">000000</span><span style="color: red">11</span>
---------------------------------------------------------------------------------
3                  |  0                 |   2                  |  6

V posledním řádku je délka nejdelšího nulového suffixu z dané skupiny. Z těchto suffixů můžeme spočítat aritmetický průměr, který nám vyjde 2,75. Hodnotu dosadíme do vzorce a vyjde nám 2^2,75≈6,727. Získáme průměrný počet unikátních prvků v každé skupině. Což samozřejmě vůbec nesedí, ale tím se netrapme, pro malé množiny dává algoritmus LogLog příšerné výsledky.

Abychom odhadli kardinalitu celé množiny, musíme ještě tuto hodnotu vynásobit počtem skupin: 6,727 · 4 = 26,908. Algoritmus spočítal, že v sadě je přibližně 27 unikátních hodnot. Bylo jich tam šest, takže je to úplně mimo, ale to teď fakt nevadí.

Implementace algoritmu

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

Parametr k určuje, kolik bitů se bude brát jako index skupiny. Tento parametr určuje přesnost algoritmu – čím vyšší k, tím větší přesnost. V proměnné bucket_index je uchováno číslo skupiny. Jak funguje ta magie na pravé straně rovnítka?

V proměnné num_buckets je počet skupin, což je vždy mocnina čísla dva. Pokud například k = 3, pak num_buckets=8. Číslo 8 má ve dvojkové soustavě podobu 1000. Odečteme-li jedničku, dostaneme číslo 7, které má podobu 0111. Po odečtení jedničky od num_buckets vždy dostaneme číslo, které má na konci k jedniček a předtím samé nuly. Dále provedeme logický součin (to je ten operátor &). Pro vektor 1110110010100101 by tato operace vypadala takto:

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

Účelem celé té magie je, abychom získali číslo, které na začátku obsahuje samé nuly a posledních k bitů má stejných jako daný hash h.

Dále spočítáme bucket_hash, což je původní hash, ze kterého odstraníme posledních k bitů tak, že celý hash posuneme o k bitů doprava. Posun se chová tak, že zkrátka všechny bity v čísle posune o k bitů doprava a zleva se číslo doplní nulami. (Bitový posun doprava o jedna se chová stejně, jako byste číslo vydělili dvěma a zahodili zbytek.) Z vektoru 1110110010100101 bychom po posunu o tři dostali 0001110110010100. Tento vektor by byl uložen v proměnné bucket_hash.

Dále spočítáme počet nul na konci tohoto vektoru a pokud je tato hodnota větší než současná maximální hodnota uložená v poli max_zeroes na indexu bucket_index, přepíšeme hodnotu.

Na konci už jen spočítáme průměrný počet nul ve všech skupinách a spočítáme, jaký je průměrný počet unikátních prvků v každé skupině (2 ** average_max_zeros). Protože máme celkem num_buckets skupin, vynásobíme tuto hodnotu právě počtem skupin, čímž získáme finální odhad počtu unikátních prvků. Uf, a ani to nebolelo. Výsledky pro několik sad dat, které obsahují 250 000 unikátů a k=10:

1	331774.56203 323349.39265 307343.444439 309430.914045 294512.379123

Néééé, pořád špatně :-(. Ale už jsme celkem blízko, nebojte. Všimněte si, že všechny výsledky jsou větší než správný výsledek. V průběhu algoritmus se totiž nahromadí různé chyby a odhad je proto znatelně větší než správný výsledek. Nicméně tyto chyby jsou poměrně stálé a lze odhadnout, jak velká chyba nastala. Když odhad vynásobíme hausnumerem 0.79402, získáme výsledky, které jsou zásadně lepší:

1	263435.63774306054 256745.88475195298 244036.84175345476 245694.33437001088 233848.71927124445

Zkusil jsem ještě multimnožinu, která má kardinalitu milion, výsledky:

1	Výsledek Chyba 1017297.17411 1.01729717411 1022820.99717 1.02282099717 984108.725487 0.984108725487 1018675.32683 1.01867532683 1007020.2853 1.0070202853

Hezky pěkně! Chyba se pohybuje pod 2 %, což je slušný výkon. A to je, dámy a pánové, algoritmus LogLog. Finální implementace i s hausnumerem vypadá takto:

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

Jak upravit tento algoritmus abychom získali onen bájný a nejvíc nejlepší HyperLogLog si povíme příště. Prozatím se podíváme na to, jak je algoritmus paměťově náročný.

Paměťová náročnost

Algoritmus je velice efektivní co do zabrané paměti. Jediné, co si musíme pamatovat, je pole udržující maxima. Délka tohoto pole je ovlivněna hodnotou k, tj. počtem bitů z vektoru, které bereme jako index skupiny. Pro dané k máme celkem 2^k různých skupin a pole maxim má proto délku 2^k. Tuto hodnotu jsme v implementaci nazývali num_buckets.

Jak velká musí být jedna buňka pole? Budeme do ní ukládat délky nulových suffixů. Můžu vám dopředu prozradit, že 64bitová hash stačí nejspíš pro všechny myslitelné multimnožiny světa, takže do tohoto pole musíme být schopni uložit čísla od 0 (vektor rovný samým jedničkám) do 64 (vektor rovný samým nulám). Dále, pokud budeme předpokládat, že k bude vždy větší než nula, pak platí, že nám stačí ukládat čísla od 0 do 63. Na to nám, prosím pěkně, stačí 6 bitů, protože 2⁶ = 64.

Ano, stačí nám “pole”, ve kterém má jedna buňka velikost 6 bitů. Dále vám můžu prozradit, že hodnota k=10 stačí na to, abychom celkem slušně odhadli kardinalitu do řádů stovek milionů. Takto nastavený algoritmus by vytvořil pole o velikosti 2¹⁰ = 1024, ve kterém každá buňka zabírá 6 bitů. Celkem by toto pole zabíralo 6144 bitů, což je 768 bajtů. Ani ne kilobajt.

A to je všechno.

Nic jiného ukládat nepotřebujeme, vypočítané hashe můžeme zase hned zahazovat, stačí nám znát počet nul na konci vektoru.

Všimněte si, že pokud byste použili větší hashovací funkci, která by například vracela 128 bitů, paměťová náročnost by se moc nezměnila. Potřebovali bychom totiž uložit čísla od 0 do 127, na což nám stačí 7 bitů. Paměťovou náročnost tak především určuje parametr k, tj. počet skupin.

LogLog se hodí především tam, kde potřebujeme počítat multimnožiny o opravdu velké kardinalitě. Jak bylo vidět i na jednoduché ukázce nahoře, LogLog si ne úplně ideálně poradí s multimnožinami, které mají malou kardinalitu. Tomu lze nicméně také pomoci například tím, že pokud zjistíme, že multimnožina má nízkou kardinalitu, použijeme k odhadu jiný algoritmus, například již dříve popsaný Linear Counting. I o tom bude řeč příště.

Zdroje:

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation (odtud je více méně vykraden kód LogLogu)

Související články:

#algoritmy, #hyperloglog