HiperLogRegistro

Algoritmo aproximado de conteo distinto

HyperLogLog es un algoritmo para el problema de recuento de elementos distintos , que aproxima el número de elementos distintos en un multiconjunto . ^[1] Calcular la cardinalidad exacta de los elementos distintos de un multiconjunto requiere una cantidad de memoria proporcional a la cardinalidad, lo que no es práctico para conjuntos de datos muy grandes. Los estimadores de cardinalidad probabilísticos, como el algoritmo HyperLogLog, utilizan significativamente menos memoria que esto, pero solo pueden aproximar la cardinalidad. El algoritmo HyperLogLog puede estimar cardinalidades de > 10 ⁹ con una precisión típica (error estándar) del 2%, utilizando 1,5 kB de memoria. ^[1] HyperLogLog es una extensión del algoritmo LogLog anterior, ^[2] que a su vez deriva del algoritmo Flajolet-Martin de 1984. ^[3]

Terminología

En el artículo original de Flajolet et al. ^[1] y en la literatura relacionada sobre el problema de recuento distinto , el término "cardinalidad" se utiliza para referirse al número de elementos distintos en un flujo de datos con elementos repetidos. Sin embargo, en la teoría de multiconjuntos, el término se refiere a la suma de multiplicidades de cada miembro de un multiconjunto. Este artículo opta por utilizar la definición de Flajolet para mantener la coherencia con las fuentes.

Algoritmo

La base del algoritmo HyperLogLog es la observación de que la cardinalidad de un multiconjunto de números aleatorios distribuidos uniformemente se puede estimar calculando el número máximo de ceros iniciales en la representación binaria de cada número del conjunto. Si el número máximo de ceros iniciales observado es  n , una estimación del número de elementos distintos en el conjunto es 2 ⁿ . ^[1]

En el algoritmo HyperLogLog, se aplica una función hash a cada elemento del multiconjunto original para obtener un multiconjunto de números aleatorios distribuidos uniformemente con la misma cardinalidad que el multiconjunto original. La cardinalidad de este conjunto distribuido aleatoriamente se puede estimar utilizando el algoritmo anterior.

La estimación simple de cardinalidad obtenida con el algoritmo anterior tiene la desventaja de una gran varianza . En el algoritmo HyperLogLog, la varianza se minimiza dividiendo el multiconjunto en numerosos subconjuntos, calculando la cantidad máxima de ceros iniciales en los números de cada uno de estos subconjuntos y utilizando una media armónica para combinar estas estimaciones para cada subconjunto en una estimación de la cardinalidad de todo el conjunto. ^[4]

Operaciones

El HyperLogLog tiene tres operaciones principales: add para añadir un nuevo elemento al conjunto, count para obtener la cardinalidad del conjunto y merge para obtener la unión de dos conjuntos. Algunas operaciones derivadas se pueden calcular utilizando el principio de inclusión-exclusión como la cardinalidad de la intersección o la cardinalidad de la diferencia entre dos HyperLogLogs combinando las operaciones merge y count.

Los datos del HyperLogLog se almacenan en una matriz M de m contadores (o "registros") que se inicializan a 0. La matriz M inicializada a partir de un multiconjunto S se denomina boceto HyperLogLog de S.

Agregar

La operación de suma consiste en calcular el hash de los datos de entrada v con una función hash h , obteniendo los primeros b bits (donde b es ), y sumándoles 1 para obtener la dirección del registro a modificar. Con los bits restantes se calcula que devuelve la posición del 1 más a la izquierda, donde la posición más a la izquierda es 1 (en otras palabras: número de ceros a la izquierda más 1). El nuevo valor del registro será el máximo entre el valor actual del registro y . ${\textstyle \log _{2}(m)}$ ${\textstyle \rho (w)}$ ${\textstyle \rho (w)}$

${\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}}$

Contar

