Scholarlink

<p>Answering reachability queries is a fundamental operation in graph theory. Existing methods either build an index for partial reachability, which may lead to costly graph traversal during query processing, or construct an index for complete reachability, which can be inefficient when handling queries involving unreachable vertex pairs, as it requires comparing full vertex labels. Most reachability methods focus on regular directed acyclic graphs (DAGs). In this paper, we introduce Mix Labeling for Reachability Queries (MLRQ), a novel approach specifically designed for reduced DAGs, which preserve the essential structural properties of regular DAGs while being smaller. MLRQ utilizes topological labels consisting of two integers to filter a considerable portion of unreachable vertex pairs effectively. Additionally, MLRQ incorporates 2-hop labels and spanning tree intervals to cover the complete reachability relationship, thereby improving query efficiency and avoiding graph traversal. We also propose optimization strategies to further improve performance. Our experimental results demonstrate that MLRQ performs optimally in answering reachability queries for the majority of graphs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

MLRQ: an efficient labeling scheme for reachability queries on reduced DAGs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月11日

查看全文
  • Haiyan Zhang,
  • Keng Hoon Gan,
  • Shengping Yang

摘要

Answering reachability queries is a fundamental operation in graph theory. Existing methods either build an index for partial reachability, which may lead to costly graph traversal during query processing, or construct an index for complete reachability, which can be inefficient when handling queries involving unreachable vertex pairs, as it requires comparing full vertex labels. Most reachability methods focus on regular directed acyclic graphs (DAGs). In this paper, we introduce Mix Labeling for Reachability Queries (MLRQ), a novel approach specifically designed for reduced DAGs, which preserve the essential structural properties of regular DAGs while being smaller. MLRQ utilizes topological labels consisting of two integers to filter a considerable portion of unreachable vertex pairs effectively. Additionally, MLRQ incorporates 2-hop labels and spanning tree intervals to cover the complete reachability relationship, thereby improving query efficiency and avoiding graph traversal. We also propose optimization strategies to further improve performance. Our experimental results demonstrate that MLRQ performs optimally in answering reachability queries for the majority of graphs.