Hispanopedia Wiki
Articulo de referencia

Registro de HyperLog

HyperLogLog es un algoritmo para el problema de conteo de elementos distintos , que aproxima el número de elementos distintos en un multiconjunto . [ 1 ] Calcular la cardinalida...

Hispanopedia WikiContenido en espanolLectura gratuita

HyperLogLog es un algoritmo para el problema de conteo 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 cual es impracticable para conjuntos de datos muy grandes. Los estimadores de cardinalidad probabilísticos, como el algoritmo HyperLogLog, utilizan mucha menos memoria, pero solo pueden aproximar la cardinalidad. El algoritmo HyperLogLog puede estimar cardinalidades > 10 9 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 conteo de elementos distintos , 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 las 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 puede estimarse 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 para el número de elementos distintos en el conjunto es 2n . [ 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 descrito anteriormente.

La estimación simple de cardinalidad obtenida mediante 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 el número máximo de ceros iniciales en los números de cada uno de estos subconjuntos y utilizando una media armónica para combinar estas estimaciones de cada subconjunto en una estimación de la cardinalidad del conjunto completo. [ 4 ]

Operaciones

El HyperLogLog tiene tres operaciones principales: agregar para añadir 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 HyperLogLog combinando las operaciones de fusión y conteo.

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 esregistro2⁡(metro){\textstyle \log _{2}(m)}), y sumándoles 1 para obtener la dirección del registro a modificar (suponiendo una indexación basada en 1). Con los bits restantes como w , calculeρ(w){\textstyle \rho (w)}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 iniciales más 1). El nuevo valor del registro será el máximo entre el valor actual del registro yρ(w){\textstyle \rho (w)}.

