FLUX
Flux massifs et algorithmes d'estimation probabiliste (FLUX)
Description du projet
Ce projet propose en premier
lieu de développer une algorithmique cohérente et générique d'estimation rapide
des caractéristiques essentielles des flux massifs de données en utilisant une
mémoire très limitée et un très petit nombre d'instructions par élément traité.
Ces algorithmes seront par nature probabilistes mais on ne s'autorise aucune
hypothèse statistique a priori quant aux types de données auxquels elle s'applique.
Cette algorithmique doit être validée théoriquement de manière complète et elle
sera solidement testée sur des données issues principalement du monde des
télécommunications. Sur ces algorithmes d'estimation, nous proposons d'abord de
construire des analyseurs de haute performance applicables aux traces massives
du trafic Internet et permettant l'identification et la classification du
trafic IP (mise en évidence des types de trafic et des dépendances longues par
exemple). Nous étudierons ensuite l'impact de l'algorithmique de base sur
l'extraction de caractéristiques de très grands graphes, tels le graphe de
l'Internet (graphe des routeurs) ou le graphe de la Toile (graphe des
pointeurs). L'objectif est alors de détecter les "architectures virtuelles"
et les "communautés" ainsi que de permettre l'extraction rapide de
nombreuses caractéristiques quantitatives
(distribution des degrés et lois de puissance, excentricité,
multiconnectivité).
Coordinateur du projet
FLAJOLET Philippe - Projet Algorithmes, INRIA Rocquencourt
Partenaires