La serie sugli algoritmi per stimare il numero di valori distinti in un multinsieme prosegue con l’algoritmo HyperLogLog, lo stato dell’arte in questo campo. Tutte le idee alla base di questo algoritmo derivano però da LogLog, descritto in precedenza: se vuoi continuare a leggere, assicurati di conoscere bene LogLog.

L’algoritmo LogLog aveva due problemi principali:

Valori anomali

La stima finale di LogLog è molto sensibile ai valori anomali, cioè a valori molto lontani dagli altri. Tipicamente succede che la maggior parte delle lunghezze massime dei suffissi nulli dei singoli gruppi sia più o meno la stessa, per esempio tra 12 e 15, e poi, all’improvviso, un suffisso nullo ha lunghezza 27. Questa grande differenza rovina la stima del numero di valori distinti, perché la classica media aritmetica non la gestisce bene. In sostanza vale lo stesso principio per cui pochi dirigenti e amministratori delegati, con i loro stipendi altissimi, fanno salire lo stipendio medio di un paese.

Gli autori dell’algoritmo cercarono di risolvere il problema eliminando i valori anomali, cioè escludendo dalla media alcuni dei massimi più alti, ma non era una buona soluzione. In seguito provarono un altro procedimento: al posto della media aritmetica usarono la media armonica, che ha proprietà molto migliori quando ci sono valori lontani dalla media.

Risultati molto scadenti per piccole cardinalità

LogLog dà risultati pessimi quando deve stimare la cardinalità di multinsiemi piccoli. Se nel multinsieme ci sono pochissimi elementi distinti, LogLog restituisce una stima assurdamente grande. Gli autori lo hanno risolto con un’idea astuta: quando l’input è un multinsieme di bassa cardinalità, non si usa LogLog, ma un algoritmo completamente diverso, il vecchio e noto Linear counting. Ma come capiamo che l’input ha una cardinalità piccola, se proprio la cardinalità non la conosciamo?

Lasciamo che LogLog stimi il numero di elementi distinti e, se la stima risulta relativamente bassa, la scartiamo e la calcoliamo di nuovo con Linear counting. Ricordiamo rapidamente come funziona Linear counting. All’inizio allochiamo un vettore (di bit) nullo di dimensione prestabilita, tipicamente una potenza di due. Scorriamo tutti gli elementi del multinsieme, calcoliamo il loro hash e lo trasformiamo in un numero intero i compreso tra 0 e la lunghezza del vettore meno 1. Nella posizione i del vettore scriviamo un 1. Alla fine contiamo gli zeri e gli uno nel vettore e stimiamo la cardinalità con una formula semplice.

L’algoritmo LogLog, però, non usa nessun vettore di bit in cui «memorizzare» gli hash calcolati. Usa invece un array in cui conserva le lunghezze massime dei suffissi. L’array può essere, per esempio, questo:

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

dove ogni numero indica la lunghezza massima del suffisso nullo nel rispettivo gruppo di hash calcolati. Un valore diverso da zero nella posizione i-esima significa necessariamente che nel multinsieme esiste un elemento il cui hash (a tre bit) è uguale a i. In altre parole, possiamo trasformare questo array nel vettore di bit per Linear counting lasciando gli zeri e sostituendo con 1 ogni numero positivo. Dall’array precedente otteniamo così il vettore di bit:

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

Ora possiamo applicare Linear counting e stimare con esso la cardinalità.

C’è però un inconveniente. Nell’array salviamo il suffisso nullo massimo, ma che cosa succede se in un gruppo tutti gli hash terminano con un 1? Se, per esempio, usiamo gli ultimi tre bit come identificatore del gruppo a cui appartiene l’hash, allora il suffisso nullo dell’hash «01001100» avrebbe lunghezza zero, perché il vettore «01001» termina con un 1. Nell’array dei massimi nella posizione 4 (100₂=4₁₀) salveremmo quindi uno zero. In Linear counting questo significherebbe che non abbiamo trovato nessun valore con hash uguale a quattro, il che non è vero.

Per questo modifichiamo l’algoritmo in modo che nell’array dei massimi non salvi la lunghezza del suffisso nullo più lungo, ma la posizione del «primo 1 da destra» (per precisione, numeriamo a partire da uno), il che equivale ad aggiungere uno alla lunghezza del suffisso nullo. In questo modo uno zero nella posizione i significa che nessun valore ha hash uguale a i, e un array fatto così si può usare per Linear counting.

Implementazione di HyperLogLog

Un passo alla volta:

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

La funzione alpha restituisce la correzione per la stima calcolata. La conosciamo già dall’articolo precedente, solo che in HyperLogLog alpha ha un valore diverso a seconda del numero di gruppi.

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

