Count sketch

En informatique, le count sketch est une technique de réduction de dimensionnalité basée sur une structure de données probabiliste, permettant d'estimer avec un coût en mémoire limité le nombre d'apparitions des éléments les plus fréquents dans un flux de données.

Il a été introduit en 2004 par M. Charikar, K. Chen, et M. Farach-Colton.

Histoire

Le count sketch a été proposé comme une amélioration du sketch AMS de N.Alon, Y.Matias et M.Szegedy.

Définition

Le count sketch peut être vu comme un nom recouvrant à la fois une structure de données, une procédure permettant de la mettre à jour lorsqu'un nouvel élément du flux doit être traité, ainsi qu'une règle permettant à tout moment d'estimer la fréquence des éléments les plus courants à partir de la structure de données.

Structure de données

Soit 𝒳 l'ensemble d'entrée, c’est-à-dire auquel appartiennent les éléments du flux. Soit t,b∈ℕ>0 deux paramètres controllant la taille du sketch. Soient h1,…,ht des fonctions de hachage de 𝒳 vers {1,…,b} indépendantes. Soient s1,…,st des fonctions de hachage de 𝒳 vers {−1,+1}, indépendantes deux à deux et indépendantes des (hi)1≤i≤t

Le sketch lui-même consiste en une table (matrice) T∈ℤt×b, dont toutes les entrées sont initialisées à zéro.

Ajout d'un élément

Lorsqu'un nouvel élément x∈𝒳 est traité, la table est mise à jour de la manière suivante:

 Pour i=1,…,t  
   Ti,hi(x)=Ti,hi(x)+si(x)

Ainsi, chaque ligne du tableau a exactement une entrée qui est modifiée (incrémentée ou décrémentée selon la valeur de si(x)) lors de l'ajout d'un nouvel élément.

Estimation du nombre d'occurrences

Pour estimer le nombre d'occurrences d'un élément e∈𝒳, l'estimateur suivant est calculé:

n̂(e)=mediane(h1(e)s1(e),…,ht(e)st(e))

Garanties

Soit ϵ>0,k∈ℕ>0, et n le nombre total d'éléments dans le flux. Soit nk le nombre d’occurrences dans le flux du k-ième élément apparaissant le plus. Dans leur article original, les auteurs prouvent qu'en choisissant t=Θ(log⁡(n)/δ) et b plus grand qu'un seuil dépendant notamment de k,ϵ, l'algorithme permet de retrouver une liste de k éléments apparaissant chacun strictement plus de (1−ϵ)nk.

Voir aussi

Articles connexes