Scholarlink

<p>Reachability query is a fundamental operation in graph applications, including social network analysis, knowledge graph based NLP. Current <i>label+G</i> solutions tend to directly answer reachability queries between near vertices. When two vertices are far apart, they have to traverse the graph, which is time consuming. In this work, we propose a multi-dimensional labeling method called TDS to support fast reachability queries. Firstly, we order the vertices with zero-indegree and traverse the graph from them in forward and reverse order to generate two traversal trees. Furthermore, we assign each vertex in a tree two labels, which indicate the level and subgraph it belongs to. With the four labels, many reachability queries for far apart and near pairs can be answered quickly. Experiments on 16 real graphs demonstrate TDS achieves better query performance in a majority of used graphs versus the state-of-the-art, while it consumes near-linear time and space for indexing.</p>

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

TDS: fast answering reachability queries with hierarchical traversal trees

  • 期刊论文

  • 发表日期：

    2025年1月21日

查看全文
  • Daoliang He,
  • Pingpeng Yuan

摘要

Reachability query is a fundamental operation in graph applications, including social network analysis, knowledge graph based NLP. Current label+G solutions tend to directly answer reachability queries between near vertices. When two vertices are far apart, they have to traverse the graph, which is time consuming. In this work, we propose a multi-dimensional labeling method called TDS to support fast reachability queries. Firstly, we order the vertices with zero-indegree and traverse the graph from them in forward and reverse order to generate two traversal trees. Furthermore, we assign each vertex in a tree two labels, which indicate the level and subgraph it belongs to. With the four labels, many reachability queries for far apart and near pairs can be answered quickly. Experiments on 16 real graphs demonstrate TDS achieves better query performance in a majority of used graphs versus the state-of-the-art, while it consumes near-linear time and space for indexing.