Leveraging efficient indexing schema to support multigraph query answering

Autor: Ienco, Dino, Ingalalli, Vijay, Poncelet, Pascal
Přispěvatelé: Territoires, Environnement, Télédétection et Information Spatiale (UMR TETIS), Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-AgroParisTech-Centre National de la Recherche Scientifique (CNRS), ADVanced Analytics for data SciencE (ADVANSE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), ANR-10-LABX-0020/10-LABX-0020,NUMEV,Digital and Hardware Solutions and Modeling for the Environement and Life Sciences(2010), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-AgroParisTech-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-10-LABX-0020,NUMEV,Digital and Hardware Solutions and Modeling for the Environement and Life Sciences(2010)
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: Revue des Sciences et Technologies de l'Information-Série ISI : Ingénierie des Systèmes d'Information
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⟩
ISSN: 1633-1311
DOI: 10.3166/isi.21.3.53-74⟩
Popis: International audience; 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.; 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.
Databáze: OpenAIRE
Externí odkaz: