$HT$ : A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs
$HT$ : A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs
复制标题
DOI：
10.1109/access.2019.2956557
复制
发表时间：
2019
期刊：
影响因子：
3.9
通讯作者：
Ming Du;Anping Yang;Junfeng Zhou;Xian Tang;Ziyang Chen;Yanfei Zuo
中科院分区：
文献类型：
--
作者：
Ming Du;Anping Yang;Junfeng Zhou;Xian Tang;Ziyang Chen;Yanfei Zuo
给定一个有向无环图（DAG），使用$k$ -hop可达性查询${u}\xrightarrow {?k}{v}$来回答是否存在从$u$到$v$的长度为$\leq k$的路径。回答$k$ -hop可达性查询是一种基本的图操作，在过去的几年里得到了广泛的研究。考虑到现有方法在实际处理大型图时仍然存在效率低下的问题，我们提出了一种新的标记方案，即HT，以加速$k$ -hop可达性查询的应答。HT使用约束的2hop距离标签来维持一组hop节点与其他节点之间的最短路径长度，对于剩余的可达性信息，HT使用新的拓扑级别来加速图的遍历。此外，我们建议通过两种优化技术来增强HT。实验结果表明，与最先进的方法相比，HT在回答$k$ -hop可达性查询时效果最好，且索引大小较小，索引构建时间合理。
Given a directed acyclic graph (DAG), a $k$ -hop reachability query ${u}\xrightarrow {?k}{v}$ is used to answer whether there exists a path from $u$ to $v$ with length $\leq k$ . Answering $k$ -hop reachability queries is a fundamental graph operation and has been extensively studied during the past years. Considering that existing approaches still suffer from inefficiency in practice when processing large graphs, we propose a novel labeling scheme, namely HT, to accelerate $k$ -hop reachability queries answering. HT uses a constrained 2hop distance label to maintain the length of shortest paths between a set of hop nodes and other nodes, and for the remaining reachability information, HT uses a novel topological level to accelerate graph traversal. Further, we propose to enhance HT by two optimization techniques. The experimental results show that compared with the state-of-the-art approaches, HT works best for most graphs when answering $k$ -hop reachability queries with small index size and reasonable index construction time.