Imagina que trabajas en el equipo de ingeniería de una aplicación con un gran volumen de usuarios y tienes que obtener métricas de forma rápida sobre cuántos usuarios únicos tienes en un día. Veamos cómo resolver este caso de uso.
La potencia que proporciona un marco matemático y el análisis y diseño de algoritmos a la programación permite resolver problemas de todo tipo, como pudiera ser la estimación de la cardinalidad.
El problema de estimación de la cardinalidad trata de averiguar el número de elementos distintos en un conjunto o flujo de datos donde puedan existir elementos repetidos.
El problema, desde la base
Podemos ejemplificar este problema considerando que tenemos un listado con todas las palabras de un libro, y queremos saber cuántas palabras distintas hay en él.
Una solución, intuitiva a primera vista, sería inicializar una estructura de datos vacía, iterar sobre el conjunto de palabras que tenemos e ir añadiendo a nuestra estructura nueva las palabras si no se encuentran ya en dicha estructura. Finalmente, la longitud de este nuevo conjunto será el número de elementos únicos del primer listado.
Esta solución tiene un problema, que radica en la escalabilidad. Si en lugar de disponer un solo libro tuviéramos que realizar esta operación sobre la totalidad de libros de la Biblioteca Británica (más de 170 millones de ejemplares), este algoritmo requeriría una gran cantidad de memoria para almacenar la nueva estructura. En términos de complejidad de memoria, necesitamos O(n), ya que incrementaría de forma lineal mientras más datos de entrada tenemos.
Una primera aproximación: Flajolet-Martin
En 1984, Philippe Flajolet y G. Nigel Martin proponen una alternativa en su artículo “Probabilistic Counting Algorithms for Data Base Applications [1]”. Esta solución, conocida como el algoritmo Flajolet-Martin, funciona, en resumidas cuentas, de la siguiente forma:
Creamos un vector de bits de longitud L, de forma que 2^L > n, donde n es la longitud del conjunto de datos.
Una función hash transforma cada elemento del flujo de datos en un número binario uniforme. La función de hash es (ax + b) mod L; donde a y b son números enteros, x el elemento de entrada del flujo de datos, y L es el límite de rango de la función hash que definido en el punto anterior.
Se cuenta el número de ceros consecutivos, al que llamaremos k, al final del número binario producido. En nuestro vector de bits establecemos el bit k-ésimo a 1.
Repetimos el proceso con cada elemento del flujo de datos.
Obtenemos el índice del primer 0 en el vector de bits, al que llamaremos R.
Estimamos la cardinalidad con la fórmula 2^R / Φ. El símbolo Φ representa un factor de corrección con valor Φ = 0.77351…
El algoritmo Flajolet-Martin se ejecuta con varias funciones hash diferentes y se calcula la media de los resultados aproximados, ya que una sola ejecución podría inducir errores si los datos no están compensados al ser hasheados.
La mejora de rendimiento de esta solución es evidente, ya que su complejidad en memoria es de O(log(n)), en lugar de O(n) como la primera sugerencia.
LogLog entra en escena
Casi 20 años después, en el Simposio Europeo de Algoritmos de 2003, Flajolet y Marianne Durand presentan “Loglog Counting of Large Cardinalities [2]” como mejora a este algoritmo.
LogLog añade el concepto de “bucketing”, por el que se divide el número binario producido por la función de hash en varios grupos de bits. De cada grupo, se toma el número de ceros consecutivos al final y se calcula la mediana. Para obtener la cardinalidad estimada de todo el conjunto de datos, se realiza la media de todas las medianas. Esto mejora la complejidad en memoria a O(log log n), de ahí el nombre del algoritmo.
Esta revisión presenta mejoras al evitar tener que ser ejecutada con distintas funciones de hash para reducir márgenes de error. En el artículo donde se presenta LogLog, una ejecución del algoritmo estimó que, teniendo como datos de entrada todas las palabras de todas las obras de Shakespeare, se estimaban alrededor de 30.897 palabras únicas. El dato real es de 28.239 palabras distintas, dando un error relativo del 9.4%.
En el mismo artículo se detalla la implementación de SuperLogLog como una optimización sobre LogLog, que además de contar los ceros consecutivos, tiene en cuenta los siguientes bits. Mediante esta estimación mejorada, obtiene resultados más precisos en conjuntos pequeños, donde más flojea LogLog.
Un algoritmo casi óptimo: HyperLogLog
No es hasta pocos años después, ya en 2007, cuando Flajolet y otros investigadores evolucionan el concepto y describen “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [3]”.
HyperLogLog (HLL) mejora a todo lo anterior, aplicando complejos mecanismos matemáticos y estadísticos que le permiten contar con un error relativo del 2% para cardinalidades superiores a 10⁹. Es considerado casi óptimo, y fue una auténtica revolución cuando se presentó.
Casos de uso
A día de hoy, ¿hay empresas y servicios que utilicen HLL? Veamos varios ejemplos:
Trino (anteriormente conocido como Presto), un motor de consulta SQL orientado a Big Data desarrollado originalmente por Facebook [4].
Redis, el popular motor de base de datos en memoria, implementa HLL con un error estándar de 0.81% [5].
Amazon Redshift, el servicio de Data Warehouse en de Amazon Web Services [6].
Otros algoritmos de cardinalidad y conclusiones
LogLog ha servido como inspiración para otros algoritmos de estimaciones de cardinalidad. En 2006 se presenta B-LogLog-EC [7], orientado al conteo de tráfico IP. Una revisión de HLL llamada HyperLogLog++ (HLL++) fue presentada por Google en 2013 [8], supliendo algunos de los puntos flacos que tenía HLL, y que en la actualidad es utilizado por Google Analytics 4 [9]. No es hasta 2016 que LogLog-Beta [10] aparece en un artículo en arXiv, cuya implementación optimizaría aún más los resultados producidos por HLL y HLL++.
En un entorno en el que se generan grandes cantidades de datos por segundo, este tipo de algoritmos son muy útiles para obtener métricas actualizadas en tiempo real como puedan ser los visitantes diarios a una página web, para estimar cuántas palabras únicas hay en la literatura mundial o para detectar anomalías en un dispositivo IoT que emita señales constantemente.
Referencias:
[1] Probabilistic Counting Algorithms for Data Base Applications: https://algo.inria.fr/flajolet/Publications/FlMa85.pdf
[2] LogLog Counting of Large Cardinalities: https://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf
[3] HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm: https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[4] HyperLogLog in Presto: A significantly faster way to handle cardinality estimation: https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/
[5] HyperLogLog | Redis: https://redis.io/docs/data-types/probabilistic/hyperloglogs/
[6] Using HyperLogLog sketches in Amazon Redshift: https://docs.aws.amazon.com/en_gb/redshift/latest/dg/hyperloglog-overview.html
[7] LOGLOG counting for the estimation of IP traffic: https://dmtcs.episciences.org/3503/pdf
[8] HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm: https://static.googleusercontent.com/media/research.google.com/es//pubs/archive/40671.pdf
[9] Unique count approximation in Google Analytics: https://developers.google.com/analytics/blog/2022/hll?hl=en
[10] LogLog-Beta and More: A New Algorithm for Cardinality Estimation Based on LogLog Counting: https://arxiv.org/ftp/arxiv/papers/1612/1612.02284.pdf
Este post fue publicado antes en Medium
Top comments (0)