Integrating Connection Search in Graph Queries - Département d'informatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Integrating Connection Search in Graph Queries

Intégration de la recherche de connexion dans les requêtes de graphique

Résumé

When graph database users explore unfamiliar graphs, potentially with heterogeneous structure, users may need to find how two or more groups of nodes are connected in a graph, even when users are not able to describe the connections. This is only partially supported by existing query languages, which allow searching for paths, but not for trees connecting three or more node groups. In this work, we formally show how to integrate connecting tree patterns (CTPs, in short) with a graph query language such as GPML, SPARQL or Cypher, leading to Extended Queries (or EQs, in short). We then study a set of algorithms for evaluating CTPs; we generalize prior keyword search work to be complete, most importantly by (i) considering bidirectional edge traversal, (ii) allowing users to select any score function for ranking CTP results and (iii) returning all results. To cope with very large search spaces, we propose efficient pruning techniques and formally establish a large set of cases where our best algorithm, MOLESP, is complete even with pruning. Our experiments validate the performance of our algorithms on many synthetic and real-world workloads.
Fichier principal
Vignette du fichier
icde2023.pdf (650.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04110779 , version 1 (30-05-2023)

Identifiants

  • HAL Id : hal-04110779 , version 1

Citer

Angelos Christos Anadiotis, Ioana Manolescu, Madhulika Mohanty. Integrating Connection Search in Graph Queries. ICDE 2023 - 39th IEEE International Conference on Data Engineering, Apr 2023, Anaheim (CA), United States. ⟨hal-04110779⟩
37 Consultations
53 Téléchargements

Partager

Gmail Facebook X LinkedIn More