Integrating connection search in graph queries

• URL: http://arxiv.org/abs/2208.04802v1
• Date: Tue, 9 Aug 2022 14:27:57 GMT
• Title: Integrating connection search in graph queries
• Authors: Angelos Christos Anadiotis and Ioana Manolescu and Madhulika Mohanty
• Abstract summary: We show how to integrate connecting tree patterns (CTPs) within a graph query language such as SPARQL or Cypher. 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.
• Score: 6.948362325254044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 work, we formally show how to integrate connecting tree patterns (CTPs, in short) within a graph query language such as SPARQL or Cypher, leading to an Extended Query Language (or EQL, in short). We then study a set of algorithms for evaluating CTPs; we generalize 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. Our experiments validate the performance of our CTP and EQL evaluation algorithms on a large set of synthetic and real-world workloads.

Related papers

• DAGE: DAG Query Answering via Relational Combinator with Logical Constraints [24.60431781360608]
  We propose a query embedding method for DAG queries called DAGE. DAGE combines the possibly multiple paths between two nodes into a single path with a trainable operator. We show that it is possible to implement DAGE on top of existing query embedding methods.
  arXiv  Detail & Related papers  (2024-10-29T15:02:48Z)
• NL2KQL: From Natural Language to Kusto Query [1.7931930942711818]
  NL2KQL is an innovative framework that uses large language models (LLMs) to convert natural language queries (NLQs) to Kusto Query Language (KQL) queries. To validate NL2KQL's performance, we utilize an array of online (based on query execution) and offline (based on query parsing) metrics.
  arXiv  Detail & Related papers  (2024-04-03T01:09:41Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Improving Text-to-SQL Semantic Parsing with Fine-grained Query Understanding [84.04706075621013]
  We present a general-purpose, modular neural semantic parsing framework based on token-level fine-grained query understanding. Our framework consists of three modules: named entity recognizer (NER), neural entity linker (NEL) and neural entity linker (NSP)
  arXiv  Detail & Related papers  (2022-09-28T21:00:30Z)
• Graph Enhanced BERT for Query Understanding [55.90334539898102]
  query understanding plays a key role in exploring users' search intents and facilitating users to locate their most desired information. In recent years, pre-trained language models (PLMs) have advanced various natural language processing tasks. We propose a novel graph-enhanced pre-training framework, GE-BERT, which can leverage both query content and the query graph.
  arXiv  Detail & Related papers  (2022-04-03T16:50:30Z)
• Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints [10.842138336245384]
  We propose a native hybrid query (NHQ) framework based on proximity graph (PG), which provides the specialized textitcomposite index and joint pruning modules for hybrid queries. We present two novel navigable PGs with optimized edge selection and routing strategies, which obtain better overall performance than existing PGs.
  arXiv  Detail & Related papers  (2022-03-25T12:02:37Z)
• Improving Candidate Retrieval with Entity Profile Generation for Wikidata Entity Linking [76.00737707718795]
  We propose a novel candidate retrieval paradigm based on entity profiling. We use the profile to query the indexed search engine to retrieve candidate entities. Our approach complements the traditional approach of using a Wikipedia anchor-text dictionary.
  arXiv  Detail & Related papers  (2022-02-27T17:38:53Z)
• Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
  Graph Query Expansion (GQE) is presented, which is learned in a supervised manner and performs aggregation over an extended neighborhood of the query. The technique achieves state-of-the-art results over known benchmarks.
  arXiv  Detail & Related papers  (2021-12-05T19:48:42Z)
• Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graph [16.26384829957165]
  We propose a new two-stage approach to build query graphs. In the first stage, the top-$k$ related instances are collected by simple strategies. In the second stage, a graph generation model performs hierarchical generation.
  arXiv  Detail & Related papers  (2021-11-01T07:08:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.