Algoritmo de Flajolet-Martin

El algoritmo Flajolet–Martin es un algoritmo para aproximar el número de elementos distintos en un flujo con un solo paso y un consumo de espacio logarítmico en el número máximo de elementos distintos posibles en el flujo (el problema de recuento distinto ). El algoritmo fue introducido por Philippe Flajolet y G. Nigel Martin en su artículo de 1984 "Algoritmos de conteo probabilístico para aplicaciones de bases de datos". ^[1] Posteriormente se ha perfeccionado en "LogLog counting of large cardinalities" de Marianne Durand y Philippe Flajolet , ^[2] y " HyperLogLog : The analysis of a near-optimal cardinality estimation algorithm" de Philippe Flajolet et al. ^[3]

En su artículo de 2010 "Un algoritmo óptimo para el problema de elementos distintos", ^[4] Daniel M. Kane, Jelani Nelson y David P. Woodruff presentan un algoritmo mejorado, que utiliza un espacio casi óptimo y tiene tiempos de actualización y generación de informes O (1) óptimos.

El algoritmo

Supongamos que se nos da una función hash que asigna la entrada a números enteros en el rango , y donde las salidas están distribuidas de manera suficientemente uniforme . Observe que el conjunto de números enteros de 0 a corresponde al conjunto de cadenas binarias de longitud . Para cualquier número entero no negativo , defina como el bit -ésimo en la representación binaria de , de modo que: ${\displaystyle \mathrm {hash} (x)}$ ${\displaystyle x}$ ${\displaystyle [0;2^{L}-1]}$ ${\displaystyle 2^{L}-1}$ ${\displaystyle L}$ ${\displaystyle y}$ ${\displaystyle \mathrm {bit} (y,k)}$ ${\displaystyle k}$ ${\displaystyle y}$

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)2^{k}.}$

Luego definimos una función que genera la posición del bit de conjunto menos significativo en la representación binaria de , y si no se puede encontrar dicho bit de conjunto ya que todos los bits son cero: ${\displaystyle \rho (y)}$ ${\displaystyle y}$ ${\displaystyle L}$

${\displaystyle \rho (y)={\begin{cases}\min\{k\geq 0\mid \mathrm {bit} (y,k)\neq 0\}&y>0\\L&y=0\end{cases}}}$

Tenga en cuenta que con la definición anterior estamos usando indexación 0 para las posiciones, comenzando desde el bit menos significativo. Por ejemplo, , ya que el bit menos significativo es un 1 (posición 0), y , ya que el bit menos significativo del conjunto está en la posición 3. En este punto, tenga en cuenta que bajo el supuesto de que la salida de nuestra función hash se distribuye uniformemente, entonces la probabilidad de observar una salida hash que termina con (un uno, seguido de ceros) es , ya que esto corresponde a obtener cara y luego cruz con una moneda justa. ${\displaystyle \rho (13)=\rho (1101_{2})=0}$ ${\displaystyle \rho (8)=\rho (1000_{2})=3}$ ${\displaystyle 2^{k}}$ ${\displaystyle k}$ ${\displaystyle 2^{-(k+1)}}$ ${\displaystyle k}$

Ahora bien, el algoritmo de Flajolet-Martin para estimar la cardinalidad de un multiconjunto es el siguiente: ${\displaystyle M}$

1. Inicializa un vector de bits BITMAP para que tenga la longitud necesaria y contenga todos los 0. ${\displaystyle L}$
2. Para cada elemento en : ${\displaystyle x}$ ${\displaystyle M}$
   1. Calcular el índice . ${\displaystyle i=\rho (\mathrm {hash} (x))}$
   2. Colocar . ${\displaystyle \mathrm {BITMAP} [i]=1}$
