Research and Optimization of Reachability Query Algorithm with Limited Hop on Big Graph
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [26]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    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.

    Reference
    [1] 杨晓冬. 大图上的K跳可达性查询算法[硕士学位论文]. 武汉: 华中科技大学, 2016.
    [2] Cheng JF, Yu JX. On-line exact shortest distance query processing. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. Saint Petersburg: ACM, 2009. 481–492.
    [3] Cheng J, Shang ZC, Cheng H, et al. K-reach: Who is in your small world. Proceedings of the VLDB Endowment, 2012, 5(11): 1292–1303. [doi: 10.14778/2350229.2350247
    [4] BIG Data Center Members. The BIG Data Center: From deposition to integration to translation. Nucleic Acids Research, 2017, 45(D1): D18–D24. [doi: 10.1093/nar/gkw1060
    [5] Chen W, Sommer C, Teng SH, et al. A compact routing scheme and approximate distance oracle for power-law graphs. ACM Transactions on Algorithms, 2012, 9(1): 4
    [6] Wang HX, He H, Yang J, et al. Dual labeling: Answering graph reachability queries in constant time. 22nd International Conference on Data Engineering. Atlanta: IEEE, 2006. 75.
    [7] Trißl S, Leser U. Fast and practical indexing and querying of very large graphs. Proceedings of The 2007 ACM SIGMOD International Conference on Management of Data (SIGMOD’07). Beijing: ACM, 2007. 845–856.
    [8] Jagadish HV. A compression technique to materialize transitive closure. ACM Transactions on Database Systems, 1990, 15(4): 558–598. [doi: 10.1145/99935.99944
    [9] Jin RM, Xiang Y, Ruan N, et al. 3-Hop: A high-compression indexing scheme for reachability query. Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. Rhode Island: Association for Computing Machinery, 2009. 813–826.
    [10] Yildirim H, Chaoji V, Zaki MJ. GRAIL: Scalable reachability index for large graphs. Proceedings of the VLDB Endowment, 2010, 3(1–2): 276–284. [doi: 10.14778/1920841.1920879
    [11] Guo YF, Qin Z, Chang Y. A novel hybrid algorithm for the dynamic shortest path problem. Sixth International Conference on Natural Computation. Yantai: IEEE, 2010. 2545–2550.
    [12] Abraham I, Delling D, Goldberg AV, et al. Hierarchical hub labelings for shortest paths. 20th Annual European Symposium on Algorithms. Berlin Heidelberg: Springer, 2012. 24–35.
    [13] Piccardi M. Background subtraction techniques: A review. IEEE International Conference on Systems, Man and Cybernetics. The Hague: IEEE, 2004. 3099–3104.
    [14] Cohen E, Halperin E, Kaplan H, et al. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 2003, 32(5): 1338–1355. [doi: 10.1137/S0097539702403098
    [15] Cai J, Poon CK. Path-hop: Efficiently indexing large graphs for reachability queries. Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto: Association for Computing Machinery, 2010. 119–128.
    [16] Wei H, Yu JX, Lu C, et al. Reachability querying: An independent permutation labeling approach. The VLDB Journal, 2018, 27(1): 1–26. [doi: 10.1007/s00778-017-0468-3
    [17] D’Andrea A, D’Emidio M, Frigioni D, et al. Experimental evaluation of dynamic shortest path tree algorithms on homogeneous batches. 13th International Symposium on Experimental Algorithms. Cham: Springer, 2014. 283–294.
    [18] Akiba T, Iwata Y, Yoshida Y. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: Association for Computing Machinery, 2013. 349–360.
    [19] Akiba T, Sommer C, Kawarabayashi KI. Shortest-path queries for complex networks: Exploiting low tree-width outside the core. Proceedings of the 15th International Conference on Extending Database Technology. Berlin: Association for Computing Machinery, 2012. 144–155.
    [20] Cheng J, Huang SL, Wu HH, et al. TF-Label: A topological-folding labeling scheme for reachability querying in a large graph. ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013. 193–204.
    [21] Hay M, Miklau G, Jensen D, et al. Resisting structural re-identification in anonymized social networks. Proceedings of the VLDB Endowment, 2008, 1(1): 102–114. [doi: 10.14778/1453856.1453873
    [22] Cheng J, Shang ZC, Cheng H, et al. Efficient processing of k-hop reachability queries. The VLDB Journal, 2014, 23(2): 227–252. [doi: 10.1007/s00778-013-0346-6
    [23] 周军锋, 陈伟, 费春苹, 等. BiRch: 一种处理k步可达性查询的双向搜索算法. 通信学报, 2015, 36(8): 50–60. [doi: 10.11959/j.issn.1000-436x.2015230
    [24] 李鸣鹏, 高宏, 邹兆年. 基于图压缩的k可达查询处理. 软件学报, 2014, 25(4): 797–812. [doi: 10.13328/j.cnki.jos.004567
    [25] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth. Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Brussels: IEEE, 2012. 745–754.
    [26] Li WT, Qiao M, Qin L, et al. Scaling distance labeling on small-world networks. Proceedings of the 2019 International Conference on Management of Data. Amsterdam: Association for Computing Machinery, 2019. 1060–1077.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

邢耕源,徐云.大图上跳数受限的可达查询算法研究与优化.计算机系统应用,2021,30(10):164-170

Copy
Share
Article Metrics
  • Abstract:840
  • PDF: 1923
  • HTML: 1655
  • Cited by: 0
History
  • Received:January 11,2021
  • Revised:February 23,2021
  • Online: October 08,2021
Article QR Code
You are the first990354Visitors
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) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063