Un nouvel algorithme pour compter efficacement les éléments distincts
(quantamagazine.org)- L’algorithme CVM approxime le nombre d’éléments distincts dans de longs flux de données, ce qui permet d’estimer le nombre d’éléments uniques sans stocker toute la liste
- Il se concentre sur le problème des éléments distincts (distinct elements problem) lorsque l’entrée totale dépasse la mémoire, et peut s’appliquer à de grands journaux ou flux d’événements contenant de nombreuses répétitions
- Il conserve seulement une partie des éléments dans une mémoire limitée et, chaque fois que l’espace est rempli, répète des suppressions aléatoires afin d’uniformiser la probabilité de conservation de chaque élément
- Dans l’exemple de Hamlet, avec une mémoire de 100 mots, il a estimé en moyenne 3 955 éléments sur 5 essais, soit un résultat proche du nombre réel de mots distincts, 3 967 ; avec une mémoire de 1 000 mots, la moyenne s’améliore à 3 964
- Plus la mémoire augmente, plus la précision progresse, et si elle est suffisante pour contenir tous les éléments distincts, une précision de 100 % est possible
Compter les éléments distincts dans de longs flux de données
- L’objectif est d’estimer efficacement le nombre d’éléments uniques après déduplication dans une longue liste où les éléments arrivent un par un
- L’approche la plus simple consiste à stocker tous les éléments vus jusqu’ici et à comparer chaque nouvel élément à la liste existante
- Dans une étude sur la faune, il faut vérifier en permanence la liste des photos d’animaux déjà observés
- Quand la liste atteint des milliards d’entrées, comme pour le nombre d’utilisateurs se connectant chaque jour à Facebook, le stockage et la comparaison deviennent difficiles
- CVM est un algorithme nommé d’après Sourav Chakraborty, Vinodchandran Variyam et Kuldeep Meel
- Il peut s’appliquer à des listes où les éléments arrivent séquentiellement, comme des mots, des produits sur un tapis roulant ou des véhicules sur une autoroute
L’idée centrale de l’algorithme CVM
- CVM ne stocke pas tous les éléments, mais seulement une partie de ceux qui tiennent dans une mémoire limitée
- Il utilise le hasard pour contrôler la probabilité qu’un élément distinct reste dans la liste finale
- Andrew McGregor estime que cet algorithme est si simple et facile à implémenter qu’il pourrait devenir une approche de base pour le problème concret des éléments distincts
Fonctionnement illustré avec Hamlet
- Hamlet contient au total 30 557 mots, et l’algorithme cherche à estimer le nombre de mots distincts
- Si l’on suppose une mémoire équivalente à un tableau blanc de 100 mots, on commence par y inscrire les 100 premiers mots distincts, en sautant les répétitions
- Une fois l’espace rempli, on lance une pièce pour chaque mot
- pile : le mot est conservé
- face : le mot est supprimé
- après cette étape préliminaire, il reste environ 50 mots distincts
Des conditions de conservation plus strictes à chaque round
- Au round 1, on continue d’ajouter de nouveaux mots et, si un mot déjà présent dans la liste réapparaît, on lance une pièce et on le supprime en cas de face
- Quand la liste revient à 100 mots, le round 1 se termine en supprimant environ la moitié des mots selon le résultat de 100 lancers de pièce
- À partir du round 2, il devient plus difficile pour un mot de survivre
- si un mot répété apparaît, il est supprimé en cas de face
- si le résultat est pile, on relance une pièce, et le mot n’est conservé que si le deuxième lancer donne aussi pile
- Au troisième round, il faut obtenir 3 piles consécutifs ; au quatrième round, 4 piles consécutifs
- En général, à la fin du k-ième round, la probabilité qu’un mot soit encore présent est de 1/2^k
Calcul de l’estimation et résultats expérimentaux
- On peut estimer le nombre total de mots distincts en divisant le nombre de mots restants dans la liste finale par leur probabilité de survie
- Par exemple, s’il reste 61 mots après 6 rounds, on divise par la probabilité 1/2^6 pour obtenir une estimation de 3 904
- Le nombre réel de mots distincts dans Hamlet est de 3 967
- Plus la taille de la mémoire augmente, plus l’estimation se rapproche de la valeur réelle
- avec une mémoire de 100 mots, la moyenne des estimations sur 5 exécutions est de 3 955
- avec une mémoire de 1 000 mots, la moyenne est de 3 964
- Variyam et ses collègues ont démontré mathématiquement que la précision de cette technique évolue en fonction de la taille de la mémoire
Une solution simple mais non triviale
- CVM est considéré comme une avancée importante sur le problème des éléments distincts, étudié depuis plus de 40 ans
- William Kuszmaul estime que même sur des problèmes très fondamentaux et déjà largement étudiés, il peut rester des solutions simples mais difficiles à imaginer
1 commentaires
Commentaires de Hacker News
J’ai participé avec les auteurs à l’implémentation de la version comptage du volume DNF de cet algorithme. Article associé ici : https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
Le code est ici : https://github.com/meelgroup/pepin
L’algorithme est absurdement rapide, au point que, souvent, 30 % du temps total est consacré aux E/S de lecture de fichiers. Pour info, Knuth a aussi contribué à l’algorithme, et ses notes sont ici : https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
Il a pris un mois entier sur son travail sur TAOCP pour faire ça, et il était, comme on peut l’imaginer, incroyablement brillant.
Cet algorithme ressemble à HyperLogLog, qui est d’ailleurs cité dans l’article. Il utilise la même intuition — suivre les séries de pile/face pour obtenir une estimation — mais semble retourner l’idée pour en faire un algorithme plus simple, où l’on abandonne les valeurs mémorisées selon la continuité des résultats des lancers de pièce.
Il fonctionne particulièrement efficacement en contexte de streaming, ce qui permet de maintenir quelque chose qui ressemble à un « compteur » du nombre d’éléments distincts, avec un certain taux d’erreur.
L’avantage d’HyperLogLog, c’est qu’à certains égards il se comporte comme un ensemble de hachage. On peut ajouter des éléments, compter le nombre d’éléments distincts et, surtout, fusionner deux HLL pour obtenir leur union, tout en gardant une mémoire fixe de quelques Ko même pour des ensembles de plusieurs milliards d’éléments. Dans les stockages de données distribués, c’est cette astuce qu’utilisent l’agrégation cardinality d’Elasticsearch/OpenSearch et PFADD/PFMERGE/PFCOUNT de Redis/Redict.
Je ne sais pas exactement comment l’algorithme CVM se compare à HLL, mais puisqu’il a été relu par Knuth et qu’un étudiant de premier cycle peut facilement l’implémenter, ça doit être un algorithme plutôt solide.
http://oertl.github.io/hyperloglog-sketch-estimation-paper/
Dans un précédent emploi, j’avais implémenté exactement cet algorithme, en stockant aussi, à côté de chaque valeur, une estimation du nombre de fois où elle était apparue. Cela permettait de produire une liste approximative des valeurs les plus fréquentes, avec le compte estimé de chacune.
Quand je travaillais autrefois dans un hôpital, j’avais utilisé l’échantillonnage par réservoir pour créer un petit sous-ensemble d’enregistrements stockés sur des bandes DAT.
Lire l’article m’a pris presque autant de temps que lire le billet de blog, et l’article était plus instructif
https://arxiv.org/pdf/2301.10191
Il traite de l’estimation de la cardinalité de l’ensemble des éléments issus d’un flux. L’algorithme est si simple qu’on peut le coder soi-même pendant la lecture de l’article pour jouer avec
Les auteurs indiquent clairement que le public visé et l’objectif de cet algorithme sont les étudiants de premier cycle et les manuels
Comme Knuth l’a relu lui-même, il a peut-être jugé que cet algorithme appartenait à cette catégorie. Si c’est le cas, l’avoir mis dans le titre peut sembler être une vantardise peu modeste de la part des auteurs, mais c’est une vantardise amplement méritée
Je me souvenais à tort que cette expression venait de Knuth ; ma mémoire me trompait
Utiliser simplement une boucle semble moins pénible que d’expliquer https://en.wikipedia.org/wiki/Up_tack. [1]
[1] https://news.ycombinator.com/item?id=40388878
D’abord, le traitement de la contradiction ressemble simplement à une erreur ou à un panic, et je ne comprends pas pourquoi il est formulé ainsi. Ensuite, l’hypothèse 1..m prête à confusion. Je n’étais pas sûr qu’il faille connaître la taille à l’avance ou non, mais en lisant la suite il semble que non. On choisit un seuil et la probabilité change selon la taille du flux, mais la description de l’algorithme donne l’impression qu’il n’a qu’une seule sortie, ce qui est déroutant
Les bornes de Chernoff et delta/epsilon ne sont pas du tout expliqués dans l’article, ce qui m’a encore plus embrouillé. Voici le code que j’ai implémenté en Go : https://github.com/betamos/distinct
Extraire la partie liée au seuil dans un helper a beaucoup plus de sens que de risquer d’allouer accidentellement trop de mémoire. Il faudrait aussi, à mon avis, des méthodes pour estimer la confiance ou le taux d’erreur. Comme personne ne connaît à l’avance la taille du flux, il est plus naturel de mettre cette valeur à jour au fil de l’eau
Vu le sujet de l’article, la note de bas de page est particulièrement charmante
Les auteurs disent avoir choisi un ordre aléatoire, au lieu de l’ancienne convention consistant à classer les noms d’auteurs par ordre alphabétique, et l’avoir signalé par r⃝. La trace publiquement vérifiable de la randomisation est ici : https://www.aeaweb.org/journals/policies/random-author-order...
[0]: https://arxiv.org/pdf/2301.10191
La description de l’algorithme ne vous semble-t-elle pas fausse ?
Si l’on implémente « vérifier si le mot est dans la liste, puis le supprimer » d’après la description « quand on rencontre un mot déjà présent dans la liste, on relance la pièce, et si c’est pile on supprime le mot », on obtient environ 20 itérations et une estimation absurde comme 772800512
À l’inverse, si l’on stocke d’abord le mot puis que l’on supprime le même mot, on obtient 7240, proche du nombre réel de mots distincts, 7233. Autrement dit, l’ordre est important dans la description, et il semble avoir été mal transmis
Après avoir lu l’article, j’ai obtenu les bonnes estimations, et le problème tenait à un petit else. L’explication de Quanta se lit comme « si ce n’est pas dans la liste, on l’ajoute ; sinon, on le retire selon une certaine probabilité », alors que l’implémentation correcte consiste à appliquer ensuite la condition probabiliste indépendamment du fait qu’on l’ait ajouté ou non
Estimer le nombre d’éléments distincts d’un ensemble et compter le nombre d’éléments distincts d’un ensemble sont deux choses très différentes. C’est une méthode élégante, mais le titre n’est pas terrible
Par exemple, on dit qu’on « compte les voix » lors d’une élection, mais si le scrutin est serré, on procède à un « recomptage », et l’on s’attend tout à fait à obtenir un nombre légèrement différent du décompte initial. Le comptage des voix est donc en fait une estimation des voix, et le recomptage n’est qu’une estimation avec des bornes d’erreur plus étroites
Le mythe des « countless stones » (https://en.wikipedia.org/wiki/Countless_stones) me semble aussi être un rappel populaire qu’on ne peut pas être trop sûr d’avoir correctement compté même des menhirs grands, solides et statiques
Les cas où le comptage n’est pas une estimation se limitent plus ou moins aux situations mathématiques : quand on peut garantir qu’on a traité tous les éléments sans omission et qu’on n’a confondu l’identité d’aucun élément avec un autre
Par exemple, la mole est un entier, mais sa valeur n’est connue qu’approximativement, et personne ne se soucie de sa valeur exacte
J’aime vraiment ce genre d’exemple de penser hors du cadre. D’autant plus que, professionnellement, c’est un point sur lequel je ne suis pas très bon. Il ne s’agit pas seulement d’apprendre la bonne manière de résoudre un problème, mais de trouver les questions qui rendent le problème qu’on a plus facile, voire parfois possible
Ici, la question clé est : « on n’a pas besoin du nombre exact, il suffit de définir une plage probabiliste dans des paramètres donnés ». Pour d’autres problèmes, il y aura d’autres questions. J’espère qu’en voyant suffisamment d’exemples de ce type, on peut intérioriser ce processus de réflexion et l’appliquer correctement
Si, dans une grande entreprise, on vous payait pour rester toute la journée devant un tableau blanc avec des ingénieurs tout aussi brillants, vous finiriez certainement par produire quelque chose qui passerait, aux yeux du monde, pour une « solution hors du cadre »
Mais la plupart d’entre nous sommes payés pour travailler sur une chaîne de production JIRA, donc le temps disponible pour expérimenter sur un seul problème est limité
L’exemple « si l’on veut compter le nombre d’utilisateurs distincts qui se connectent chaque jour à Facebook, sachant que certains utilisateurs se connectent depuis plusieurs appareils et à plusieurs moments » ne me semble pas être un cas où cet algorithme serait vraiment utile
Si l’on sait déjà qu’on aura besoin de cette information au moment de concevoir le processus de connexion, c’est simple. On stocke la date de dernière connexion de chaque compte, et on n’incrémente le compteur d’utilisateurs uniques que lorsque la valeur stockée diffère de la date courante
Même si ce n’est pas le cas, on devrait pouvoir « rejouer » plus tard le flux des événements de connexion depuis la base de données pour l’analyser. Ce serait différent si l’on avait déjà accumulé des années de données
À propos du comptage, je voudrais mentionner un algorithme efficace et facile à implémenter pour trouver les k éléments les plus fréquents dans un flux. Il me semble moins connu qu’il ne le mérite
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf
Votre description donne l’impression qu’on cherche un nombre fixe de k éléments, avec la garantie qu’ils sont nécessairement les plus fréquents. L’abstract donne plutôt l’impression qu’on cherche des éléments, dont le nombre n’est pas connu à l’avance, qui satisfont une condition du type « supérieur à une certaine valeur k »
Cela ressemble à la différence entre « trouver les 100 utilisateurs les plus âgés » et « trouver tous les utilisateurs de plus de 30 ans » ; est-ce que j’ai mal compris vos propos ou l’abstract ? L’anglais n’est pas ma langue maternelle, donc je m’y perds
Les informaticiens ont donc inventé une méthode économe en mémoire pour estimer la taille d’un sous-ensemble