Une nouvelle méthode efficace de comptage d'éléments distincts dans un flux de données

Des chercheurs viennent de pondre un nouvel algorithme révolutionnaire pour compter les éléments distincts dans un flux de données. Ça s’appelle le CVM et c’est super malin !

Imaginez un peu le truc, vous recevez des tonnes de données en continu, genre des milliards d’entrées, et vous voulez savoir combien y a d’éléments uniques là-dedans. Facile à dire mais pas évident à faire ! Parce que si vous essayez de tout stocker en mémoire pour comparer, bonjour la galère et l’explosion de RAM. C’est là que le CVM entre en scène !

Le principe est simple comme bonjour (enfin, quand on vous l’explique !). Au lieu de tout garder, on va échantillonner aléatoirement les données qui arrivent. Un peu comme quand vous piquez des frites dans l’assiette de votre pote pour goûter parce que vous, vous avez pris une salade. Sauf qu’ici, c’est un échantillon représentatif qu’on veut.

Concrètement, on conserve un petit sous-ensemble des éléments dans une mémoire limitée. Et quand ça déborde, on vire aléatoirement la moitié ! Hop, un petit coup de pile ou face et on libère de l’espace. Mais attention, c’est pas fini ! On repart pour un tour en ajustant la probabilité de garder un élément. Ainsi, à la fin, chaque rescapé a la même probabilité d’être là. Vous me suivez ? Non ? On s’en fiche, l’essentiel c’est que ça marche !

Les chercheurs qui ont inventé ça ont prouvé mathématiquement que leur bidule était précis et peu gourmand en mémoire. Genre vraiment précis, à quelques pourcents près. C’est dingue quand même, avec une poignée d’octets, on peut estimer des millions d’éléments distincts !

Et vous savez quoi ? L’algo est tellement simple qu’un étudiant pourrait l’implémenter. Pas besoin d’être un crack en maths ou en informatique, c’est à la portée de tous. Bon après, faut quand même en vouloir pour se fader les preuves théoriques. Mais ça ce n’est pas notre problème !

En gros, le CVM c’est une avancée notable, que ce soit pour analyser les logs, détecter des anomalies, mesurer une audience ou je ne sais quoi, il y a des tonnes d’applications. On nage en plein dans le Big Data !

Je peux déjà vous voir les data scientists qui me lisent, en train de vous frotter les mains et dégainer votre plus beau Python pour tester ce truc. Les entreprises vont pouvoir économiser des téraoctets de stockage et des heures de calcul, tout ça grâce à un petit algorithme simple mais efficace.

C’est quand même beau de voir comment avec une idée futée, on peut résoudre de grands problèmes. C’est encore une fois un bel exemple d’élégance algorithmique.

Bref, chapeau bas aux chercheurs de l’Institut Indien de Statistiques, de l’Université de Nebraska-Lincoln et de l’Université de Toronto qui ont pondu cette méthode de comptage. Les détails, c’est par ici que ça se passe : Computer Scientists Invent an Efficient New Way to Count