HyperLogLog | Un algoritmo para contarlos (aproximadamente) a todos
Tags: algorithms, computerscience, bigdata, spanish
Published: 2023-10-04 21:08:19

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.


![Una representación sencilla de varios conjuntos de datos y su correspondiente cardinalidad.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o3qokxpo05z104vldojn.png)


## 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:

 1. Creamos un **vector de bits** de longitud _L_, de forma que _2^L > n_, donde _n_ es la longitud del conjunto de datos.

 2. 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.

 3. 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.

 4. **Repetimos** el proceso con cada elemento del flujo de datos.

 5. **Obtenemos el índice del primer 0** en el vector de bits, al que llamaremos _R_.

 6. **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](https://algo.inria.fr/flajolet/Publications/FlMa85.pdf)

* [2] LogLog Counting of Large Cardinalities: [https://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf](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](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/](https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/)

* [5] HyperLogLog | Redis: [https://redis.io/docs/data-types/probabilistic/hyperloglogs/](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](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](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](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](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](https://arxiv.org/ftp/arxiv/papers/1612/1612.02284.pdf)

---

Este post fue publicado antes en [Medium](https://medium.com/p/2b1dacd14b33)