Algoritmo de conteo aproximado

El algoritmo de conteo aproximado permite contar un gran número de eventos utilizando una pequeña cantidad de memoria. Inventado en 1977 por Robert Morris de Bell Labs , utiliza técnicas probabilísticas para incrementar el contador . Fue analizado completamente a principios de la década de 1980 por Philippe Flajolet de INRIA Rocquencourt, quien acuñó el nombre de conteo aproximado y contribuyó en gran medida a su reconocimiento en la comunidad de investigación. Al centrarse en una alta calidad de aproximación y una baja probabilidad de fallo, Nelson y Yu demostraron que una modificación muy leve del Contador de Morris es asintóticamente óptima entre todos los algoritmos para el problema. ^{[ 1 ]} El algoritmo se considera uno de los precursores de los algoritmos de flujo , y el problema más general de determinar los momentos de frecuencia de un flujo de datos ha sido central en el campo.

Teoría de funcionamiento

Utilizando el algoritmo de Morris, el contador representa una " estimación del orden de magnitud " del recuento real. La aproximación es matemáticamente insesgada .

Para incrementar el contador, se utiliza un evento pseudoaleatorio , de modo que el incremento es un evento probabilístico. Para ahorrar espacio, solo se conserva el exponente. Por ejemplo, en base 2, el contador puede estimar el conteo como 1, 2, 4, 8, 16, 32 y todas las potencias de dos . El requisito de memoria es simplemente almacenar el exponente .

Por ejemplo, para incrementar el contador de 4 a 8, se generaría un número pseudoaleatorio tal que la probabilidad de que el contador aumente sea de 0,25. En caso contrario, el contador permanece en 4.

La siguiente tabla ilustra algunos de los valores potenciales del contador:

Si el contador tiene el valor de 101, que equivale a un exponente de 5 (el equivalente decimal de 101), entonces el recuento estimado es $2^{5}$ , o 32. Hay una probabilidad bastante baja de que el recuento real de eventos de incremento fuera 5 ( ${\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}$ ). Es probable que el número real de eventos de incremento sea "alrededor de 32", pero podría ser arbitrariamente alto (con probabilidades decrecientes para recuentos reales superiores a 39).

Selección de valores de contador

Si bien usar potencias de 2 como valores de contador es eficiente en cuanto a memoria, los valores arbitrarios tienden a generar un rango de error dinámico, y los valores más pequeños tendrán una mayor tasa de error que los valores más grandes. Otros métodos para seleccionar valores de contador consideran parámetros como la disponibilidad de memoria, la tasa de error deseada o el rango de conteo para proporcionar un conjunto óptimo de valores. ^{[ 2 ]}

Sin embargo, cuando varios contadores comparten los mismos valores, estos se optimizan según el contador con el mayor rango de conteo, lo que produce una precisión subóptima para los contadores más pequeños. Esto se mitiga manteniendo intervalos de estimación de contadores independientes ^{[ 3 ]} , que restringen el efecto de un contador mayor a los demás contadores del intervalo.

Algoritmo

El algoritmo se puede implementar manualmente. Para incrementar el contador, lanza una moneda un número de veces equivalente al valor actual del contador. Si sale cara en cada lanzamiento, incrementa el contador. De lo contrario, no lo incrementes.

Esto se puede lograr fácilmente en una computadora. $c$ sea el valor actual del contador. Generando $c$ bits pseudoaleatorios y usando el AND lógico de todos esos bits y sumando el resultado al contador. Como el resultado fue cero si alguno de esos bits pseudoaleatorios es cero, logrando una probabilidad de incremento de $2^{-c}$ Este procedimiento se ejecuta cada vez que se solicita incrementar el contador.

Aplicaciones

El algoritmo resulta útil para analizar grandes flujos de datos en busca de patrones. Esto es especialmente útil en aplicaciones de compresión de datos , reconocimiento de imágenes y sonidos, y otras aplicaciones de inteligencia artificial .

Véase también

Registro de HyperLog

Referencias

↑ Nelson, Jelani; Yu, Huacheng (2020). "Límites óptimos para el conteo aproximado". arXiv : 2010.02116 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
↑ Tsidon, Erez, Iddo Hanniel e Isaac Keslassy. «Los estimadores también necesitan valores compartidos para crecer juntos». INFOCOM, Actas de 2012 IEEE. IEEE, 2012.
↑ Einziger, G.; Fellman, B.; Kassner, Y. (abril de 2015). "Cubos de estimación de contador independientes". Conferencia IEEE de Comunicaciones Informáticas (INFOCOM) de 2015. págs. 2560–2568 . doi : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0. S2CID 15673730 .

Fuentes

Morris, R. Conteo de grandes cantidades de eventos en registros pequeños . Communications of the ACM 21, 10 (1978), 840–842
Flajolet, P. Conteo aproximado: un análisis detallado . BIT 25, (1985), 113–134
Fouchs, M., Lee, CK., Prodinger, H., Conteo aproximado mediante el método de Poisson-Laplace-Mellin

[ny2020-1] Nelson, Jelani; Yu, Huacheng (2020). "Límites óptimos para el conteo aproximado". arXiv : 2010.02116 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )

[2] Tsidon, Erez, Iddo Hanniel e Isaac Keslassy. «Los estimadores también necesitan valores compartidos para crecer juntos». INFOCOM, Actas de 2012 IEEE. IEEE, 2012.

[3] Einziger, G.; Fellman, B.; Kassner, Y. (abril de 2015). "Cubos de estimación de contador independientes". Conferencia IEEE de Comunicaciones Informáticas (INFOCOM) de 2015. págs. 2560–2568 . doi : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0. S2CID 15673730 .

[ 1 ]

[ 2 ]

[ 3 ]