HyperLogLog

Parte de una serie sobre
Estructuras de datos probabilísticas
Filtro de floración Esbozo de conteo mínimo Filtro de cociente Lista de omisión
Árboles aleatorios
Árbol binario aleatorio Treap Árbol aleatorio de exploración rápida
Relacionados
Algoritmo aleatorizado HyperLogLog
v t mi

HyperLogLog es un algoritmo para el problema de conteo distinto , que se aproxima al número de elementos distintos en un multiset . ^{[1] El} cálculo de la cardinalidad exacta de un conjunto múltiple requiere una cantidad de memoria proporcional a la cardinalidad, lo que no es práctico para conjuntos de datos muy grandes. Los estimadores probabilísticos de cardinalidad, como el algoritmo HyperLogLog, usan significativamente menos memoria que esta, a costa de obtener solo una aproximación de 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] derivado 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 conteo distinto , el término "cardinalidad" se usa para referirse al número de elementos distintos en un flujo de datos con elementos repetidos. Sin embargo, en la teoría de conjuntos múltiples, el término se refiere a la suma de multiplicidades de cada miembro de un conjunto múltiple. Este artículo elige utilizar la definición de Flajolet para mantener la coherencia con las fuentes.

Algoritmo

Esta sección incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar esta sección introduciendo citas más precisas. ( Marzo de 2014 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

La base del algoritmo HyperLogLog es la observación de que la cardinalidad de un conjunto múltiple 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 a la izquierda 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 multiset original para obtener un multiset de números aleatorios distribuidos uniformemente con la misma cardinalidad que el multiset original. La cardinalidad de este conjunto distribuido aleatoriamente se puede estimar utilizando el algoritmo anterior.

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

Operaciones

El HyperLogLog tiene tres operaciones principales: agregar para agregar un nuevo elemento al conjunto, contar para obtener la cardinalidad del conjunto y fusionar 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 que combinan las operaciones de combinación y recuento.

Los datos del HyperLogLog se almacenan en una matriz M de contadores llamados registros con tamaño m que se establecen en 0 en su estado inicial.

Agregar

La operación de suma consiste en calcular el hash de los datos de entrada v con una función hash h , obtener los primeros b bits (donde b es ) y agregarles 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. 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 usar 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 n siendo la cardinalidad desconocida de M , cada subconjunto tendrá elementos. Entonces debería estar cerca de . La media armónica de 2 a estas cantidades es la que debería estar cerca . Por lo tanto, debe 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 colisiones hash.${\textstyle \alpha _{m}}$${\textstyle m^{2}Z}$

Consideraciones prácticas

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

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

Sin embargo, la técnica HyperLogLog está sesgada por pequeñas cardinalidades por debajo de un umbral de . El artículo original propone el uso de un algoritmo diferente para pequeñas cardinalidades conocido como conteo lineal. ^[5] En el caso de 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 recuento de registros igual a 0.${\textstyle V}$
2. Si , utilice el estimador estándar HyperLogLog anterior.${\textstyle V=0}$${\textstyle E}$
3. De lo contrario, use 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 superior e inferior, el error se puede estimar como .${\textstyle \sigma =1.04/{\sqrt {m}}}$

Fusionar

La operación de fusión para 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 flujo 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 (generalmente menos de un tamaño de 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 adición 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 adición es .${\displaystyle O(1)}$

Las operaciones de recuento y fusión dependen del número de registros my 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 la función hash de 64 bits en lugar de los 32 bits utilizados en el documento original. Esto reduce las colisiones hash para cardinalidades grandes, lo que permite eliminar la corrección de rango grande.
• Se encuentra cierto sesgo para cardinalidades pequeñas cuando se cambia del conteo lineal al conteo HLL. Se propone una corrección del sesgo empírico para mitigar el problema.
• Se propone una representación dispersa de los registros para reducir los requisitos de memoria para pequeñas cardinalidades, 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 boceto HLL y usa un 36% menos de memoria para lograr un nivel de error dado. Este estimador es probablemente óptimo para cualquier boceto de conteo distinto aproximado insensible duplicado en un solo flujo.

El escenario de flujo único también da lugar a variantes en la construcción del boceto HLL. HLL-TailCut + usa 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

• "Estructuras de datos probabilísticas para analítica web y minería de datos" . highscalable.wordpress.com. Mayo de 2012 . Consultado el 19 de abril de 2014 .
• "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 e Informática Teórica . Nancy, Francia . AH : 127-146. CiteSeerX 10.1.1.76.4286 . Consultado el 11 de diciembre de 2016 .  
2. Durand, M .; Flajolet, P. (2003). "Conteo LogLog de cardinalidades grandes". (PDF) . En G. Di Battista y U. Zwick (ed.). Apuntes de conferencias en Ciencias de la Computación . Simposio europeo anual sobre algoritmos (ESA03). 2832 . Saltador. págs. 605–617.
3. Flajolet, Philippe; Martin, G. Nigel (1985). "Algoritmos de conteo probabilístico para aplicaciones de bases de datos" (PDF) . Revista de Ciencias de la Computación y 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) . seg 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". Transacciones ACM en sistemas de bases de datos . 15 (2): 208–229. doi : 10.1145 / 78922.78925 .
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, revisitados: estimadores HIP para análisis de gráficos masivos". Transacciones IEEE sobre conocimiento e ingeniería de datos . 27 (9): 2320–2334. arXiv : 1306.3284 . doi : 10.1109 / TKDE.2015.2411606 .
9. Ting, D. (agosto de 2014). "Recuento aproximado transmitido de distintos elementos: superando los métodos óptimos por lotes" . Actas de la 20ª Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos (KDD '14) : 442–451. doi : 10.1145 / 2623330.2623669 . ISBN 9781450329569.
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 : 1–9. doi : 10.1109 / INFOCOM.2017.8057088 . ISBN 978-1-5090-5336-0.