Grâce à quelques algorithmes probabilistes simples, il s’avère possible de déterminer « au vol » et avec très peu de mémoire auxiliaire certaines caractéristiques quantitatives de flux massifs de données. Les algorithmes correspondants reposent de manière cruciale sur une analyse de modèles discrets. On donnera un aperçu d’algorithmes fondamentaux relatifs au comptage et à la détermination de la cardinalité (nombre de valeurs différentes), ainsi qu’à la boucle d’analyse-conception qui met en jeu des méthodes de la combinatoire analytique (fonctions génératrices et transformation de Mellin, notamment). Quelques applications à la gestion de réseaux et à la classification de documents seront également évoquées.

INRIA-Rocquencourt