期刊文献+

有向无环图上k步可达查询优化算法 被引量:5

Optimized algorithm for k-step reachability queries on directed acyclic graphs
下载PDF
导出
摘要 k步可达查询用于在给定的有向无环图(DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集(如引用网络、社交网络等)的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。 The k-step reachability query is used to answer whether there exists a path between two nodes with length no longer than k in a Directed Acyclic Graph(DAG).Concerning the problems of large index size and low query processing efficiency of existing approaches,a bi-directional shortest path index based on partial nodes was proposed to improve the coverage of reachable queries,and a set of optimization rules was proposed to reduce the index size.Then,a bi-directional reversed topological index was proposed to accelerate the unreachable queries answering based on the simplified graph.Finally,the farthest-node-first-visiting bi-traversal strategy was proposed to improve the efficiency of query processing.Experimental results on 21 real datasets,such as citation networks and social networks,show that compared with existing efficient approaches including PLL(Pruned Landmark Labeling)and BFSI-B(Breadth First Search Index-Bilateral),the proposed algorithm has smaller index size and higher query response speed.
作者 杜明 杨安平 周军锋 陈子阳 杨云 DU Ming;YANG Anping;ZHOU Junfeng;CHEN Ziyang;YANG Yun(School of Computer Science and Technology,Donghua University,Shanghai 201620,China;School of Information Management,Shanghai Lixin University of Accounting and Finance,Shanghai 201620,China)
出处 《计算机应用》 CSCD 北大核心 2020年第2期426-433,共8页 journal of Computer Applications
关键词 有向无环图 k步可达性查询 hop点最短路径索引 双向互逆拓扑索引 双向遍历 Directed Acyclic Graph(DAG) k-step reachability query hop point shortest path index bi-directional reversed topological index bi-traversal
  • 相关文献

同被引文献28

引证文献5

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部