Philippe Flajolet (INRIA Rocquencourt, Académie des Sciences, médaillé du CNRS)

Cette conférence présente quelques axes de développement d’une algorithmique cohérente et générique d’estimation rapide de caractéristiques essentielles des volumes massifs de données. Il s’agit d’utiliser une mémoire très limitée et un tout petit nombre d’instructions par élément traité. Cette algorithmique est par nature probabiliste (étant fondée sur le hachage) mais elle ne se s’autorise pratiquement aucune hypothèse statistique a priori quant aux types de données auxquels elle s’applique. Les problèmes traités concerneront le comptage approximatif, le comptage probabiliste du nombre d’éléments différents, l’échantillonnage des domaines, ainsi que l’estimation des “moments des fréquences”. L’analyse de ces algorithmes, nécessaire à leur validation, met en jeu des méthodes parfois sophistiquées de la combinatoire analytique dont il sera donné au passage un bref aperçu.

Références: http://algo.inria.fr/flajolet/Publications/publist.html Voir: Counting by coin tossings, 2004