El algoritmo de conteo consiste en calcular la media armónica de los m registros y utilizar una constante para derivar una estimación del conteo: ${\textstyle E}$

${\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}$

${\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}$

${\displaystyle E=\alpha _{m}m^{2}Z}$

La intuición es que, al ser n la cardinalidad desconocida de M , cada subconjunto tendrá elementos. Entonces debería estar cerca de . La media armónica de 2 para estas cantidades es que debería estar cerca de . Por lo tanto, debería ser n aproximadamente. ${\textstyle M_{j}}$ ${\textstyle n/m}$ ${\textstyle \max _{x\in M_{j}}\rho (x)}$ ${\textstyle \log _{2}(n/m)}$ ${\textstyle mZ}$ ${\textstyle n/m}$ ${\textstyle m^{2}Z}$

Finalmente, se introduce la constante para corregir un sesgo multiplicativo sistemático presente debido a las colisiones hash. ${\textstyle \alpha _{m}}$ ${\textstyle m^{2}Z}$

Consideraciones prácticas

La constante no es sencilla de calcular y se puede aproximar con la fórmula ^[1] ${\textstyle \alpha _{m}}$

${\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{\text{for }}m=16;\\0.697,&{\text{for }}m=32;\\0.709,&{\text{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{for }}m\geq 128.\end{cases}}}$

Sin embargo, la técnica HyperLogLog está sesgada para cardinalidades pequeñas por debajo de un umbral de . El artículo original propone utilizar un algoritmo diferente para cardinalidades pequeñas conocido como conteo lineal. ^[5] En el caso en que la estimación proporcionada anteriormente sea menor que el umbral , se puede utilizar el cálculo alternativo: ${\textstyle {\frac {5}{2}}m}$ ${\textstyle E<{\frac {5}{2}}m}$

1. Sea el número de registros igual a 0. ${\textstyle V}$
2. Si es así , utilice el estimador HyperLogLog estándar anterior. ${\textstyle V=0}$ ${\textstyle E}$
3. De lo contrario, utilice el conteo lineal: ${\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}$

Además, para cardinalidades muy grandes que se acercan al límite del tamaño de los registros ( para registros de 32 bits), la cardinalidad se puede estimar con: ${\textstyle E>{\frac {2^{32}}{30}}}$

${\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)}$

Con las correcciones anteriores para los límites inferior y superior, el error se puede estimar como . ${\textstyle \sigma =1.04/{\sqrt {m}}}$

Unir

La operación de fusión de dos HLL ( ) consiste en obtener el máximo para cada par de registros ${\textstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}$ ${\textstyle j:1..m}$

