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