Large-scale data management in real-world graphs

Résumé : De nos jours, un grand nombre d’applications utilisent de grands graphes pour la modélisation de données du monde réel. Nous avons assisté, ces dernières années, à une très rapide croissance de ces graphes dans divers contextes ; à savoir, les réseaux sociaux, la bioinformatique, le web sémantique, les systèmes de gestion des données géographiques, etc. La gestion, l’analyse et l’interrogation de ces données constituent un enjeu très important et ont suscité un vaste intérêt dans la communauté des Bases de Données. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’indexation et l’interrogation des données dans les grands graphes. Nous avons proposé EUQLID, une technique d’indexation qui permet de répondre efficacement aux requêtes de calcul de distance dans les grands graphes orientés. L’efficacité de cette technique est dûe au fait qu’elle exploite des propriétés intéressantes des graphes du monde réel. En effet, nous proposons un algorithme basé sur une variante efficace du fameux algorithme 2-hop. Les résultats obtenus montrent que notre algorithme surpassent les approches existantes en terme de temps d’indexation, ainsi qu’en temps de réponse. En effet, il permet de calculer la distance entre deux noeuds en quelques centaines de millisecondes sur de très grands graphes. Nous proposons également un modèle de contrôle d’accès pour les réseaux sociaux qui permet aux utlisateurs de spécifier leurs poltiques de contrôle d’accès en se basant sur leurs relations sociales, et qui peut utiliser EUQLID pour passer à l’échelle. Nous décrivons Primates comme étant un prototype appliquant le modèle proposé.
Mots-clés : Sécurité
Type de document :
Thèse
Data Structures and Algorithms [cs.DS]. Télécom ParisTech, 2013. English. 〈NNT : 2013ENST0087〉
Liste complète des métadonnées

Littérature citée [90 références]  Voir  Masquer  Télécharger

https://pastel.archives-ouvertes.fr/tel-01307470
Contributeur : Abes Star <>
Soumis le : mardi 26 avril 2016 - 15:12:07
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : mercredi 27 juillet 2016 - 14:42:00

Fichier

TheseBenDhiaV2.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01307470, version 1

Citation

Imen Ben Dhia. Large-scale data management in real-world graphs. Data Structures and Algorithms [cs.DS]. Télécom ParisTech, 2013. English. 〈NNT : 2013ENST0087〉. 〈tel-01307470〉

Partager

Métriques

Consultations de la notice

216

Téléchargements de fichiers

87