Count-Min Sketch
Struttura dati probabilistica per approssimare le frequenze in un flusso — Cormode & Muthukrishnan (2003). Come un filtro di Bloom, ma conta invece di rispondere solo sì/no.
Matrice bidimensionale (d funzioni hash × w bucket). Con increment(key) si incrementa la cella in hash_i(key) % w per ogni riga. Con count(key) si restituisce il minimo tra tutte le righe (da cui «min» nel nome). Non sovrastima mai la frequenza reale, ma può sottostimarla, di rado.
Alimenta moduli di Redis, Druid, l'analisi NetFlow e i contatori dei «hashtag di tendenza». Efficiente in memoria: 100 MB bastano per seguire miliardi di chiavi distinte con un errore di circa l'1 %.