Leveraging efficient indexing schema to support multigraph query answering

Dino Ienco 1, 2 Vijay Ingalalli 2, 1 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 graphs with a set of nodes intercon- nected with each other by multiple relations (e.g., social network, RDF graph, biological data). Such a rich graph, called multigraph, is well suited to represent real world scenarios with com- plex interactions. However, performing subgraph query on multigraphs is still an open issue since, unfortunately, all the existing algorithms for subgraph query matching are not able to ad- equately leverage the multiple relationships that exist between the nodes. Motivated by the lack of approaches for sub-multigraph query and stimulated by the increasing number of datasets that can be modelled as multigraphs, in this paper we propose IMQA (Index based Multigraph Query Answering), a novel algorithm to extract all the embeddings of a sub-multigraph query from a single large multigraph. IMQA is composed of two main phases: Firstly, it implements a novel indexing schema for multiple edges, which will help to efficiently retrieve the vertices of the multigraph that match the query vertices. Secondly, it performs an efficient subgraph search to output the entire set of embeddings for the given query. Extensive experiments conducted on real datasets prove the time efficiency as well as the scalability of IMQA.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01399606
Contributor : Dino Ienco <>
Submitted on : Saturday, November 3, 2018 - 7:52:50 PM
Last modification on : Wednesday, September 18, 2019 - 4:04:05 PM
Long-term archiving on : Monday, February 4, 2019 - 12:39:49 PM

File

4033943f5c5a81f5632a491a39bb8a...
Publisher files allowed on an open archive

Identifiers

Citation

Dino Ienco, Vijay Ingalalli, Pascal Poncelet. Leveraging efficient indexing schema to support multigraph query answering. Revue des Sciences et Technologies de l'Information - Série ISI : Ingénierie des Systèmes d'Information, Lavoisier, 2016, 21 (3), pp.53-74. ⟨10.3166/isi.21.3.53-74⟩. ⟨lirmm-01399606⟩

Share

Metrics

Record views

335

Files downloads

114