La serie sobre algoritmos para estimar el número de valores distintos de un multiconjunto continúa con el algoritmo HyperLogLog, el state of the art en la materia. Todas las ideas en las que se basa provienen del LogLog descrito antes, así que, si quieres seguir leyendo, asegúrate de conocer bien LogLog.

El algoritmo LogLog tenía dos problemas principales:

Valores atípicos

La estimación final de LogLog es muy sensible a los valores atípicos (outliers), valores muy alejados del resto. Suele ocurrir que la mayoría de las longitudes máximas de los sufijos de ceros de cada grupo son aproximadamente iguales, por ejemplo entre 12 y 15, pero entonces, ¡zas!, un sufijo de ceros tiene longitud 27. Esa gran diferencia desbarata la estimación final del número de valores distintos, porque la media aritmética clásica no se las arregla muy bien con ella. En el fondo funciona el mismo principio que cuando unos pocos directivos y altos cargos suben con sus sueldos altísimos el sueldo medio del país.

Los autores del algoritmo intentaron resolverlo deshaciéndose de los valores atípicos y no incluyendo en la media algunos de los máximos más altos, pero no fue una solución demasiado buena. Más tarde probaron otro procedimiento: en lugar de la media aritmética usaron la media armónica, que tiene propiedades mucho mejores cuando hay valores alejados de la media.

Resultados muy malos para cardinalidades pequeñas

LogLog tiene resultados pésimos cuando tiene que estimar la cardinalidad de multiconjuntos pequeños. Si en el multiconjunto hay pocos elementos distintos, LogLog nos devuelve una estimación absurdamente grande. Los autores lo resolvieron con astucia: cuando a la entrada tenemos un multiconjunto de cardinalidad baja, no se usa el algoritmo LogLog, sino otro completamente distinto, el viejo conocido Linear Counting. Pero, claro, ¿cómo sabemos que a la entrada tenemos un multiconjunto de cardinalidad pequeña si precisamente no conocemos la cardinalidad?

Dejamos que LogLog estime el número de elementos distintos y, si resulta que esa estimación es relativamente baja, la descartamos y la calculamos de nuevo con el algoritmo Linear Counting. Recordemos rápidamente cómo funciona Linear Counting. Al principio reservamos un array de bits inicializado a cero, de un tamaño fijado de antemano, típicamente una potencia de dos. Recorremos todos los elementos del multiconjunto, calculamos su hash y lo convertimos en un número entero i del intervalo de 0 a la longitud del array menos 1. En el índice i del array guardamos entonces un uno. Por último contamos los ceros y los unos del array y, con una fórmula sencilla, estimamos la cardinalidad.

Pero el algoritmo LogLog no usa ningún array de bits en el que «guardar» los hashes calculados. En su lugar usa un array en el que conserva las longitudes máximas de los sufijos. El array puede ser, por ejemplo, así:

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

donde cada número indica la longitud máxima del sufijo de ceros en el grupo correspondiente de hashes calculados. Un valor distinto de cero en la posición i significa necesariamente que entre los valores del multiconjunto existe un elemento cuyo hash (de tres bits) es igual a i. Dicho de otro modo, este array se puede convertir en el array de bits para Linear Counting dejando los ceros como están y convirtiendo cualquier número positivo en un uno. Del array anterior obtendríamos así este array de bits:

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

Ahora podemos aplicar el algoritmo Linear Counting y estimar con él la cardinalidad.

Eso sí, hay un inconveniente. En el array guardamos el sufijo de ceros máximo, pero ¿y si en algún grupo de valores todos los hashes terminan en uno? Si, por ejemplo, usamos los tres últimos bits como identificador del grupo al que pertenece el hash, la longitud del sufijo de ceros de este hash «01001100» sería cero, porque el vector «01001» termina en uno. En el array de máximos guardaríamos entonces un cero en el índice 4 (100₂=4₁₀). En el algoritmo Linear Counting eso se manifestaría como que no hemos encontrado ningún valor cuyo hash sea cuatro, y eso no es verdad.

Por eso modificamos el algoritmo para que en el array de máximos no guarde la longitud del sufijo de ceros más largo, sino el índice del «primer uno por la derecha» (por claridad: indexamos desde uno), que es lo mismo que sumar uno a la longitud del sufijo de ceros. Así conseguimos que un cero en el índice i signifique que ningún valor tiene hash igual a i, y ese array ya se puede usar para Linear Counting.

Implementación de HyperLogLog

Paso a paso:

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

La función alpha devuelve la corrección de la estimación calculada, algo que ya conocemos de la entrega anterior; solo que en HyperLogLog alpha tiene otro valor, que depende del número de grupos.

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

