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^[1].

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

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.

Soit ${\displaystyle {\mathcal {X}}}$ l'ensemble d'entrée, c.-à-d. auquel appartiennent les éléments du flux. Soit ${\displaystyle t,b\in \mathbb {N} _{>0}}$ deux paramètres controllant la taille du sketch. Soient ${\displaystyle h_{1},\dots ,h_{t}}$ des fonctions de hachage de ${\displaystyle {\mathcal {X}}}$ vers ${\displaystyle \{1,\dots ,b\}}$ indépendantes. Soient ${\displaystyle s_{1},\dots ,s_{t}}$ des fonctions de hachage de ${\displaystyle {\mathcal {X}}}$ vers ${\displaystyle \{-1,+1\}}$, indépendantes deux à deux et indépendantes des ${\displaystyle (h_{i})_{1\leq i\leq t}}$

Le sketch lui-même consiste en une table (matrice) ${\displaystyle T\in \mathbb {Z} ^{t\times b}}$, dont toutes les entrées sont initialisées à zéro.

Lorsqu'un nouvel élément ${\displaystyle x\in {\mathcal {X}}}$ est traité, la table est mise à jour de la manière suivante:

 Pour ${\displaystyle i=1,\dots ,t}$  
   ${\displaystyle T_{i,h_{i}(x)}=T_{i,h_{i}(x)}+s_{i}(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 ${\displaystyle s_{i}(x)}$) lors de l'ajout d'un nouvel élément.

Pour estimer le nombre d'occurrences d'un élément ${\displaystyle e\in {\mathcal {X}}}$, l'estimateur suivant est calculé:

${\displaystyle {\hat {n}}(e)=\mathrm {mediane} (h_{1}(e)s_{1}(e),\dots ,h_{t}(e)s_{t}(e))}$

Soit ${\displaystyle \epsilon >0,k\in \mathbb {N} _{>0}}$, et ${\displaystyle n}$ le nombre total d'éléments dans le flux. Soit ${\displaystyle n_{k}}$ le nombre d’occurrences dans le flux du ${\displaystyle k}$-ième élément apparaissant le plus. Dans leur article original, les auteurs prouvent^[1] qu'en choisissant ${\displaystyle t=\Theta (\log(n)/\delta )}$ et ${\displaystyle b}$ plus grand qu'un seuil dépendant notamment de ${\displaystyle k,\epsilon }$, l'algorithme permet de retrouver une liste de ${\displaystyle k}$ éléments apparaissant chacun strictement plus de ${\displaystyle (1-\epsilon )n_{k}}$.

• Algorithme de Flajolet–Martin
• Filtre de Bloom
• HyperLogLog

• Portail de l’informatique