¿Cómo se implementa un Count-Min Sketch para estimar frecuencias en flujos de datos?

1. Planteamiento

Una plataforma de registro recibe claves de eventos como URLs o IDs de productos, potencialmente miles de millones de eventos. Implemente add(key) y estimate(key) con memoria fija. Devuelva un conteo aproximado de ocurrencias y analice el error, la fusión de fragmentos (shards), el desbordamiento de contadores y cuándo se requiere una estructura exacta.

2. Restricciones y aclaraciones

• Cada evento se observa una vez; todas las claves no pueden caber en una tabla hash.
• La sobreestimación es aceptable, con parámetros que controlan la probabilidad de error.
• Comience con actualizaciones no negativas; las eliminaciones, los pesos negativos y la expiración basada en tiempo requieren restricciones adicionales.
• Los fragmentos (shards) solo pueden fusionarse directamente cuando el ancho, la profundidad, las semillas de hash y la codificación de los contadores coinciden.

3. Enfoque principal

Count-Min Sketch (CMS) mantiene d filas de w contadores no negativos. Cada fila tiene una función hash independiente que mapea una clave a una columna. Una actualización incrementa cada contador seleccionado; una consulta devuelve el mínimo de los contadores seleccionados. El conteo real aparece en cada fila seleccionada, mientras que las colisiones de otras claves solo pueden sumar a los contadores, por lo que el mínimo es un límite superior que no subestima el conteo.

Usando el error epsilon y la probabilidad de falla delta, las elecciones comunes son w = ceil(e / epsilon) y d = ceil(ln(1 / delta)). Con un peso total de actualización N, la estimación es a lo sumo el conteo real más epsilon * N con una probabilidad de al menos 1 - delta. Este es un límite de error probabilístico, no una garantía absoluta para cada consulta.

4. Implementación de referencia

init(epsilon, delta):
  w = ceil(e / epsilon)
  d = ceil(ln(1 / delta))
  table = array(d, w, fill=0)
  seeds = choose_d_independent_seeds()

add(key, weight=1):
  require weight >= 0
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    table[row][col] += weight
  total += weight

estimate(key):
  values = []
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    values.append(table[row][col])
  return min(values)

merge(other):
  require same w, d, seeds, counter encoding
  for each cell (r, c):
    table[r][c] += other.table[r][c]
  total += other.total

5. Complejidad y corrección

Cada actualización y consulta accede a d celdas, por lo que el tiempo es O(d). El espacio es O(d * w), independiente del número de claves distintas. Con actualizaciones no negativas, el mínimo permanece al menos igual a la frecuencia real. Aumentar el ancho reduce el sesgo de colisión; aumentar la profundidad reduce la probabilidad de exceder el límite de error, mientras que ambos aumentan la memoria y el trabajo de hashing linealmente.

Los contadores necesitan suficiente ancho de enteros o una política explícita de saturación; el desbordamiento cíclico sin signo invalidaría la propiedad de no subestimación. La fusión de fragmentos suma las celdas correspondientes, y todos los mapeos hash deben coincidir. Combinar diferentes disposiciones produce un resultado no interpretable.

6. Preguntas de seguimiento y trampas comunes

• CMS responde al conteo aproximado de una clave conocida; no enumera Top-K. Mantenga un conjunto de candidatos o use una estructura de elementos frecuentes (heavy-hitters) para eso.
• Las colisiones solo sobreestiman, por lo que la estimación no puede recuperar una frecuencia exacta ni un conjunto de elementos distintos exacto.
• Las actualizaciones negativas rompen la monotonicidad y la demostración simple; la eliminación y las ventanas deslizantes generalmente requieren cubos de tiempo (time buckets) o una estructura de decaimiento.
• Una ventana de tiempo no se puede mantener restando totales antiguos a menos que se conserve el estado de cubos con capacidad de reversión (rollback).

7. Lecturas adicionales

Compare CMS con un mapa hash exacto, un filtro de Bloom, HyperLogLog y un Frequent Items Sketch: estos están dirigidos respectivamente a consultas de frecuencia, pertenencia, cardinalidad e identificación de elementos frecuentes. Elija según la consulta, el presupuesto de error, las necesidades de eliminación y si se deben emitir claves candidatas.

8. Puntos de evaluación para la entrevista

Puede explicar la matriz de contadores

El candidato debe describir los hashes de fila independientes, la actualización de cada fila, la toma del mínimo y por qué las colisiones solo pueden aumentar un contador.

Puede enunciar los parámetros de error

Debe relacionar epsilon, delta, w, d y el peso total N, distinguiendo un límite probabilístico de una garantía exacta absoluta.

Puede manejar los límites de ingeniería

Debe abordar el desbordamiento de contadores, la compatibilidad de parámetros de fragmentos, la suma celda por celda y el diseño adicional para pesos negativos o ventanas deslizantes.

Puede elegir una estructura adecuada

Debe reconocer que CMS no proporciona Top-K, listas de pertenencia exactas ni cardinalidad exacta, y cambiar a un mapa exacto, HLL o una estructura de elementos frecuentes cuando los requisitos cambien.