3. Sea el índice más pequeño tal que . ${\displaystyle R}$ ${\displaystyle i}$ ${\displaystyle \mathrm {BITMAP} [i]=0}$
4. Estimar la cardinalidad de como , donde . ${\displaystyle M}$ ${\displaystyle 2^{R}/\phi }$ ${\displaystyle \phi \approx 0.77351}$

La idea es que si es el número de elementos distintos en el multiconjunto , entonces se accede aproximadamente a , se accede aproximadamente a , y así sucesivamente. En consecuencia, si , entonces es casi seguro que es 0, y si , entonces es casi seguro que es 1. Si , entonces se puede esperar que sea 1 o 0. ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle \mathrm {BITMAP} [0]}$ ${\displaystyle n/2}$ ${\displaystyle \mathrm {BITMAP} [1]}$ ${\displaystyle n/4}$ ${\displaystyle i\gg \log _{2}n}$ ${\displaystyle \mathrm {BITMAP} [i]}$ ${\displaystyle i\ll \log _{2}n}$ ${\displaystyle \mathrm {BITMAP} [i]}$ ${\displaystyle i\approx \log _{2}n}$ ${\displaystyle \mathrm {BITMAP} [i]}$

El factor de corrección se obtiene mediante cálculos que se pueden encontrar en el artículo original. ${\displaystyle \phi \approx 0.77351}$

Mejorando la precisión

Un problema con el algoritmo Flajolet-Martin en la forma anterior es que los resultados varían significativamente. Una solución común ha sido ejecutar el algoritmo varias veces con diferentes funciones hash y combinar los resultados de las diferentes ejecuciones. Una idea es tomar la media de los resultados juntos de cada función hash, obteniendo una única estimación de la cardinalidad. El problema con esto es que el promedio es muy susceptible a los valores atípicos (que son probables aquí). Una idea diferente es usar la mediana , que es menos propensa a ser influenciada por valores atípicos. El problema con esto es que los resultados solo pueden tomar la forma , donde es un entero. Una solución común es combinar tanto la media como la mediana: crear funciones hash y dividirlas en grupos distintos (cada uno de tamaño ). Dentro de cada grupo, use la media para agregar los resultados y, finalmente, tome la mediana de las estimaciones del grupo como la estimación final. ^[5] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2^{R}/\phi }$ ${\displaystyle R}$ ${\displaystyle k\cdot l}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle k}$

El algoritmo HyperLogLog 2007 divide el multiconjunto en subconjuntos y estima sus cardinalidades, luego utiliza la media armónica para combinarlos en una estimación de la cardinalidad original. ^[3]

Véase también

• Algoritmo de transmisión
• HiperLogRegistro

Referencias

1. Flajolet, Philippe; Martin, G. Nigel (1985). "Algoritmos de conteo probabilísticos 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 . Consultado el 11 de diciembre de 2016 .
2. Durand, Marianne; Flajolet, Philippe (2003). "Recuento loglog de cardinalidades grandes" (PDF) . Algoritmos - ESA 2003. Apuntes de clase en informática. Vol. 2832. pág. 605. doi :10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Recuperado el 11 de diciembre de 2016 .
3. 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 : 127–146. CiteSeerX 10.1.1.76.4286 . Consultado el 11 de diciembre de 2016 . 
4. Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "Un algoritmo óptimo para el problema de los elementos distintos" (PDF) . Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos - PODS '10 . p. 41. doi :10.1145/1807085.1807094. ISBN . 978-1-4503-0033-9. S2CID  10006932 . Consultado el 11 de diciembre de 2016 .
5. Leskovec, Rajaraman, Ullman (2014). Minería de conjuntos de datos masivos (2.ª ed.). Cambridge University Press. pág. 144. Consultado el 30 de mayo de 2022 .{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

Fuentes adicionales

• Rajaraman, Anand; Ullman, Jeffrey David (27 de octubre de 2011). Minería de conjuntos de datos masivos. Cambridge University Press . p. 119. ISBN 9781139505345. Recuperado el 9 de noviembre de 2014 .