LogLog: cómo estimar el número de valores distintos
Después de las entregas anteriores sobre Linear Counting y Min Value, llegamos por fin a casi el mejor algoritmo probabilístico para estimar el número de valores distintos de un conjunto de datos: LogLog. Solo lo supera su hermano pequeño, HyperLogLog, que parte de LogLog, pero de ese hablaremos la próxima vez.
Recordemos el planteamiento del problema. Tenemos a la entrada un conjunto de datos o multiconjunto, por ejemplo un array o un generador de identificadores. En ese array algunos valores aparecen varias veces y queremos calcular el número de valores distintos que contiene. A ese número lo llamaremos cardinalidad. Esperamos que la cardinalidad sea realmente muy grande; si no, podemos usar los algoritmos convencionales.
La idea del algoritmo LogLog
Imaginemos que tenemos un conjunto de vectores binarios. No te asustes: por ejemplo, 0001011001001100 es un vector binario de longitud 16. Supongamos que tenemos vectores binarios de longitud 32 y que en total tenemos un millón de ellos, todos generados de forma completamente aleatoria. ¿Cuántos vectores terminarán en cero?
Eso, por supuesto, no podemos saberlo con exactitud, pero si de verdad hemos generado los vectores al azar, aproximadamente la mitad terminará en cero, es decir, 500.000. ¿Cuántos vectores terminarán en 00? Una cuarta parte. ¿Y en 000? Una octava parte. Y así sucesivamente. Podemos representarlo más o menos así:
patrón del vector proporción entre todos los vectores
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Si preguntamos por un sufijo (un sufijo es una cadena con la que termina otra cadena; lo contrario de un prefijo) de longitud d, esperamos encontrar v vectores que terminen en ese sufijo. El valor de v se calcula así:
donde N es el número de todos los vectores del conjunto. Un sufijo de longitud 3 (por ejemplo …010) debería aparecer en 1/2^3 N = 1/8 N vectores, es decir, en el 12,5 % de todos los vectores.
Ahora vamos a hacer un pequeño truco que te va a hacer flipar. Tomemos un multiconjunto de 1024 vectores distintos. ¿Cuántos vectores deberían terminar en el sufijo 0000000000? (diez ceros) Sustituimos en la fórmula y obtenemos
Anda, ¡uno! Entre mil vectores binarios generados al azar debería haber justo un vector que termina en diez ceros. ¿Y cómo usar esta información para estimar el número de elementos distintos? Podemos proceder al revés. ¿Qué pasa si recorremos todos los vectores binarios que tenemos a la entrada y descubrimos que en el conjunto hay un único vector que termina en diez ceros? ¡Entonces podemos estimar que en el conjunto había 1024 vectores!
Generalizamos y construimos el algoritmo
El objetivo sería encontrar un sufijo que esté contenido en un único vector y que sea lo más corto posible. Eso, sin embargo, es muy difícil, porque para encontrar de verdad ese vector tendríamos que guardar todos los sufijos, y no queremos hacerlo porque ocuparía demasiada memoria. En su lugar nos conformaremos con buscar la secuencia de ceros más larga al final de un vector.
Recorremos, pues, todos los vectores, para cada uno calculamos cuántos ceros tiene al final y en una variable guardamos el máximo de esos valores. Cuando hayamos recorrido todos los vectores, conoceremos la longitud del sufijo más largo formado solo por ceros. Esa longitud la designamos con la letra d. Ahora modificamos la fórmula anterior para despejar la variable N, de modo que sea la salida del algoritmo y no la entrada. Además, en lugar de v podemos poner uno, porque esperamos encontrar exactamente un vector así; es decir, esperamos que se cumpla v=1.
Así, si encontramos la longitud d del sufijo de ceros más largo, estimamos la cardinalidad con la fórmula N=2d.
¿Cómo conseguir vectores binarios aleatorios?
Con vectores binarios aleatorios el algoritmo ya funciona, pero ¿cómo aplicar este procedimiento a datos reales? Como de costumbre, también aquí usaremos una función hash adecuada. Si tenemos a la entrada un conjunto de datos, por ejemplo identificadores (strings), primero les calculamos el hash. La salida de una función hash de n bits son n bits que, desde un punto de vista práctico, parecen vectores binarios generados al azar.
Ya podemos escribir nuestro 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 función trailing_zeroes devuelve el número de ceros que hay al final de un número. ¿Cómo lo hace? Si no lo has entendido por el código, mejor ni preguntes. ¿Y qué tal acierta la función? Para un conjunto que contenía cien mil valores distintos, la función devolvió una estimación de 524.288.
Vaya…
Bueno, no es que sea muy buena, ¿verdad? Pero no pasa nada. Intentaremos mejorar el algoritmo exactamente igual que hicimos con el anterior Min Value. Dividiremos los datos de entrada en varios grupos disjuntos, para cada grupo calcularemos el sufijo de ceros máximo y al final calcularemos la longitud media de los sufijos de ceros y la usaremos para estimar el número de valores distintos.
Podemos decidir, por ejemplo, que los dos últimos bits de cada vector determinen el número del grupo al que pertenece. Estos seis vectores
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
los podemos dividir en cuatro grupos según su terminación:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
A continuación calculamos la longitud del sufijo de ceros más largo de cada vector, saltándonos los bits que hemos usado como número de grupo. Marcamos en verde los «sufijos» de ceros:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Al final tenemos las longitudes de los sufijos de ceros más largos de cada grupo. De estos valores podemos calcular la media aritmética, que nos da 2,75. Sustituimos el valor en la fórmula y obtenemos
Así obtenemos el número medio de elementos distintos de cada grupo. Que, por supuesto, no cuadra en absoluto, pero no nos preocupemos: para conjuntos pequeños, el algoritmo LogLog da resultados pésimos.
Para estimar la cardinalidad de todo el conjunto, todavía tenemos que multiplicar este valor por el número de grupos: 6,727 · 4 = 26,908. El algoritmo ha calculado que en el conjunto hay aproximadamente 27 valores distintos. Había seis, así que no se acerca ni de lejos, pero ahora mismo eso de verdad no importa.
Implementación del 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
El parámetro k determina cuántos bits se toman como índice del grupo. Este parámetro determina la precisión del algoritmo: cuanto mayor es k, mayor es la precisión. En la variable bucket_index se guarda el número del grupo. ¿Cómo funciona esa magia a la derecha del signo igual?
En la variable num_buckets está el número de grupos, que siempre es una potencia de dos. Si, por ejemplo, k = 3, entonces num_buckets=8. El número 8 en el sistema binario es 1000. Si le restamos uno, obtenemos el número 7, que es 0111. Al restarle uno a num_buckets siempre obtenemos un número que termina en k unos y delante tiene solo ceros. A continuación hacemos un Y lógico bit a bit (ese es el operador &). Para el vector 1110110010100101 esta operación sería así:
1110110010100101
& 0000000000000111
------------------
0000000000000101
El objetivo de toda esa magia es obtener un número que al principio contiene solo ceros y cuyos últimos k bits son iguales a los del hash h dado.
Después calculamos bucket_hash, que es el hash original al que quitamos los últimos k bits desplazando todo el hash k bits a la derecha. El desplazamiento funciona así: simplemente mueve todos los bits del número k posiciones a la derecha y por la izquierda rellena con ceros. (Un desplazamiento de bits a la derecha de una posición se comporta igual que dividir el número entre dos y descartar el resto.) Del vector 1110110010100101, tras un desplazamiento de tres posiciones, obtendríamos 0001110110010100. Ese vector se guardaría en la variable bucket_hash.
Luego calculamos el número de ceros al final de este vector y, si ese valor es mayor que el máximo actual guardado en el array max_zeroes en el índice bucket_index, sobrescribimos el valor.
Al final solo queda calcular el número medio de ceros de todos los grupos y, con él, el número medio de elementos distintos de cada grupo (2 ** average_max_zeros). Como tenemos num_buckets grupos en total, multiplicamos este valor por el número de grupos y así obtenemos la estimación final del número de valores distintos. Uf, y ni siquiera ha dolido. Resultados para varios conjuntos de datos que contienen 250.000 valores distintos y k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
¡Noooo, sigue mal! :-( Pero ya estamos bastante cerca, no te preocupes. Fíjate en que todos los resultados son mayores que el resultado correcto. Durante el algoritmo se acumulan distintos errores y por eso la estimación es notablemente mayor que el resultado correcto. Sin embargo, esos errores son bastante constantes y se puede estimar de qué tamaño es el error. Si multiplicamos la estimación por una constante empírica, 0,79402, obtenemos resultados mucho mejores:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Probé también con un multiconjunto de cardinalidad un millón; resultados:
Resultado Error
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
¡Muy bien! El error se mueve por debajo del 2,5 %, que es un rendimiento decente. Y este, señoras y señores, es el algoritmo LogLog. La implementación final, con la constante empírica incluida, queda así:
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
Cómo modificar este algoritmo para obtener el legendario HyperLogLog, lo mejor de lo mejor, lo contaremos la próxima vez. De momento veamos cuánta memoria necesita el algoritmo.
Consumo de memoria
El algoritmo es muy eficiente en cuanto a memoria ocupada. Lo único que tenemos que recordar es el array que guarda los máximos. La longitud de este array depende del valor de k, es decir, del número de bits del vector que tomamos como índice del grupo. Para un k dado tenemos en total 2k grupos distintos, y por eso el array de máximos tiene longitud 2k. Este valor es el que en la implementación llamamos num_buckets.
¿De qué tamaño tiene que ser una celda del array? En ella guardaremos longitudes de sufijos de ceros. Te adelanto que una función hash de 64 bits basta probablemente para todos los multiconjuntos imaginables del mundo, así que en este array tenemos que poder guardar números de 0 (un vector formado solo por unos) a 64 (un vector formado solo por ceros). Además, si suponemos que k será siempre mayor que cero, nos basta con guardar números de 0 a 63. Para eso nos bastan —ojo— 6 bits, porque 26 = 64.
Sí, nos basta con un «array» en el que cada celda ocupa 6 bits. Te adelanto también que el valor k=10 basta para estimar la cardinalidad con bastante decencia hasta el orden de cientos de millones. Un algoritmo configurado así crearía un array de tamaño 210 = 1024 en el que cada celda ocupa 6 bits. En total este array ocuparía 6144 bits, que son 768 bytes. Ni siquiera un kilobyte.
Y eso es todo.
No necesitamos guardar nada más; los hashes calculados podemos descartarlos enseguida, nos basta con conocer el número de ceros al final del vector.
Fíjate en que, si usaras una función hash mayor, que devolviera por ejemplo 128 bits, el consumo de memoria no cambiaría mucho. Tendríamos que guardar números de 0 a 127, y para eso nos bastan 7 bits. El consumo de memoria lo determina, pues, sobre todo el parámetro k, es decir, el número de grupos.
LogLog sirve sobre todo allí donde necesitamos contar multiconjuntos de cardinalidad realmente grande. Como se vio ya en el ejemplo sencillo de arriba, LogLog no se las arregla del todo bien con multiconjuntos de cardinalidad pequeña. Aun así, también eso tiene arreglo: si descubrimos que el multiconjunto tiene una cardinalidad baja, usamos para la estimación otro algoritmo, por ejemplo el ya descrito Linear Counting. De eso también hablaremos la próxima vez.
Fuentes:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (de ahí he copiado, más o menos, el código de LogLog)
Capítulos: Linear Counting: cómo estimar el número de valores distintos, Min Value: cómo estimar el número de valores distintos, LogLog: cómo estimar el número de valores distintos, HyperLogLog: cómo estimar con precisión el número de valores distintos
