Los flujos de datos hacían que el conteo exacto resultara poco práctico: mantener un contador para cada elemento posible podía costar más memoria de la que tenía el procesador de flujos. Resúmenes anteriores mejoraban el espacio, pero muchas cotas seguían siendo demasiado costosas.
Count-Min Sketch usaba una pequeña matriz de contadores y varias funciones hash. Las actualizaciones eran incrementos en tiempo constante; las consultas puntuales, por rango y de producto interno eran aproximadas, pero rápidas y sublineales en memoria.
La página de publicación de Cormode y Muthukrishnan resume la mejora: para varios problemas de flujos, la cota de espacio o de tiempo típicamente mejoraba de un factor de 1/epsilon al cuadrado a 1/epsilon.
Hacer que todo error apunte hacia arriba
Las colisiones de hash se toleran en lugar de prevenirse, lo que hace que la memoria sea fija y predecible.
Tomar el mínimo entre las filas convierte muchos contadores ruidosos en una sobreestimación acotada.
La estructura admite varias consultas de flujos, no solo un único informe de elementos frecuentes.
Su forma pequeña y fusionable la hizo práctica para telemetría, publicidad, redes y bases de datos.
La aproximación es más fácil de operar cuando sus errores tienen una dirección; el error unilateral permite que los sistemas posteriores traten el resultado como una estimación superior segura.
Count-Min Sketch se convirtió en uno de los sketches estándar para la estimación de frecuencias en sistemas de flujos. El movimiento ingenioso no fue fingir que las colisiones desaparecían; dispuso las colisiones de modo que su daño fuera medible y unilateral.
CONSULTA LAS PRUEBAS
Las fuentes
- An improved data stream summary: The count-min sketch and its applications University of Oxford · cs.ox.ac.uk