LogLog: come stimare il numero di valori distinti
Dopo le puntate precedenti su Linear counting e Min Value arriviamo finalmente a LogLog, quasi il migliorissimo algoritmo probabilistico per stimare il numero di valori distinti in un insieme di dati. Meglio c’è solo il suo fratellino HyperLogLog, che deriva da LogLog, ma ne parleremo la prossima volta.
Ripetiamo il problema. In ingresso abbiamo un insieme di dati/multinsieme, per esempio un array/generatore di identificatori. In questo array alcuni valori compaiono più volte e noi vogliamo contare i valori distinti dell’array. Questo numero lo chiameremo cardinalità. Ci aspettiamo che la cardinalità sia davvero grande, altrimenti possiamo usare gli algoritmi convenzionali.
L’idea dell’algoritmo LogLog
Immaginiamo di avere un insieme di vettori binari. Non spaventarti: per esempio 0001011001001100 è un vettore binario di lunghezza 16. Supponiamo di avere vettori binari di lunghezza 32 e di averne in tutto un milione, tutti generati in modo completamente casuale. Quanti vettori finiranno con uno zero?
Naturalmente non possiamo saperlo con esattezza, ma se i vettori sono stati davvero generati a caso, circa la metà dovrebbe finire con zero, cioè 500 mila. Quanti vettori finiranno con 00? Un quarto. Con 000? Un ottavo. E così via. Possiamo rappresentarlo più o meno così:
schema del vettore quota tra tutti i vettori
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Se cerchiamo un suffisso (un suffisso è la stringa con cui termina un’altra stringa, il contrario del prefisso) di lunghezza d, ci aspettiamo di trovare v vettori che terminano con questo suffisso. Il valore v si calcola come:
dove N è il numero di tutti i vettori dell’insieme. Un suffisso di lunghezza 3 (per esempio …010) dovrebbe comparire in 1/2^3 N = 1/8 N vettori, cioè il 12,5% di tutti i vettori.
Ora facciamo un piccolo mindfuck. Prendiamo un multinsieme di 1024 vettori distinti. Quanti vettori dovrebbero terminare con il suffisso 0000000000? (dieci zeri) Sostituiamo nella formula e otteniamo
Huh, uno! In mille vettori binari generati a caso dovrebbe esserci esattamente un vettore che termina con dieci zeri. E come usare questa informazione per stimare il numero di elementi distinti? Possiamo infatti procedere al contrario. Cosa succede se scorriamo tutti i vettori binari che abbiamo in ingresso e scopriamo che nell’insieme esiste un solo vettore che termina con dieci zeri? Allora possiamo stimare che nell’insieme ci fossero 1024 vettori!
Generalizziamo e costruiamo l’algoritmo
L’obiettivo dovrebbe essere trovare un suffisso che sia contenuto in un solo vettore e che sia il più corto possibile. Questo però è molto difficile, perché per trovare davvero un vettore del genere dovremmo salvare tutti i suffissi, cosa che non vogliamo, perché occuperebbe troppa memoria. Ci accontentiamo invece di cercare la sequenza di zeri più lunga alla fine di un vettore.
Scorriamo quindi tutti i vettori, per ciascuno contiamo quanti zeri ha alla fine e in una sola variabile conserviamo il massimo di questi valori. Quando avremo scorso tutti i vettori, conosceremo la lunghezza del suffisso più lungo formato solo da zeri. Indichiamo questa lunghezza con la lettera d. Ora modifichiamo la formula precedente in modo da isolare la variabile N, cioè in modo che sia l’uscita dell’algoritmo, non l’ingresso. Al posto di v possiamo sostituire uno, perché ci aspettiamo di trovare esattamente un vettore di questo tipo, cioè ci aspettiamo che valga v=1.
Se troviamo la lunghezza d del suffisso nullo più lungo, stimiamo quindi la cardinalità con la formula N=2d.
Come ottenere vettori binari casuali?
Con vettori binari casuali l’algoritmo ormai funziona, ma come applicare questo procedimento a dati reali? Come al solito, anche qui useremo una funzione di hash adatta. Se in ingresso abbiamo un insieme di dati, per esempio identificatori (stringhe), prima ne calcoliamo l’hash. L’uscita di una funzione di hash a n bit è formata da n bit che, da un punto di vista pratico, sembrano vettori binari generati a caso.
A questo punto possiamo scrivere il nostro algoritmo:
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
La funzione trailing_zeroes restituisce il numero di zeri alla fine del numero. Come fa? Se non l’hai capito dal codice, meglio non chiedere. E che successo ha la funzione? Per un insieme che conteneva centomila elementi distinti la funzione ha restituito la stima 524.288.
Beh…
Non è proprio il massimo, vero? Ma non importa! Proviamo a migliorare l’algoritmo esattamente come per il precedente Min Value. Dividiamo i dati in ingresso in diversi gruppi disgiunti, per ogni gruppo calcoliamo il suffisso nullo massimo e alla fine calcoliamo la lunghezza media del suffisso nullo e la usiamo per stimare il numero di valori distinti.
Possiamo per esempio stabilire che gli ultimi due bit di ogni vettore determinino il numero del gruppo a cui il vettore appartiene. Questi sei vettori
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
possiamo dividerli in quattro gruppi in base alla terminazione:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Poi calcoliamo la lunghezza del suffisso nullo più lungo di ciascun vettore, saltando però i bit che abbiamo usato come numero del gruppo. I «suffissi» nulli li evidenziamo in verde:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Alla fine abbiamo le lunghezze dei suffissi nulli più lunghi di ciascun gruppo. Da questi suffissi possiamo calcolare la media aritmetica, che ci viene 2,75. Sostituiamo il valore nella formula e otteniamo
Otteniamo il numero medio di elementi distinti in ogni gruppo. Che naturalmente non torna per niente, ma non preoccupiamocene: per piccoli insiemi l’algoritmo LogLog dà risultati pessimi.
Per stimare la cardinalità dell’intero insieme dobbiamo ancora moltiplicare questo valore per il numero di gruppi: 6,727 · 4 = 26,908. L’algoritmo ha calcolato che nell’insieme ci sono circa 27 valori distinti. In realtà erano sei, quindi siamo completamente fuori, ma per ora non importa davvero.
Implementazione dell’algoritmo
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
Il parametro k determina quanti bit si prendono come indice del gruppo. Questo parametro determina la precisione dell’algoritmo: più alto è k, maggiore è la precisione. Nella variabile bucket_index è conservato il numero del gruppo. Come funziona quella magia a destra del segno di uguale?
Nella variabile num_buckets c’è il numero di gruppi, che è sempre una potenza di due. Se per esempio k = 3, allora num_buckets=8. Il numero 8 in binario si scrive 1000. Sottraendo uno otteniamo il numero 7, che si scrive 0111. Sottraendo uno da num_buckets otteniamo sempre un numero che ha alla fine k uni e prima solo zeri. Poi eseguiamo l’AND logico (è l’operatore &). Per il vettore 1110110010100101 questa operazione sarebbe così:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Lo scopo di tutta questa magia è ottenere un numero che all’inizio contiene solo zeri e i cui ultimi k bit sono uguali a quelli dell’hash h dato.
Poi calcoliamo bucket_hash, cioè l’hash originale da cui eliminiamo gli ultimi k bit, spostando l’intero hash di k bit verso destra. Lo scorrimento di bit («shift») si comporta semplicemente così: sposta tutti i bit del numero di k posizioni a destra e a sinistra riempie il numero di zeri. (Lo scorrimento di bit a destra di uno si comporta come se dividessi il numero per due e scartassi il resto.) Dal vettore 1110110010100101, dopo uno scorrimento di tre posizioni, otterremmo 0001110110010100. Questo vettore sarebbe salvato nella variabile bucket_hash.
Poi contiamo gli zeri alla fine di questo vettore e, se questo valore è maggiore del massimo attuale salvato nell’array max_zeroes all’indice bucket_index, sovrascriviamo il valore.
Alla fine calcoliamo solo il numero medio di zeri in tutti i gruppi e calcoliamo il numero medio di elementi distinti in ogni gruppo (2 ** average_max_zeros). Dato che abbiamo in tutto num_buckets gruppi, moltiplichiamo questo valore proprio per il numero di gruppi e otteniamo la stima finale del numero di elementi distinti. Uff, e non ha nemmeno fatto male. Risultati per alcuni insiemi di dati che contengono 250.000 valori distinti e k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Nooo, ancora sbagliato :-(. Ma siamo già abbastanza vicini, non preoccuparti. Osserva che tutti i risultati sono maggiori del risultato corretto. Durante l’algoritmo si accumulano infatti vari errori e la stima è perciò sensibilmente maggiore del risultato corretto. Tuttavia questi errori sono piuttosto costanti ed è possibile stimare quanto sia grande l’errore commesso. Se moltiplichiamo la stima per la costante di correzione 0,79402, otteniamo risultati nettamente migliori:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Ho provato anche con un multinsieme di cardinalità un milione, risultati:
Risultato Errore
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Che bello! L’errore di stima resta sotto il 2,5%, che è una buona prestazione. E questo, signore e signori, è l’algoritmo LogLog. L’implementazione finale con la costante di correzione è così:
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
Come modificare questo algoritmo per ottenere il leggendario e migliorissimo HyperLogLog lo vedremo la prossima volta. Per ora vediamo quanta memoria richiede l’algoritmo.
Occupazione di memoria
L’algoritmo è molto efficiente per quanto riguarda la memoria occupata. L’unica cosa che dobbiamo ricordare è l’array che conserva i massimi. La lunghezza di questo array dipende dal valore di k, cioè dal numero di bit del vettore che prendiamo come indice del gruppo. Per un dato k abbiamo in tutto 2k gruppi diversi e l’array dei massimi ha quindi lunghezza 2k. Questo valore nell’implementazione si chiamava num_buckets.
Quanto deve essere grande una cella dell’array? Ci salveremo le lunghezze dei suffissi nulli. Posso anticiparti che un hash a 64 bit basta con ogni probabilità per tutti i multinsiemi immaginabili del mondo, quindi in questo array dobbiamo poter salvare i numeri da 0 (vettore fatto di soli uni) a 64 (vettore fatto di soli zeri). Inoltre, se supponiamo che k sia sempre maggiore di zero, ci basta salvare i numeri da 0 a 63. Per farlo bastano, pensa un po’, 6 bit, perché 26 = 64.
Sì, ci basta un «array» in cui ogni cella ha la dimensione di 6 bit. Posso anche anticiparti che il valore k=10 basta per stimare la cardinalità in modo abbastanza decente fino all’ordine di centinaia di milioni. Un algoritmo impostato così creerebbe un array di dimensione 210 = 1024, in cui ogni cella occupa 6 bit. In tutto questo array occuperebbe 6144 bit, cioè 768 byte. Nemmeno un kilobyte.
E questo è tutto.
Non dobbiamo salvare nient’altro: gli hash calcolati possiamo subito scartarli di nuovo, ci basta conoscere il numero di zeri alla fine del vettore.
Osserva che, se usassi una funzione di hash più grande, che per esempio restituisse 128 bit, l’occupazione di memoria non cambierebbe granché. Dovremmo infatti salvare i numeri da 0 a 127, e per questo bastano 7 bit. L’occupazione di memoria è quindi determinata soprattutto dal parametro k, cioè dal numero di gruppi.
LogLog è adatto soprattutto dove dobbiamo contare multinsiemi di cardinalità davvero grande. Come si è visto anche nel semplice esempio qui sopra, LogLog non se la cava in modo ideale con i multinsiemi di piccola cardinalità. Anche a questo si può però porre rimedio: per esempio, se scopriamo che il multinsieme ha una cardinalità bassa, per la stima usiamo un altro algoritmo, come il Linear counting descritto in precedenza. Di questo parleremo la prossima volta.
Fonti:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (da qui è più o meno copiato il codice di LogLog)
Capitoli: Linear counting: come stimare il numero di valori distinti, Min Value: come stimare il numero di valori distinti, LogLog: come stimare il numero di valori distinti, HyperLogLog: come stimare con grande precisione il numero di valori distinti
