Tâches

1 - Algorithmes pour l’analyse et la fouille de grands graphes

Le travail réalisé dans le cadre de la tâche 1 Algorithmes pour l’analyse et la fouille de grands graphes du projet GIRAFON visait à développer de nouveaux algorithmes permettant l’analyse de grands graphes. Il a été effectué dans le cadre d’une collaboration entre les équipes BDTLN (Bases de données et Traitement des langues naturelles) du LIFAT (Laboratoire d’Informatique Fondamentale et Appliquée des Tours), PAMDA (Parallélisme, calcul distribué, bases de données) et CA (Contraintes et Apprentissage) du LIFO (Laboratoire d’Informatique Fondamentale d’Orléans).

Ce travail collaboratif a impliqué l’embauche d’un post-doctorant, M. Khanh-Chuong Duong. Ce post-doctorant a notamment eu en charge le développement dans un environnement Hadoop/MapReduce de nouvelles méthodes de fouille de données, mais également leurs expérimentations sur de gros volumes de données dans des clusters de machines virtuelles mises à disposition par le LIFO. Ce post-doctorant a été aidé dans ses développements par un stagiaire de master, Léo Fourrier, financé grâce à l’aide de la fédération ICVL (Informatique en Centre Val de Loire).

Au démarrage du projet, dans un environnement distribué Hadoop/MapReduce, aucune méthode ne permettait d’extraire les motifs fréquents d’un grand volume de données, en garantissant la réalisation complète et correcte du calcul quel que soit la mémoire disponible sur les différents nœuds du système. Dans ce contexte, l’algorithme MapFIM développé par les équipes BDTLN, PAMDA et CA impliquées dans le projet est le premier algorithme de fouille de motifs fréquents qui soit t-extensible, à savoir qui puisse traiter un volume quelconque de transactions, en s’adaptant aux ressources mémoires disponibles dans les différents nœuds du système. Si la première version de l’algorithme nécessitait un réglage manuel de paramètres pour garantir son exécution la plus optimale possible, sa deuxième version garantit un usage optimal des ressources mémoires disponibles tout en limitant l’intervention de l’utilisateur (par un choix judicieux de paramètres).

2 - Langages de requêtes sur les grands graphes

Les propositions actuelles s’intéressent essentiellement aux requêtes sur la structure des graphes alors que les travaux sur le web sémantique nous permettent d’envisager des formes plus riches d’interrogation où la sémantique des divers types de données est prise en compte.

Luiz Celso Gomes a travaillé ur un langage de requête: conception et implémentation d’un langage type datalog étendu (agrégation, calcul, etc). Un prototype avec les données en mémoire centrale a été réalisé. Cheik Ba a continué ce travail avec l’étude d’extension vers des données distribuées avec le framework Giraph.

3 - Programmation parallèle structurée sur les grands graphes

Les objectifs de cette tâche étaient de concevoir une ou plusieurs bibliothèques de parallélisme structuré pour les grands graphes mais adaptées à certaines classes de problèmes étudiés au sein de ce projet, et d’étudier la sémantique formelle de bibliothèques et tirer parti des propriétés, notamment algébriques, des opérations proposées pour concevoir des règles de transformation, fondements d’un outil d’optimisation basé sur des techniques de transformation de programmes.

Nous avons conçu GeoSkelSL, un langage DSL dédié aux géosciences qui aide les non-spécialistes en informatique à écrire leurs propres programmes parallèles. Ce DSL est intégré au langage Python, largement utilisé en géosciences. Le programme écrit par l’utilisateur est dérivé d’un programme parallèle efficace C++/MPI utilisant des motifs parallèles implicites. Les outils associés au DSL génèrent également des scripts qui permettent à l’utilisateur de compiler et d’exécuter automatiquement le programme résultant sur l’architecture distribuée ciblée.

Pendant sont stage, Emile Cadorel a développé une bibliothèque de squelettes parallèles pour la manipulation de grands graphes. L’objectif de ce stage était double, (i) manipuler efficacement les grands graphes sur des architectures distribuées et hétérogènes et (ii) permettre l’adaptabilité des programmes dynamiquement en fonction des ressources matérielles disponibles dans le système et de critères définis par l’utilisateur (performance, consommation énergétique). Le prototype réalisé est disponible.

Pendant son stage Nicolas Serrette a établi une comparaison des framework existants de calculs sur les grands graphes. Samy Ouzerrout a travaillé à une surcouche de style fonctionnel pour le framework MapReduce. Igor Zhirkov a travaillé à une formalisation de la bibliothèque de programmation parallèle BSPlib, utilisée notamment pour l’implantation d’algorithme parallèles sur des graphes distribués. Jolan Philippe a développé un formalization du DSL Fregel à l’aide de l’assistant de preuve Coq. Finalement une formalisation d’algorithmes de recherche de motifs fréquents a été conduite avec l’assistant de preuve Coq: des algorithmes de plus en plus efficaces ont été obtenus par des techniques de transformation de programmes.

4 - Protection de la vie privée

Le travail a principalement été centré sur l’étude d’une métrique d’influence dans les graphes, la coreness. Nous avons travaillé à l’extension d’un algorithme P2P de calcul de coreness pour:

Ces deux contributions ont été implantées dans un logiciel développé en Java: DPCore.

Les problèmes de protection de la vie privée apparaissent en particulier dans le cadre de réseau sociaux. Dans le cadre de leur stage, Manal Ibrik et Sarah Kobar ont conçu et développé un logiciel de simulation réaliste de réseau social à large échelle.

Au niveau théorique, les systèmes de catégorisation sont largement étudiés en psychologie, en sociologie et en théorie de l’organisation en tant que dispositifs de structuration de l’information qui sont essentiels aux processus décisionnels. Nous avons introduit une logique épistémique correcte et complète de perception catégorique des catégories et des agents. Nous avons prooposé une sémantique basée sur les graphes utilisant des multigraphes bipartites étiquetés.