${\displaystyle {\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}$

Complejidad

Para analizar la complejidad se utiliza el modelo de streaming de datos ^[6] , que analiza el espacio necesario para obtener una aproximación con una probabilidad de éxito fija . El error relativo de HLL es y necesita espacio, donde n es la cardinalidad establecida y m es el número de registros (normalmente de tamaño inferior a un byte). ${\displaystyle (\epsilon ,\delta )}$ ${\displaystyle 1\pm \epsilon }$ ${\displaystyle 1-\delta }$ ${\displaystyle 1.04/{\sqrt {m}}}$ ${\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}$

La operación de suma depende del tamaño de la salida de la función hash. Como este tamaño es fijo, podemos considerar que el tiempo de ejecución de la operación de suma es . ${\displaystyle O(1)}$

Las operaciones de conteo y fusión dependen del número de registros m y tienen un costo teórico de . En algunas implementaciones ( Redis ) ^[7] el número de registros es fijo y el costo se considera en la documentación. ${\displaystyle O(m)}$ ${\displaystyle O(1)}$

HLL++

El algoritmo HyperLogLog++ propone varias mejoras en el algoritmo HyperLogLog para reducir los requisitos de memoria y aumentar la precisión en algunos rangos de cardinalidades: ^[6]

• Se utiliza una función hash de 64 bits en lugar de los 32 bits utilizados en el artículo original. Esto reduce las colisiones de hash para cardinalidades grandes, lo que permite eliminar la corrección de rango grande.
• Se detecta cierto sesgo en las cardinalidades pequeñas al cambiar del conteo lineal al conteo HLL. Se propone una corrección empírica del sesgo para mitigar el problema.
• Se propone una representación dispersa de los registros para reducir los requisitos de memoria para cardinalidades pequeñas, que luego pueden transformarse en una representación densa si la cardinalidad crece.

Transmisión de HLL

Cuando los datos llegan en un solo flujo, el estimador de probabilidad inversa histórica o martingala ^{[8] [9]} mejora significativamente la precisión del esquema HLL y utiliza un 36 % menos de memoria para alcanzar un nivel de error determinado. Este estimador es demostrablemente óptimo para cualquier esquema de recuento aproximado distinto e insensible a los duplicados en un solo flujo.

El escenario de flujo único también genera variantes en la construcción del boceto HLL. HLL-TailCut+ utiliza un 45 % menos de memoria que el boceto HLL original, pero a costa de depender del orden de inserción de datos y no poder fusionar bocetos. ^[10]

Lectura adicional

• "Nuevos algoritmos de estimación de cardinalidad para bocetos HyperLogLog" (PDF) . Consultado el 29 de octubre de 2016 .

Referencias

1. Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: El análisis de un algoritmo de estimación de cardinalidad casi óptimo" (PDF) . Actas de Matemáticas Discretas y Ciencias de la Computación Teórica . AH . Nancy, Francia : 137–156. CiteSeerX 10.1.1.76.4286 . Consultado el 11 de diciembre de 2016 . 
2. Durand, M.; Flajolet, P. (2003). "LogLog counting of large cardinalities" (Recuento log-log de cardinalidades grandes) . (PDF) . En G. Di Battista y U. Zwick (ed.). Lecture Notes in Computer Science . Simposio europeo anual sobre algoritmos (ESA03). Vol. 2832. Springer. págs. 605–617.
3. Flajolet, Philippe; Martin, G. Nigel (1985). "Algoritmos de conteo probabilísticos para aplicaciones de bases de datos" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 31 (2): 182–209. doi :10.1016/0022-0000(85)90041-8.
4. S Heule; M Nunkesser; A Hall (2013). "HyperLogLog en la práctica: ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación" (PDF) . sección 4.
5. Whang, Kyu-Young; Vander-Zanden, Brad T; Taylor, Howard M (1990). "Un algoritmo de conteo probabilístico de tiempo lineal para aplicaciones de bases de datos". ACM Transactions on Database Systems . 15 (2): 208–229. doi : 10.1145/78922.78925 . S2CID  2939101.
6. "HyperLogLog en la práctica: ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación" . Consultado el 19 de abril de 2014 .
7. "PFCOUNT – Redis".
8. Cohen, E. (marzo de 2015). "Bocetos de todas las distancias, revisados: estimadores HIP para análisis de gráficos masivos". IEEE Transactions on Knowledge and Data Engineering . 27 (9): 2320–2334. arXiv : 1306.3284 . doi :10.1109/TKDE.2015.2411606.
9. Ting, D. (agosto de 2014). "Recuento aproximado en tiempo real de elementos distintos". Actas de la 20.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 442–451. doi :10.1145/2623330.2623669. ISBN 978-1-4503-2956-9. Número de identificación del sujeto  13179875.
10. Xiao, Q.; Zhou, Y.; Chen, S. (mayo de 2017). "Mejor con menos bits: mejora del rendimiento de la estimación de cardinalidad de grandes flujos de datos". IEEE INFOCOM 2017 - Conferencia IEEE sobre comunicaciones informáticas . págs. 1–9. doi :10.1109/INFOCOM.2017.8057088. ISBN 978-1-5090-5336-0. Número de identificación del sujeto  27159273.