Una función que devuelve el número de bits cero al final de un número.

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 función que recorre todos los valores, los reparte en num_buckets grupos y para cada grupo calcula el índice del primer uno por la derecha (la longitud del sufijo de ceros máximo más 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 función ligeramente modificada para calcular el 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 función principal, que lo junta todo. Primero calcula la estimación con el LogLog modificado, en la cuarta línea usa en lugar de la media aritmética la media armónica y por último aplica la corrección en forma de Linear Counting si la estimación calculada es menor que 2,5 veces el número de grupos (en ese caso esperamos que la estimación estándar de LogLog sea peor que si usáramos Linear Counting) y si en el array de máximos hay al menos un cero (un array en el que solo hay unos no podemos usarlo en Linear Counting; véase el artículo anterior). ¿Y qué resultados da HyperLogLog?

Ejecutamos un código de prueba que estima la cardinalidad de conjuntos de cardinalidad 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)

Resultados:

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

Vemos que los resultados se desvían siempre del valor correcto en menos de un uno por ciento. ¡Y eso está bien!

Otras mejoras de HyperLogLog

HyperLogLog ha recibido varias mejoras más interesantes. Uno de los problemas que quedan es el alto consumo de memoria. Suena bastante raro, después de que la entrega anterior alabáramos hasta el cielo el consumo de memoria y calculáramos que para guardar el array de máximos nos bastan 768 bytes. Pero el problema surge si quieres calcular la cardinalidad no de un único multiconjunto enorme, sino de varios millones de multiconjuntos pequeños en paralelo, o si quieres conservar estos arrays de máximos en una base de datos para trastear con ellos más adelante.

Si, por ejemplo, calculáramos a la vez la cardinalidad de mil millones de multiconjuntos, con la implementación actual necesitaríamos 1.000.000.000 por 768 bytes, es decir, 768 GB. Por un lado no está mal… pero por otro somos capaces de implementar HyperLogLog mejor.

Representación dispersa

Imaginemos que fijamos k=12, es decir, usamos 12 bits para identificar los grupos y obtenemos por tanto 2¹² grupos de hashes distintos. Al principio del algoritmo tenemos que reservar un array de longitud 4096 (véase la línea 3 de la función count_maxims). Y supongamos que nuestro multiconjunto tiene tres elementos distintos. Eso significa que en el array fijaremos un valor en tres lugares distintos y los 4093 valores restantes del array seguirán siendo cero; los otros 4093 simplemente no los hemos usado para nada. No es muy eficiente, ¿verdad?

Para evitar tener un array que en su mayor parte es cero y no se usa, pero que aun así ocupa un valioso trozo de memoria, podemos al principio guardar los valores como pares [índice, valor]. Un ejemplo para entenderlo mejor. Este 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]

lo podemos representar de manera mucho más eficiente en memoria como dos pares:

[0, 7], [4, 12]

En lugar de tener en memoria un montón de espacio reservado sin usar, podemos ir reservando poco a poco solo el espacio que de verdad necesitamos. A esta representación la llamamos sparse (dispersa). Sin embargo, llega un momento en que esta representación resulta más costosa en memoria que guardarlo directamente en un array; entonces podemos convertir la representación dispersa en el array clásico sin pérdida de información.

Desplazamientos (offsets)

La práctica ha demostrado que todos los valores del array son aproximadamente iguales. El array de máximos suele tener, por ejemplo, este aspecto:

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

Todos los valores rondan el número 13. Otra estrategia para reducir el tamaño de un array así es restar a cada elemento un valor fijo y recordarlo. Podemos restar, por ejemplo, un ocho:

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

Ahora cada valor del array consume menos memoria: en el primer array necesitamos guardar números de 0 a 15, para lo que hacen falta 4 bits, mientras que para el segundo nos bastan 3 bits, porque solo guardamos números de 0 a 7. Por supuesto, esto presupone una implementación del array a nivel de bits individuales. Cuando queramos leer los valores del array, tenemos que volver a sumarles el valor anotado.

…y un montón de mejoras más. La investigación en este campo sigue en marcha, así que seguro que podemos esperar más ideas interesantes. La próxima vez hablaremos de la unión y la intersección de vectores HyperLogLog y, algún día, en un futuro cercano, de por qué puede venirnos bien guardar miles de millones de vectores HyperLogLog.

Enlaces y fuentes

• Puedes ver toda mi implementación en GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF]: el artículo original en el que se presentó HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF]: versión mejorada del HyperLogLog original, por ejemplo con la representación dispersa mencionada.