Compter les objets dans un flux de données - les nuls

Apprendre à compter des objets dans un flux peut vous aider à trouver les éléments les plus fréquents ou à classer les événements habituels et inhabituels. Cet algorithme utilise des fonctions de hachage et des croquis approximatifs. Il le fait après avoir filtré les objets dupliqués et compté les éléments distincts qui sont apparus dans le flux de données.

Vous utilisez cette technique pour résoudre des problèmes tels que trouver les requêtes les plus fréquentes dans un moteur de recherche, les articles les plus vendus d'un détaillant en ligne, les pages très populaires d'un site Web ou les stocks les plus volatils (en comptant vendu et acheté).

Vous appliquez la solution à ce problème, Count-Min Sketch, à un flux de données. Il ne nécessite qu'un seul passage de données et stocke le moins d'informations possible. Cet algorithme est appliqué dans de nombreuses situations du monde réel (telles que l'analyse du trafic réseau ou la gestion de flux de données distribués). La recette nécessite d'utiliser un tas de fonctions de hachage, chacune associée à un vecteur de bits, d'une manière qui ressemble à un filtre de Bloom, comme le montre la figure:

1. Initialise tous les vecteurs binaires aux zéros dans toutes les positions.
2. Appliquez la fonction de hachage à chaque vecteur binaire lors de la réception d'un objet d'un flux. Utilisez l'adresse numérique résultante pour incrémenter la valeur à cette position.
3. Appliquez la fonction de hachage à un objet et récupérez la valeur à la position associée lorsqu'on lui demande d'estimer la fréquence d'un objet. De toutes les valeurs reçues des vecteurs binaires, vous prenez la plus petite fréquence du flux.

Comment les valeurs sont mises à jour dans un croquis Count-Min.

Parce que les collisions sont toujours possibles lors de l'utilisation d'une fonction de hachage, en particulier si le vecteur binaire associé a peu de créneaux, disposer de plusieurs vecteurs binaires vous assure qu'au moins l'un d'entre eux garde la bonne valeur. La valeur du choix devrait être la plus petite car elle n'est pas mélangée avec des comptes faussement positifs dus aux collisions.