Count-Min Sketch
Estructura de datos probabilística para aproximar frecuencias en un flujo — Cormode y Muthukrishnan (2003). Como un filtro de Bloom, pero cuenta en lugar de responder solo sí/no.
Una matriz de 2D (d funciones hash × w cubetas). En increment(key) se incrementa la celda de hash_i(key) % w por cada fila. En count(key) se devuelve el mínimo de todas las filas (de ahí el «min» del nombre). Nunca sobreestima; puede subestimar, pero rara vez.
Da soporte a módulos de Redis, a Druid, al análisis de NetFlow y a los contadores de «hashtags en tendencia». Eficiente en memoria: 100 MB pueden seguir miles de millones de claves distintas con ~1 % de error.