Description
Date depot: 1 janvier 1900
Titre: Algorithmique quantitative de très hautes performances pour les masses de données
Directrice de thèse:
Michèle SORIA (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le sujet de cette thèse est l'extraction de caractéristiques quantitatives de masses de données de natures très diverses (traces de routeurs dans les réseaux, corpus de documents textuels, très grandes bases de données), avec des méthodes très fines issues de l'analyse d'algorithmes.
Dans la démarche utilisée, les données sont d'abord transformées par une fonction de hachage universelle en des quantités pseudo-aléatoires uniformes. Il s'agit ensuite de déterminer des observables qui fournissent des indications quantitatives sur diverses caractéristiques des données. On entre alors dans une boucle d'analyse-synthèse: analyse du comportement probabiliste des observables, calcul de biais et estimation de variance, puis synthèse d'algorithme. Les résultats attendus sont des algorithmes qui opèrent en une seule passe, utilisent une mémoire très réduite (quelques Koctets) et fournissent des résultats de précision garantie (quelques pour-cent). Une telle algorithmique permet de traiter en quelques secondes des volumes de données de plusieurs Goctets, apportant fréquemment des gains de plusieurs ordres de grandeurs par rapport à une algorithmique déterministe classique.
Les problèmes à traiter dans le cadre de cette thèse sont les suivants:
a) Détermination de cardinalité d'opérateurs booléens appliqués à des flux de données (par exemple décision du problème de l'inclusion).
b) Détermination de caractéristiques fines du 'profil' des données: moments de fréquence, et notamment indice de variabilité.
c) Echantillonnage de valeurs distinctes et application à l'estimation des éléments de basse fréquence ('souris' dans la terminologie de surveillance des réseaux).
d) Estimation de l'indice de similarité de flux et documents (index de Broder) et comparaison des méthodes fondées sur l'échantillonnage, l'estimation de cardinalité, et les techniques dites 'min-hashing'.
e) Extraction de caractéristiques quantitatives de grands graphes (graphe du web, graphe de l'Internet), comme l'indice d'ordonnance, mesuré par le nombre de triangles et de petites cliques.
Le candidat devra avoir une excellente formation en algorithmique, une très bonne connaissance de l'analyse des modèles probabilistes discrets et un goût marqué pour l'expérimentation sur données réelles.
Doctorant.e: Lumbroso Jeremie Oliver