Supervision : Mesaac MAKPANGOU

Co-supervision : NDIAYE Samba

Freecore : un système d’indexation de résumés de document sur une Table de Hachage Distribuée (DHT)

Cette thèse étudie la problématique de l’indexation et de la recherche dans les tables de hachage distribuées (Distributed Hash Table --DHT). Elle propose un système de stockage distribué des résumés de documents en se basant sur leur contenu. Concrètement, la thèse utilise les Filtres de Blooms (FBs) pour représenter les résumés de documents et propose une méthode efficace d’insertion et de récupération des documents représentés par des FBs dans un index distribué sur une DHT. Le stockage basé sur contenu présente un double avantage, il permet de regrouper les documents similaires afin de les retrouver plus rapidement et en même temps, il permet de retrouver les documents en faisant des recherches par mots-clés en utilisant un FB. Cependant, la résolution d’une requête par mots-clés représentée par un filtre de Bloom constitue une opération complexe, il faut un mécanisme de localisation des filtres de Bloom de la descendance qui représentent des documents stockés dans la DHT.
Ainsi, la thèse propose dans un deuxième temps, deux index de filtres de Bloom distribués sur des DHTs. Le premier système d’index proposé combine les principes d’indexation basée sur contenu et de listes inversées et répond à la problématique liée à la grande quantité de données stockée au niveau des index basés sur contenu. En effet, avec l’utilisation des filtres de Bloom de grande longueur, notre solution permet de stocker les documents sur un plus grand nombre de serveurs et de les indexer en utilisant moins d’espace.
Ensuite, la thèse propose un deuxième système d’index qui supporte efficacement le traitement des requêtes de sur-ensembles (des requêtes par mots-clés) en utilisant un arbre de préfixes. Cette dernière solution exploite la distribution des données et propose une fonction de répartition paramétrable permettant d’indexer les documents avec un arbre binaire équilibré. De cette manière, les documents sont répartis efficacement sur les serveurs d’indexation. En outre, la thèse propose dans la troisième solution, une méthode efficace de localisation des documents contenant un ensemble de mots-clés donnés. Comparé aux solutions de même catégorie, cette dernière solution permet d’effectuer des recherches de sur-ensembles en un moindre coût et constitue est une base solide pour la recherche de sur-ensembles sur les systèmes d’index construits au-dessus des DHTs.
Enfin, la thèse propose le prototype d’un système pair-à-pair pour l’indexation de contenus et la recherche par mots-clés. Ce prototype, prêt à être déployé dans un environnement réel, est expérimenté dans l’environnement de simulation peersim qui a permis de mesurer les performances théoriques des algorithmes développés tout au long de la thèse.

2012-2018 Publications

• 2018
  • B. Ngom : “Freecore : un système d’indexation de résumés de document sur une Table de Hachage Distribuée (DHT)”, thesis, phd defence 07/13/2018, supervision Makpangou, Mesaac, co-supervision : Ndiaye, Samba (2018)
  • B. Ngom, M. Makpangou, S. Ndiaye : “SPT – Summary Prefix Tree: An over DHT Indexing Data Structure for Efficient Superset Search”, (2018)
• 2017
  • B. Ngom, M. Makpangou : “Summary Prefix Tree: An over DHT Indexing Data Structure for Efficient Superset Search”, NCA 2017 - 16^th IEEE International Symposium on Network Computing and Applications, Cambridge, MA, United States, pp. 1-5 (2017)
• 2014
  • M. Makpangou, B. Ngom, S. Ndiaye : “FreeCore : Un substrat d’indexation des filtres de Bloom fragmentés pour la recherche par mots clés”, ComPAS'2014, Neuchâtel, Switzerland (2014)
• 2012
  • M. Makpangou, B. Ngom, S. Ndiaye : “Friticores: A RSS Feed Monitoring and Dissemination System”, AFRICOMM 2012 - Fourth International IEEE EAI Conference on e-Infrastructure and e‐Services for Developing Countries, Yaounde, Cameroon (2012)