Count-Min-Sketch
Probabilistische Datenstruktur, um Häufigkeiten in einem Stream anzunähern — Cormode & Muthukrishnan (2003). Wie ein Bloom-Filter, zählt aber statt nur „ja/nein" zu sagen.
2D-Matrix (d Hashfunktionen × w Buckets). Bei increment(key): die Zelle bei hash_i(key) % w in jeder Zeile erhöhen. Bei count(key): das Minimum über alle Zeilen zurückgeben (daher „Min" im Namen). Überschätzt nie, kann unterschätzen, aber selten.
Treibt Redis-Module, Druid, NetFlow-Analyse, Zähler für „Trending Hashtags" an. Speichereffizient: 100 MB Speicher reichen, um Milliarden verschiedener Keys mit rund 1 % Fehler zu verfolgen.