Count-Min Sketch
Un Count-Min Sketch estime des fréquences avec plusieurs fonctions de hachage, en utilisant un espace sous-linéaire au prix d'une surestimation ; il sert aux statistiques de fréquence sur les flux.
Objectif
Fournir des statistiques de fréquence approximatives économes en espace sur des flux de données.
Mécanisme
Une matrice de comptage à d lignes et w colonnes. Mise à jour de x : pour chaque ligne i, count[i][h_i(x)]+=1. Requête de x : prendre min_i count[i][h_i(x)]. La probabilité de surestimation est au plus we^(-d), avec une erreur ≤ε||f||_1.
Cas d’usage
- Statistiques de flux
- Estimation de fréquences
- Détection Top-k