Count-Min Sketch
Ein Count-Min Sketch schätzt Häufigkeiten mit mehreren Hash-Funktionen und nutzt sublinearen Speicher auf Kosten einer Überschätzung; es dient Häufigkeitsstatistiken über Datenströme.
Zweck
Speichereffiziente, approximative Häufigkeitsstatistiken über Datenströme bereitstellen.
Mechanismus
Eine Zählmatrix mit d Zeilen und w Spalten. Update von x: für jede Zeile i, count[i][h_i(x)]+=1. Abfrage von x: min_i count[i][h_i(x)] nehmen. Die Überschätzungswahrscheinlichkeit beträgt höchstens we^(-d), mit Fehler ≤ε||f||_1.
Anwendungsfälle
- Stream-Statistiken
- Häufigkeitsschätzung
- Top-k-Erkennung