El algoritmo de recuento aproximado permite el recuento de una gran cantidad de eventos utilizando una pequeña cantidad de memoria. Inventado en 1977 por Robert Morris (criptógrafo) de Bell Labs , utiliza técnicas probabilísticas para incrementar el contador . Philippe Flajolet de INRIA Rocquencourt lo analizó completamente a principios de la década de 1980 , quien acuñó el nombre de conteo aproximado y contribuyó en gran medida a su reconocimiento entre la comunidad de investigadores. Cuando se enfoca en una alta calidad de aproximación y una baja probabilidad de falla, Nelsony Yu demostró 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 transmisión , y el problema más general de determinar los momentos de frecuencia de un flujo de datos ha sido fundamental para el campo.
Teoría de operación
Usando el algoritmo de Morris, el contador representa una " estimación de 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 la base 2, el contador puede estimar que la cuenta es 1, 2, 4, 8, 16, 32 y todas las potencias de dos . El requisito de memoria es simplemente mantener el exponente .
Como ejemplo, para incrementar de 4 a 8, se generaría un número pseudoaleatorio tal que una probabilidad de .25 genera un cambio positivo en el contador. De lo contrario, el contador permanece en 4.
La siguiente tabla ilustra algunos de los valores potenciales del contador:
Valor binario almacenado del contador | Aproximación | Rango de valores posibles para el recuento real | Expectativa (n suficientemente grande, distribución uniforme) |
---|---|---|---|
0 | 1 | 0, o valor inicial | 0 |
1 | 2 | 1 o más | 2 |
10 | 4 | 2 o más | 6 |
11 | 8 | 3 o más | 14 |
100 | dieciséis | 4 o más | 30 |
101 | 32 | 5 o más | 62 |
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. Existe una probabilidad bastante baja de que el recuento real de eventos de incremento fuera 5 (). Es probable que el recuento real de eventos de incremento sea "alrededor de 32", pero podría ser arbitrariamente alto (con probabilidades decrecientes de recuentos reales superiores a 39).
Seleccionar valores de contador
Si bien el uso de potencias de 2 como valores de contador es eficiente en la memoria, los valores arbitrarios tienden a crear un rango de error dinámico, y los valores más pequeños tendrán una tasa de error mayor 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, los valores se optimizan de acuerdo con el contador con el rango de conteo más grande y producen una precisión subóptima para contadores más pequeños. La mitigación se logra mediante el mantenimiento de depósitos de estimación de contador independiente, [3] que restringen el efecto de un contador más grande a los otros contadores en el depósito.
Algoritmo
Al incrementar el contador, "lanza una moneda" el número de veces que el valor actual del contador. Si aparece "Cabezas" cada vez, incrementa el contador. De lo contrario, no lo incremente.
Esto se puede hacer mediante programación generando "c" bits pseudoaleatorios (donde "c" es el valor actual del contador) y utilizando la función lógica AND en todos esos bits. El resultado es cero si alguno de esos bits pseudoaleatorios es cero y uno si todos son unos. Simplemente agregue el resultado al contador. Este procedimiento se ejecuta cada vez que se solicita incrementar el contador.
Aplicaciones
El algoritmo es útil para examinar grandes flujos de datos en busca de patrones. Esto es particularmente útil en aplicaciones de compresión de datos , reconocimiento visual y de sonido y otras aplicaciones de inteligencia artificial .
Ver también
Referencias
- ^ Nelson, Jelani; Yu, Huacheng (2020). "Límites óptimos para el recuento aproximado". arXiv : 2010.02116 . Cite journal 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 2015 sobre comunicaciones informáticas (INFOCOM) : 2560–2568. doi : 10.1109 / INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0.
Fuentes
- Morris, R. Contar un gran número de eventos en pequeños registros. Comunicaciones del ACM 21, 10 (1978), 840–842
- Flajolet, P. Recuento aproximado: un análisis detallado. TBI 25, (1985), 113-134 [1]
- Michael F., Chung-Kuei L., Prodinger, Conteo aproximado mediante el método de Poisson-Laplace-Mellin [2]