Skip to Main content Skip to Navigation
Journal articles

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
Résumé : De nombreuses données réelles peuvent être représentées par un réseau avec un ensemble de nœuds interconnectés via différentes relations (i.e. les réseaux sociaux, les données biologiques, les graphes RDF). Ce type de graphe, appelé multigraphe, est tout à fait adapté à la représentation de scénarios réels contenant des interactions complexes. La recherche de sousmultigraphe dans des multigraphes est un domaine de recherche ouvert et malheureusement les algorithmes existants pour faire de la recherche de sous-graphe ne sont pas adaptés et ne peuvent pas prendre en compte les différentes relations qui peuvent exister entre les nœuds. Motivés par le manque d’approches existantes et par le nombre croissant d’applications qui peuvent être modélisées via des multigraphes, nous proposons dans cet article IMQA un nouvel algorithme pour extraire tous les sous-multigraphes inclus dans un grand multigraphe. IMQA comporte deux étapes principales. Tout d’abord il implémente une nouvelle structure d’indexation pour les relations multiples qui est utilisée pour rechercher efficacement les sommets du multigraphe qui correspondent aux sommets de la requête. Ensuite, il réalise une recherche efficace de Ingénierie des systèmes d’information – no 3/2016, 53-74 54 ISI. Volume 21 – no 3/2016 l’ensemble des sous-multigraphes correspondant à une requête donnée. Les nombreuses expérimentations menées sur des jeux de données réelles ont montré l’efficacité et le passage à l’échelle de 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 : Thursday, July 2, 2020 - 2:01:37 PM
Document(s) archivé(s) le : 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

444

Files downloads

362