Esta es la razón por la cual el algoritmo HyperLogLog es mi nuevo favorito

Sucribete a nuestro canal de Youtube


 

Visita nuestra paguina en Facebook


 

Visita a la paguina oficial

De vez en cuando me encuentro con un concepto tan simple y poderoso que desearía haber descubierto una idea tan increíble y hermosa.

Descubrí HyperLogLog (HLL) hace un par de años y me enamoré justo después de leer cómo Redis decidió agregar una estructura de datos HLL .

La idea detrás de HLL es devastadoramente simple pero extremadamente poderosa. Esto es lo que lo convierte en un algoritmo tan extendido, utilizado por gigantes de internet como Google y Reddit.

Recolectando números telefónicos

Mi amigo Tommy y yo planeamos ir a una conferencia. Mientras nos dirigíamos a su ubicación, decidimos apostar quién conocería a la gente más nueva. Una vez que llegamos al lugar, comenzamos a conversar y mantener un contador de la cantidad de personas con las que hablamos.

Al final del evento, Tommy acude a mí con su figura, digamos, 17, y le digo que he hablado con 46 personas.

Claramente, soy el ganador, pero Tommy está frustrado ya que cree que he contado a las mismas personas varias veces. Él cree que solo me vio hablando con tal vez 15-20 personas en total.

Entonces, la apuesta está apagada. Decidimos que para nuestro próximo evento, eliminaremos nombres, para asegurarnos de contar personas únicas, y no solo el número total de conversaciones.

Al final de la siguiente conferencia, nos encontramos con una larga lista de nombres y, ¿adivinen qué? ¡Tommy tuvo un par de encuentros más que yo! Nos reímos, y mientras hablamos de nuestro enfoque para contar los únicos, a Tommy se le ocurre una gran idea:

“Alex, ¿sabes qué? No podemos ir con bolígrafo y papel y rastrear una lista de nombres, ¡es realmente poco práctico! Hoy hablé con 65 personas diferentes y contar sus nombres en este documento fue un verdadero dolor. ¡Perdí la cuenta tres veces y tuve que empezar desde cero!

“Sí, lo sé, pero ¿tenemos siquiera una alternativa?”

“¿Qué pasa si, en nuestra próxima conferencia, en lugar de pedir nombres, le preguntamos a las personas los últimos 5 dígitos de su número de teléfono? En lugar de ganar contando sus nombres, el ganador será quien le haya hablado a alguien con la secuencia más larga de ceros a la izquierda en esos dígitos “.

“Espera Tommy, vas demasiado rápido! Reduzca la velocidad un segundo y déme un ejemplo … “

“Claro, solo pregúntale a cada persona por los últimos 5 dígitos, ¿está bien? Supongamos que responden ‘54701’. No hay cero a la izquierda, por lo que la secuencia más larga de ceros a la izquierda es 0. La siguiente persona con la que hablas dice “02561”: ¡eso es un cero a la izquierda! Entonces, tu secuencia más larga ahora es 1. “

“Estás empezando a tener sentido para mí …”

“Sí, así que si hablamos solo con un par de personas, lo más probable es que la secuencia cero más larga sea 0. Pero si hablamos con quizás 10 personas, tenemos más posibilidades de que sea 1.”

“Ahora, imagine que me dice que su secuencia cero más larga es 5: ¡debe haber hablado con miles de personas para encontrar a alguien con 00000 en su número de teléfono!”

“¡Amigo, eres un maldito genio!”

Y eso, mis amigos, es cómo funciona HyperLogLog fundamentalmente.

Nos permite estimar elementos únicos dentro de un gran conjunto de datos registrando la secuencia más larga de ceros dentro de ese conjunto.

Esto termina creando una ventaja increíble sobre el seguimiento de todos y cada uno de los elementos del conjunto. Es una forma increíblemente eficiente de contar valores únicos, con una precisión relativamente alta.

“El algoritmo HyperLogLog puede estimar cardinalidades mucho más allá de 10⁹ con una precisión relativa (error estándar) del 2% mientras solo usa 1.5kb de memoria”

Fangjin Yang:  rápido, barato y 98% correcto: estimación de cardinalidad para Big Data

Como puedo simplificar demasiado, echemos un vistazo a algunos detalles más de HLL.

Más detalles de HLL

HLL es parte de una familia de algoritmos que tienen como objetivo abordar la estimación de cardinalidad  , también conocida como el “problema de conteo diferenciado”. ¿Cómo podemos contar eficazmente el número de objetos únicos en un conjunto de datos?

Esto es extremadamente útil para muchas aplicaciones web de hoy en día. Por ejemplo, cuando desea contar cuántas vistas únicas ha generado un artículo en su sitio.

Cuando se ejecuta HLL, toma sus datos de entrada y los mezcla, convirtiéndolos en una secuencia de bits:

Dirección IP del espectador: 54.134.45.789
Hash HLL: 010010101010101010111010 ...

Ahora, una parte importante de HLL es asegurarse de que su función de hash distribuya los bits lo más uniformemente posible. No quiere usar una función débil como:

Un HLL que use esta función de hash devolverá resultados parciales si, por ejemplo, la distribución de sus visitantes está vinculada a una región geográfica específica .

El documento original tiene algunos detalles más sobre lo que significa una buena función hash para HLL:

“Todos los estimadores de cardinalidad eficientes conocidos se basan en la aleatorización, que se garantiza mediante el uso de funciones hash.

