Research and Optimization of Reachability Query Algorithm with Limited Hop on Big Graph

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments

    It is a classic problem to judge whether there is a path between two vertices in a directed graph. For some practical applications such as routing and graph analysis, it is required to find whether there is a reachable path with limited hops, which is a variant of reachability query in graphs. For the query algorithm with limited hops on a large graph, it is necessary to balance the time and space efficiency of large-graph query and optimize the algorithm with the characteristics of limited hops. The common reachability query algorithm takes up too much space for small-degree vertex index entries, which leads to serious space waste. Therefore, we propose a hop-limited 2-hop partial index method, which combines an improved index method with local search to achieve hop-limited effective reachability query. The experimental results show that, compared with the existing algorithms, the proposed algorithm can save 32% index space and slightly increase query time on the Orkut social network dataset. Thus, the proposed algorithm can calculate the hop-limited reachability problem of larger graphs.

    Cited by
Get Citation


Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
  • Received:January 11,2021
  • Revised:February 23,2021
  • Adopted:
  • Online: October 08,2021
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a)
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063