Thèse de Chemseddine Nabti


Sujet :
Structure et Algorithmes de graphes pour le big Data

Résumé :

Big Data est un paradigme émergeant qui a gagné un intérêt substantiel dans le domaine académique ainsi qu’en industrie. Aujourd’hui, les applications d’observation et de la surveillance des systèmes, et les modèles de simulation, ainsi que les nouvelles applications comme : les réseaux sociaux, capteurs, l’internet des objets, etc., produisent une grande quantité de données, ces données doivent être collectées, traitées et communiquées.
Les graphes sont au cœur des problématiques du Big Data liées à la détection de données, leur traitement de données, et la communication de ces données. En effet, les Graphes sont utilisés pour représenter les objets, les interactions entre ces objets, et les données complexes et hétérogènes ce qui est un grand défi dans l’air du big data.
En fait, la collecte et la communication des données reposent sur des méthodes de calcul et d'optimisation sur les topologies de réseau, représentées par des graphes. Le traitement de données est relié aux algorithmes de graphes qui visent à comparer et rechercher des données structurées et complexes.
Dans cette thèse on s’intéresse aux grands graphes, en explorant leurs paramètres et propriétés, qui peuvent être utilisés pour simplifier leur traitement. Pour ce faire, nous nous appuyons sur une approche à trois niveaux basés sur la structure des graphes. Dans cette approche, le but est de simplifier les algorithmes de traitement de graphes afin qu'ils puissent être exécutés sur une seule machine dans un temps acceptable. Les trois niveaux considérés sont :
1- Niveau 1 : les représentations de graphes. Comment représenter des grands graphes en gardant leurs propriétés, et en même temps en minimisant l’espace mémoire requis pour les stocker ?
2- Niveau 2 : Un traitement orienté-Représentation. Comment adapter le traitement des requêtes et des algorithmes de graphes tels que les algorithmes de recherche, et de comparaison sur ces représentations?
3- Niveau 3 : Utiliser les propriétés de la représentation. Est-ce que ces représentations des graphes mettent en évidence de nouvelles propriétés sur lesquelles nous pouvons nous appuyer pour atteindre plus de performance?
Comme un domaine d'application, nous avons l'intention de travailler sur deux principaux types de grands graphes:
1- Analyse des réseaux sociaux afin d'analyser les interactions et la recherche pour des communautés ou aux interconnexions particulières.
2- La découverte de ressources à grande échelle des objets connectés sur l'Internet des objets. Ici l'objectif est d'utiliser les propriétés de données pour appréhender les milliards d'objets connectés.


Encadrant : Hamida Seba

Date de soutenance : vendredi, 15 décembre, 2017