Madhulika Mohanty will present her work on July 20th at 2:30PM.
It will be online at https://ecolepolytechnique.zoom.us/j/7051282821?pwd=WTlXcy9jei9rUDJvMXI5c2pzamFGQT09
Title
Integrating connection search in graph queries
Abstract
Graph data management and querying has many practical applications. When graphs are very heterogeneous and/or users are unfamiliar with their structure, they 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. The latter is related to the NP-hard Group Steiner Tree problem, and has been previously considered for keyword search in databases. In this talk, I will present the joint work with Angelos Anadiotis and Ioana Manolescu, where we formally show how to integrate connecting tree patterns (CTPs) within a graph query language such as SPARQL or Cypher, thus, leading to an Extended Query Language (EQL). We will also discuss a set of algorithms for evaluating CTPs. In particular, our problem generalizes prior keyword search work, most importantly by (i) considering bidirectional edge traversal and (ii) allowing users to select any score function for ranking CTP results. To cope with very large search spaces, we propose an efficient pruning technique and formally establish a large set of cases where our algorithm, MoLESP, is complete even with pruning. I will also discuss our experiments which validate the performance of our CTP and EQL evaluation algorithms on a large set of synthetic and real-world workloads.
Bio
Madhulika Mohanty is a postdoc in the CEDAR Team at Inria, Saclay. Prior to that, she was an Assistant Professor at IIT Dhanbad, India. She obtained her PhD from IIT Delhi in 2020 on the topic of “Techniques for effective search and exploration over Knowledge Graphs”. Her research interests are in Algorithms for Querying Graphs and Information Retrieval.