Los elementos a contar pertenecen a un determinado dominio de datos D, asumimos que tiene una función hash, h: D → {0, 1} ∞; es decir, asimilamos valores hash a infinitas cadenas binarias de {0, 1} ∞ o equivalentes a números reales del intervalo de la unidad.

[…]

Postulamos que la función hash ha sido diseñada de tal manera que los valores hash se parecen mucho a un modelo uniforme de aleatoriedad, es decir, se supone que los bits de los valores hash son independientes y que cada probabilidad [0.5] se produce “.

Philippe Flajolet -  HyperLogLog: el análisis de un algoritmo de estimación de cardinalidad casi óptimo

Ahora, después de haber escogido una función hash adecuada, tenemos que abordar otra trampa: la varianza .

Volviendo a nuestro ejemplo, imagina que la primera persona con la que hablas en la conferencia te dice que su número termina con 00004 ¡Jackpot!

Es posible que haya ganado una apuesta contra Tommy, pero si utiliza este método en la vida real, es probable que los datos específicos en su conjunto influyan negativamente en la estimación.

No temas más, ya que este es un problema que HLL nació para resolver.

No muchos son conscientes de que Philippe Flajolet , uno de los cerebros detrás de HLL, ha estado involucrado en problemas de estimación de cardinalidad durante mucho tiempo. El tiempo suficiente para haber surgido con el algoritmo Flajolet-Martin en 1984 y (super-) LogLog en 2003 .

Estos algoritmos ya abordaron algunos de los problemas con los valores hash periféricos, dividiendo las mediciones en segmentos y (algo) promediando los valores en los segmentos.

Si se perdió aquí, permítame volver a nuestro ejemplo original.

En lugar de simplemente tomar los últimos 5 dígitos de un número de teléfono, tomamos 6 de ellos. Ahora, almacenamos la secuencia más larga de ceros a la izquierda junto con el primer dígito (el ‘cubo’).

Esto significa que nuestros datos se verán así:

Entrada: 
708942 -> en el 7 ° cubo, la secuencia más larga de 0 es 1 
518942 -> en el 5 ° cubo, la secuencia más larga de 0 es 0 
500973 -> en el 5 ° cubo, la secuencia más larga de 0 es ahora 2 
900000 -> en el noveno cubo, la secuencia más larga de 0 es 5 
900672 -> en el noveno cubo, la secuencia más larga de 0 se mantiene 5
Cucharones: 
0: 0 
1: 0 
2: 0 
3: 0 
4: 0 
5: 2 
6: 0 
7: 1 
8: 0 
9: 5
Salida: 
avg (cubetas) = ​​0.8

Como puede ver, si no estuviéramos utilizando cubos, en cambio, usaríamos 5 como la secuencia más larga de ceros. Esto tendría un impacto negativo en nuestra estimación.

Aunque simplifiqué la matemática detrás de los cubos (no es solo un promedio simple), puede ver totalmente cómo este enfoque tiene sentido.

Es interesante ver cómo Flajolet aborda la varianza a lo largo de sus trabajos:

“Si bien tenemos un estimado que ya es bastante bueno, es posible mejorar mucho. Durand y Flajolet hacen la observación de que los valores distantes hacen mucho para disminuir la precisión de la estimación; arrojando los valores más grandes antes de promediar, se puede mejorar la precisión.

Específicamente, al tirar el 30% de las cubetas con los valores más grandes y promediar solo el 70% de las cubetas con los valores más pequeños, se puede mejorar la precisión de 1,30 / sqrt (m) a solo 1,05 / sqrt (m). Esto significa que nuestro ejemplo anterior, con 640 bytes de estado y un error promedio de 4% ahora tiene un error promedio de aproximadamente 3.2%, sin necesidad de aumentar el espacio adicional.

Finalmente, la principal contribución de Flajolet et al en el documento HyperLogLog es usar un tipo diferente de promediado, tomando la media armónica en lugar de la media geométrica que acabamos de aplicar. Al hacer esto, pueden disminuir el error a 1.04 / sqrt (m), de nuevo sin aumentar el estado requerido “.

Nick Johnson  -  Mejora de la precisión: SuperLogLog y HyperLogLog

HLL en la naturaleza

Entonces, ¿dónde podemos encontrar la aplicación de HLL? Dos excelentes ejemplos a escala web son:

  • BigQuery , para contar de manera eficiente los únicos en una tabla ( APPROX_COUNT_DISTINCT())
  • Reddit , donde se usa para calcular la cantidad de vistas únicas que una publicación ha reunido

En particular, vea cómo HLL impacta las consultas en BigQuery:

SELECT COUNT (DISTINCT actor.login) exact_cnt 
FROM `githubarchive.year.2016` 
6,610,026 (4,1 s transcurridos, 3,39 GB procesados, 320,825,029 filas escaneadas)
SELECCIONE APPROX_COUNT_DISTINCT (actor.login) approx_cnt 
DESDE `githubarchive.year.2016` 
6,643,627 (transcurrieron 2.6s, procesaron 3.39 GB, escanearon 320.825.029 filas)

El segundo resultado es una aproximación (con una tasa de error de ~ 0.5%), pero toma una fracción del tiempo.

En resumen: ¡ HyperLogLog es increíble!

Ahora ya sabes lo que es y cuándo se puede usar, ¡así que sal y haz cosas increíbles con él!

Otras lecturas

Leave a Reply

Your email address will not be published. Required fields are marked *

Ir a la barra de herramientas