incógnita:=h(v)j:=1+⟨incógnita1incógnita2...incógnitab⟩2w:=incógnitab+1incógnitab+2...METRO[j]:=máximo(METRO[j],ρ(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 obtener una estimación.mi{\textstyle E}del recuento:

Z=(∑j=1metro2−METRO[j])−1{\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}
αmetro=(metro∫0∞(registro2⁡(2+tú1+tú))metrodtú)−1{\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}
mi=αmetrometro2Z{\displaystyle E=\alpha _ {m}m^{2}Z}

La intuición es que n es la cardinalidad desconocida de M , cada subconjuntoMETROj{\textstyle M_{j}}tendránorte/metro{\textstyle n/m}elementos. Entonces máximoincógnita∈METROjρ(incógnita){\textstyle \max _{x\in M_{j}}\rho (x)}debería estar cerca deregistro2⁡(norte/metro){\textstyle \log _{2}(n/m)}. La media armónica de 2 a estas cantidades esmetroZ{\textstyle mZ}que debería estar cercanorte/metro{\textstyle n/m}. De este modo,metro2Z{\textstyle m^{2}Z}debería ser n aproximadamente.

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

Consideraciones prácticas

La constanteαmetro{\textstyle \alpha _{m}}no es sencillo de calcular y se puede aproximar con la fórmula [ 1 ].

αmetro≈{0,673,para metro=16;0,697,para metro=32;0,709,para metro=64;0,72131+1.079/metro,para metro≥128.{\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{\text{para }}m=16;\\0.697,&{\text{para }}m=32;\\0.709,&{\text{para }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{para }}m\geq 128.\end{cases}}}

Sin embargo, la técnica HyperLogLog está sesgada hacia cardinalidades pequeñas por debajo de un umbral de52metro{\textstyle {\frac {5}{2}}m}El artículo original propone utilizar un algoritmo diferente para cardinalidades pequeñas conocido como Conteo Lineal. [ 5 ] En el caso de que la estimación proporcionada anteriormente sea menor que el umbralmi<52metro{\estilo de texto E<{\frac {5}{2}}m}Se puede utilizar el cálculo alternativo:

  1. DejarV{\textstyle V}sea ​​el recuento de registros igual a 0.
  2. SiV=0{\textstyle V=0}, utilice el estimador HyperLogLog estándarmi{\textstyle E}arriba.
  3. De lo contrario, utilice el conteo lineal:mi⋆=metroregistro⁡(metroV){\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}

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

mi⋆=−232registro⁡(1−mi232){\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σ=1.04/metro{\textstyle \sigma =1.04/{\sqrt {m}}}.

Unir

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

hllunión[j]=máximo(hll1[j],hll2[j]){\displaystyle {\mathit {hll}}_{\text{unión}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}

Complejidad

Para analizar la complejidad, el flujo de datos(ϵ,δ){\displaystyle (\épsilon,\delta)}Se utiliza el modelo [ 6 ] , que analiza el espacio necesario para obtener un1±ϵ{\displaystyle 1\pm \epsilon }aproximación con una probabilidad de éxito fija1−δ{\displaystyle 1-\delta }. El error relativo de HLL es1.04/metro{\displaystyle 1.04/{\sqrt {m}}}y lo necesitaO(ϵ−2registro⁡registro⁡norte+registro⁡norte){\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}espacio, donde n es la cardinalidad del conjunto y m es el número de registros (normalmente de menos de un byte).

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 esO(1){\displaystyle O(1)}.

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

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 ]

  • En lugar de la función hash de 32 bits empleada en el artículo original, se utiliza una función hash de 64 bits. Esto reduce las colisiones de hash para cardinalidades grandes, lo que permite eliminar la corrección de rango amplio.
  • Se observa cierto sesgo para 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 posteriormente se puede transformar en una representación densa si la cardinalidad aumenta.

Transmisión de HLL

Cuando los datos llegan en un único flujo, el estimador de probabilidad inversa histórica o de 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 conteo distinto aproximado insensible a duplicados en un único 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 ]

Lecturas adicionales

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

Referencias

  1. 1 2 3 4 5 Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: Análisis de un algoritmo de estimación de cardinalidad casi óptimo" (PDF) . Actas de Matemáticas Discretas e Informática 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." (PDF) . En G. Di Battista y U. Zwick (eds.). Lecture Notes in Computer Science . Simposio Europeo Anual sobre Algoritmos (ESA03). Vol. 2832. Springer. pp. 605–617 .  
  3. ↑ Flajolet, Philippe; Martin, G. Nigel (1985). "Algoritmos de conteo probabilístico para aplicaciones de bases de datos" (PDF) . Journal of Computer and System Sciences . 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) . sec. 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. 1 2 "HyperLogLog en la práctica: ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación" . Recuperado el 19 de abril de 2014 .
  7. ↑ "PFCOUNT – Redis" .
  8. ↑ Cohen, E. (marzo de 2015). "Esbozos de todas las distancias, revisados: estimadores HIP para el análisis de grafos 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. S2CID 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. S2CID 27159273 . 
Lecturas relacionadas
6 articulos
{\displaystyle 120=2^{3}3^{1}5^{1},}Conjunto múltipleEn matemáticas , un multiconjunto (o bag , o mset ) es una modificación del concepto de conjunto que, a diferencia de un conjunto, [1] permite múlt...CardinalidadCardinalidadEn matemáticas , la cardinalidad describe una relación entre conjuntos que compara su tamaño relativo. [1] Por ejemplo, los conjuntos y tienen el m...Función hashFunción hashUna función hash es cualquier función que se puede utilizar para mapear datos de tamaño arbitrario a valores de tamaño fijo, aunque hay algunas fun...DiferenciaDiferenciaEn teoría de probabilidad y estadística , la varianza es el valor esperado de la desviación al cuadrado de la media de una variable aleatoria . La ...{\displaystyle \left({\frac {1^{-1}+4^{-1}+4^{-1}}{3}}\right)^{-1}={\frac {3}{{\frac {1}{1}}+{\frac {1}{4}}+{\frac {1}{4}}}}={\frac {3}{1.5}}=2\,.}Media armónicaEn matemáticas , la media armónica es uno de los diversos tipos de promedio y, en particular, una de las medias pitagóricas . A veces es apropiada ...Principio de inclusión-exclusiónPrincipio de inclusión-exclusiónEn combinatoria , una rama de las matemáticas , el principio de inclusión-exclusión es una técnica de conteo que generaliza el método familiar de o...