Count-Min Sketch
Un Count-Min Sketch estima frecuencias con múltiples funciones hash, usando espacio sublineal a costa de sobreestimación; se usa en estadísticas de frecuencia sobre flujos.
Propósito
Proporcionar estadísticas de frecuencia aproximadas con uso eficiente de espacio sobre flujos de datos.
Mecanismo
Una matriz de conteo de d filas y w columnas. Actualizar x: para cada fila i, count[i][h_i(x)]+=1. Consultar x: tomar min_i count[i][h_i(x)]. La probabilidad de sobreestimación es a lo sumo we^(-d), con error ≤ε||f||_1.
Casos de uso
- Estadísticas de flujos
- Estimación de frecuencias
- Detección Top-k