Les flux de données rendaient le comptage exact peu pratique : conserver un compteur pour chaque élément possible pouvait coûter plus de mémoire que n'en disposait le processeur de flux. Les résumés antérieurs amélioraient l'espace, mais de nombreuses bornes restaient encore trop coûteuses.
Le Count-Min Sketch utilisait une petite matrice de compteurs et plusieurs fonctions de hachage. Les mises à jour étaient des incréments en temps constant ; les requêtes ponctuelles, par intervalle et de produit scalaire étaient approximatives, mais rapides et sous-linéaires en mémoire.
La page de publication de Cormode et Muthukrishnan résume l'amélioration : pour plusieurs problèmes de flux, la borne d'espace ou de temps s'améliorait typiquement d'un facteur de 1/epsilon au carré à 1/epsilon.
Faire pointer chaque erreur vers le haut
Les collisions de hachage sont tolérées plutôt que prévenues, ce qui rend la mémoire fixe et prévisible.
Prendre le minimum entre les lignes transforme de nombreux compteurs bruités en une surestimation bornée.
La structure prend en charge plusieurs requêtes de flux, et pas seulement un unique rapport d'éléments fréquents.
Sa forme compacte et fusionnable la rendait pratique pour la télémétrie, la publicité, les réseaux et les bases de données.
L'approximation est plus facile à exploiter lorsque ses erreurs ont une direction ; une erreur unilatérale permet aux systèmes en aval de traiter le résultat comme une estimation supérieure sûre.
Suites
Le Count-Min Sketch est devenu l'un des sketches standard pour l'estimation de fréquence dans les systèmes de flux. L'astuce ingénieuse n'était pas de prétendre que les collisions disparaissent ; elle organisait les collisions de sorte que leur dommage soit mesurable et unilatéral.
VÉRIFIEZ LES SOURCES
Les sources
- An improved data stream summary: The count-min sketch and its applications University of Oxford · cs.ox.ac.uk