Count-Min Sketch
Structure de données probabiliste qui estime des fréquences dans un flux — Cormode & Muthukrishnan (2003). Un filtre de Bloom qui compte au lieu de se contenter de répondre oui ou non.
Une matrice à deux dimensions (d fonctions de hachage × w cases). Sur increment(clé) : on incrémente, pour chaque ligne, la case à l'indice hash_i(clé) % w. Sur count(clé) : on renvoie le minimum des cases lues (d'où le « min » du nom). Le résultat ne sous-estime jamais la vraie valeur ; il peut la surestimer, à cause des collisions, mais rarement.
On le retrouve dans des modules Redis, dans Druid, dans l'analyse NetFlow et dans les compteurs de « hashtags tendance ». Sobre en mémoire : 100 Mo suffisent à suivre des milliards de clés distinctes avec environ 1 % d'erreur.