Count sketch

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

Summarize Timeline Fact Check

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))}$