Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 426-433.DOI: 10.11772/j.issn.1001-9081.2019081605

• CCF NDBC 2019 • Previous Articles     Next Articles

Optimized algorithm for k-step reachability queries on directed acyclic graphs

Ming DU1, Anping YANG1, Junfeng ZHOU1(), Ziyang CHEN2, Yun YANG1   

  1. 1.School of Computer Science and Technology,Donghua University,Shanghai 201620,China
    2.School of Information Management,Shanghai Lixin University of Accounting and Finance,Shanghai 201620,China
  • Received:2019-08-16 Revised:2019-09-23 Accepted:2019-10-24 Online:2019-10-31 Published:2020-02-10
  • Contact: Junfeng ZHOU
  • About author:DU Ming, born in 1975, Ph. D., associate professor. His research interests include information retrieval, data analysis and mining, natural language processing.
    YANG Anping, born in 1994, M. S. candidate. His research interests include query processing and optimization of graph data.
    CHEN Ziyang, born in 1973, Ph. D., professor. His research interests include computation theory, query processing, optimization of graph data.
    YANG Yun, born in 1995, M. S. candidate. Her research interests include query processing and optimization of graph data.


杜明1, 杨安平1, 周军锋1(), 陈子阳2, 杨云1   

  1. 1.东华大学 计算机科学与技术学院,上海 201620
    2.上海立信会计金融学院 信息管理学院,上海 201620
  • 通讯作者: 周军锋
  • 作者简介:杜明(1975—),男,黑龙江虎林人,副教授,博士,主要研究方向:信息检索、数据分析和挖掘、自然语言处理


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.

Key words: Directed Acyclic Graph (DAG), k-step reachability query, hop point shortest path index, bi-directional reversed topological index, bi-traversal



关键词: 有向无环图, k步可达性查询, hop点最短路径索引, 双向互逆拓扑索引, 双向遍历

CLC Number: