Algoritmo de conteo con pérdida

El algoritmo de conteo con pérdida identifica elementos en un flujo de datos cuya frecuencia supera un umbral definido por el usuario. El algoritmo divide el flujo de datos en grupos para los elementos frecuentes, llenando la mayor cantidad posible de grupos en la memoria principal de una sola vez. La frecuencia calculada por este algoritmo no siempre es precisa, pero tiene un umbral de error que puede especificar el usuario. El tiempo de ejecución y el espacio requerido por el algoritmo son inversamente proporcionales al umbral de error especificado; por lo tanto, cuanto mayor sea el error, menor será el consumo de memoria.

El algoritmo fue creado por los informáticos Rajeev Motwani y Gurmeet Singh Manku. Encuentra aplicaciones en cálculos donde los datos toman la forma de un flujo de datos continuo en lugar de un conjunto de datos finito , como mediciones de tráfico de red , registros de servidores web y flujos de clics .

El algoritmo general es el siguiente ^{[ 1 ]}

• Paso 1: Dividir el flujo de datos entrante en cubos de ancho${\displaystyle w=1/\epsilon }$, dónde${\displaystyle \epsilon }$es mencionado por el usuario como el límite de error (junto con el umbral de soporte mínimo =${\displaystyle \sigma }$).
• Paso 2: Incremente el contador de frecuencia de cada elemento según los nuevos valores de los cubos. Después de cada cubo, disminuya todos los contadores en 1.
• Paso 3: Repetir – Actualizar los contadores y después de cada cubo, disminuir todos los contadores en 1.