Una funzione che restituisce il numero di bit nulli alla fine di un numero.

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

Una funzione che scorre tutti i valori, li divide in num_buckets gruppi e per ogni gruppo calcola la posizione del primo 1 da destra (la lunghezza del suffisso nullo massimo più uno).

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

Una funzione leggermente modificata per calcolare l’algoritmo Linear counting.

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

La funzione principale, che mette insieme tutto. Per prima cosa calcola la stima con il LogLog modificato, usando alla quarta riga la media armonica al posto della media aritmetica; infine applica la correzione con Linear counting, se la stima calcolata è minore di 2,5 volte il numero di gruppi (in questo caso ci aspettiamo che la stima standard di LogLog sia peggiore di quella di Linear counting) e se nell’array dei massimi c’è almeno uno zero (un array fatto solo di uno non si può usare in Linear counting, vedi l’articolo precedente). E quali sono i risultati di HyperLogLog?

Eseguiamo un codice di prova che stima la cardinalità di insiemi con cardinalità 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)

Risultati:

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

Vediamo che i risultati si discostano sempre dal valore corretto per meno dell’1%. E questo è un ottimo risultato!

Altri miglioramenti di HyperLogLog

HyperLogLog ha ricevuto parecchi altri miglioramenti interessanti. Uno dei problemi rimasti è l’elevato consumo di memoria. Suona strano, visto che la volta scorsa abbiamo lodato fino al cielo il basso consumo di memoria e abbiamo calcolato che per salvare l’array dei massimi bastano 768 byte. Il problema nasce però se vuoi calcolare la cardinalità non di un solo enorme multinsieme, ma di diversi milioni di piccoli multinsiemi in parallelo, oppure se vuoi conservare in un database questi array dei massimi per usarli più avanti in altre operazioni.

Se, per esempio, calcolassimo contemporaneamente la cardinalità di un miliardo di multinsiemi, con l’implementazione attuale ci servirebbero 1.000.000.000 per 768 byte, cioè 768 GB. Da un lato non è male … ma dall’altro siamo in grado di implementare HyperLogLog meglio.

Rappresentazione sparsa

Immaginiamo di impostare k=12, cioè di usare 12 bit per identificare i gruppi, e di ottenere quindi 2¹² gruppi di hash diversi. All’inizio dell’algoritmo dobbiamo allocare un array di lunghezza 4096 (vedi la riga 3 della funzione count_maxims). Supponiamo che il nostro multinsieme abbia tre elementi diversi. Questo significa che nell’array impostiamo un valore in tre posizioni diverse e i restanti 4093 valori dell’array restano nulli: semplicemente non li abbiamo usati in alcun modo. Non è molto efficiente, vero?

Per evitare di avere un array in gran parte nullo e inutilizzato, che occupa comunque una preziosa quantità di memoria, all’inizio possiamo salvare i valori come coppie [indice, valore]. Un esempio per capire meglio. Questo array

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

si può rappresentare in modo molto più efficiente per la memoria con due coppie:

[0, 7], [4, 12]

Invece di tenere in memoria un mucchio di spazio inutilizzato, possiamo allocare gradualmente solo lo spazio che serve davvero. Questa si chiama rappresentazione sparsa. A un certo punto, però, questa rappresentazione occuperebbe più memoria del semplice array: allora possiamo convertire la rappresentazione sparsa in un array classico senza perdere informazioni.

Offset

La pratica ha mostrato che tutti i valori dell’array sono più o meno uguali. L’array dei massimi di solito ha un aspetto come questo:

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

Tutti i valori stanno intorno al numero 13. Un’altra strategia per ridurre la dimensione di un array così è sottrarre da ogni elemento un valore fisso e ricordarselo. Possiamo sottrarre, per esempio, otto:

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

A questo punto ogni valore dell’array occupa meno memoria: nel primo array dobbiamo salvare numeri da 0 a 15, e per questo servono 4 bit, mentre per il secondo array ne bastano 3, perché salviamo solo numeri da 0 a 7. Naturalmente questo presuppone un’implementazione dell’array a livello dei singoli bit. Quando vorremo leggere i valori dall’array, dovremo sommare di nuovo il valore che ci siamo annotati.

…e un mucchio di altri miglioramenti. La ricerca in questo campo è ancora in corso, quindi possiamo di sicuro aspettarci altre idee interessanti. La prossima volta parleremo di unione e intersezione di vettori HyperLogLog e, in un futuro non lontano, spiegheremo perché può essere utile salvare miliardi di vettori HyperLogLog.

Link e fonti

• Puoi guardare la mia implementazione completa su GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – l’articolo originale in cui è stato presentato HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – una versione migliorata dell’HyperLogLog originale, per esempio con la rappresentazione sparsa di cui abbiamo parlato.