SuMGra: Querying Multigraphs via Efficient Indexing

Vijay Ingalalli 1, 2 Dino Ienco 1, 2 Pascal Poncelet 2
2 ADVANSE - ADVanced Analytics for data SciencE
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Many real world datasets can be represented by a network with a set of nodes interconnected with each other by multiple relations. Such a rich graph is called a multigraph. Unfortunately, all the existing algorithms for subgraph query matching are not able to adequately leverage multiple relationships that exist between the nodes. In this paper we propose an efficient indexing schema for querying single large multi-graphs, where the indexing schema aptly captures the neighbourhood structure in the data graph. Our proposal SuMGra couples this novel indexing schema with a subgraph search algorithm to quickly traverse though the solution space to enumerate all the matchings. Extensive experiments conducted on real benchmarks prove the time efficiency as well as the scalability of SuMGra.
Type de document :
Communication dans un congrès
DEXA: Database and Expert Systems Applications, Sep 2016, Porto, Portugal. 27th International Conference on Database and Expert Systems Applications - Proceedings, Part I, LNCS (9827), pp.387-401, 2016, Database and Expert Systems Applications. 〈10.1007/978-3-319-44403-1_24〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01362431
Contributeur : Pascal Poncelet <>
Soumis le : jeudi 8 septembre 2016 - 17:14:01
Dernière modification le : jeudi 24 mai 2018 - 15:59:25
Document(s) archivé(s) le : vendredi 9 décembre 2016 - 13:18:08

Fichier

Paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Vijay Ingalalli, Dino Ienco, Pascal Poncelet. SuMGra: Querying Multigraphs via Efficient Indexing. DEXA: Database and Expert Systems Applications, Sep 2016, Porto, Portugal. 27th International Conference on Database and Expert Systems Applications - Proceedings, Part I, LNCS (9827), pp.387-401, 2016, Database and Expert Systems Applications. 〈10.1007/978-3-319-44403-1_24〉. 〈lirmm-01362431〉

Partager

Métriques

Consultations de la notice

130

Téléchargements de fichiers

137