El algoritmo de recuento con pérdida es un algoritmo que identifica elementos en un flujo de datos cuya frecuencia excede un umbral determinado por el usuario. El algoritmo funciona dividiendo el flujo de datos en grupos para los elementos frecuentes, pero llena tantos grupos como sea posible en la memoria principal una sola vez. La frecuencia calculada por este algoritmo no siempre es precisa, pero tiene un umbral de error que puede ser especificado por el usuario. El tiempo de ejecución y el espacio requeridos por el algoritmo son inversamente proporcionales al umbral de error especificado; por lo tanto, cuanto mayor sea el error, menor será la huella.
El algoritmo fue creado por los científicos informáticos Rajeev Motwani y Gurmeet Singh Manku. Tiene aplicaciones en cálculos en los que los datos toman la forma de un flujo continuo de datos en lugar de un conjunto finito de datos , como las mediciones de tráfico de red , los registros de servidores web y los flujos de clics .
El algoritmo general es el siguiente [1]
