Count-Min Sketch
Probabilistische datastructuur om frequenties in een datastroom te benaderen — Cormode & Muthukrishnan (2003). Als een Bloomfilter, maar dan met tellen in plaats van alleen ja/nee.
Een 2D-matrix (d hashfuncties × w buckets). Bij increment(key) wordt in elke rij de cel op hash_i(key) % w verhoogd. Bij count(key) is het antwoord het minimum over alle rijen (vandaar “min” in de naam). Overschat nooit, kan wel onderschatten, maar zelden.
Wordt gebruikt in Redis-modules, Druid, NetFlow-analyse en tellers voor “trending hashtags”. Zuinig met geheugen: 100 MB kan miljarden verschillende sleutels bijhouden met ongeveer 1 % fout.