Reachability Algorithm Based on Key Points Labeling for Sparse Graphs

doi:10.3778/j.issn.1673-9418.2212016

Abstract

Abstract: Reachability queries of directed graphs are fundamental when studying various network problems, such as querying whether two persons follow each other in a social network. However, with the increasing size of networks, traditional algorithms have become unacceptable due to their huge time or space complexity. Therefore, it is necessary to use a suitable reachability algorithm according to the structural characteristics of the network. A sparse graph consists of several directed spanning trees with a small number of non-tree edges. The GRKPL (graph reachability indexing via key points labeling) algorithm splits the reachability problem in sparse graphs into two parts: the tree reachability problem and the impact of adding non-tree edges. The first part is solved by the interval labeling method, and the second part is solved by constructing a key point set, which transforms all the reachability queries in the original graph into queries in the key point set. The key point set includes all nodes covered by non-tree edges and the lowest common ancestors between adjacent nodes after these nodes are sorted in the preorder traversal order. And it is proven that the size of the key point set is of the same order of magnitude as the size of the non-tree edges in the original graph. Finally, GRKPL is tested on ten small- and medium-scale and four large-scale realistic datasets. GRKPL performs well on small- and medium-scale datasets, with an average 49.8% reduction in query processing time and 65.1% reduction in space occupation compared to other algorithms.

Key words: reachability, sparse graphs, directed graphs, strongly connected components, lowest common ancestor, bitwise operations

摘要： 有向图中任意两点间的可达性查询是研究各种网络问题时的一个基础操作，如在社交网络中查询两个人是否相互关注等。但随着网络规模的日益扩大，传统算法因巨大的时间或空间复杂度而变得难以被应用。因此需要根据网络结构特点针对性地使用合适的可达性算法。稀疏图可以看作由若干有向生成树与少量非树边组成，GRKPL算法将稀疏图中的可达性问题拆分成两部分：树上可达性问题与加入非树边后带来的影响。前一部分使用区间标记法解决；后一部分通过构造关键点集，将原图中所有的可达性查询转化为关键点集中的查询后得以解决。关键点集包括所有被非树边覆盖的节点，以及这些节点按照前序遍历的顺序排序后相邻节点之间的最近公共祖先。证明了关键点集的大小与原图中非树边的规模具有相同的数量级。最后在10个中小规模与4个大规模现实数据集上进行了测试，GRKPL在中小规模数据集上表现优异，查询处理时间相较于其他算法平均减少49.8%，空间占用平均减少65.1%。

关键词: 可达性, 稀疏图, 有向图, 强连通, 最近公共祖先, 位运算

MIAO Weihua, WEI Hui. Reachability Algorithm Based on Key Points Labeling for Sparse Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(10): 2426-2434.

苗伟华, 危辉. 适用于稀疏图的基于关键点标记的可达性算法[J]. 计算机科学与探索, 2023, 17(10): 2426-2434.

References

[1] TESFAYE B, AUGSTEN N, PAWLIK M, et al. Speeding up reachability queries in public transport networks using graph partitioning[J]. Information Systems Frontiers, 2022, 24(1): 11-29.
[2] WU Y, CHEN J, RU Y, et al. Research on power communica-tion network planning based on information transmission reachability against cyber-attacks[J]. IEEE Systems Journal, 2021, 15(2): 2883-2894.
[3] WANG Y, YUAN Y, ZHANG W, et al. Reachability-driven influence maximization in time-dependent road-social networks[C]//Proceedings of the 38th IEEE International Conference on Data Engineering, Kuala Lumpur, May 9-12, 2022. Piscat-away: IEEE, 2022: 367-379.
[4] 李晗笑. 大规模动态图上位置查询处理的关键技术研究[D]. 天津: 天津大学, 2020.
LI H X. Research on location-based query over the large-scale dynamic graphs[D]. Tianjin: Tianjin University, 2020.
[5] 庞建成. 大图上可达查询覆盖率问题研究[D]. 上海: 东华大学, 2021.
PANG J C. Research on reachability query coverage over large graphs[D]. Shanghai: Donghua University, 2021.
[6] 赵丹枫, 林俊辰, 宋巍, 等. 低冗余计算的可达性查询保持图压缩策略[J]. 计算机应用, 2020, 40(2): 510-517.
ZHAO D F, LIN J C, SONG W, et al. Strategy with low redundant computation for reachability query preserving graph compression[J]. Journal of Computer Applications, 2020, 40(2): 510-517.
[7] WANG H, HE H, YANG J, et al. Dual labeling: answering graph reachability queries in constant time[C]//Proceedings of the 22nd International Conference on Data Engineering, Atlanta, Apr 3-8, 2006. Washington: IEEE Computer Society, 2006: 75.
[8] AGRAWAL R, BORGIDA A, JAGADISH H V. Efficient management of transitive relationships in large data and knowledge bases[J]. ACM SIGMOD Record, 1989, 18(2): 253-262.
[9] SU Z, WANG D, ZHANG X, et al. Efficient reachability query with extreme labeling filter[C]//Proceedings of the 15th ACM International Conference on Web Search and Data Mining, Tempe, Feb 21-25, 2022. New York: ACM, 2022: 966-975.
[10] FLOYD R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345.
[11] SIMON K. An improved algorithm for transitive closure on acyclic digraphs[J]. Theoretical Computer Science, 1988, 58(1): 325-346.
[12] JIN R, XIANG Y, RUAN N, et al. Efficiently answering reachability queries on very large directed graphs[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, Vancouver, Jun 10-12, 2008. New York: ACM, 2008: 595-608.
[13] COHEN E, HALPERIN E, KAPLAN H, et al. Reachability and distance queries via 2-hop labels[C]//Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, Jan 6-8, 2002. New York: ACM, 2002: 937-946.
[14] JIN R, XIANG Y, RUAN N, et al. 3-hop: a high-compression indexing scheme for reachability query[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Manage- ment of Data, Providence, Jun 29-Jul 2, 2009. New York: ACM, 2009: 813-826.
[15] SCHENKEL R, THEOBALD A, WEIKUM G. Efficient creation and incremental maintenance of the hopi index for complex XML document collections[C]//Proceedings of the 21st International Conference on Data Engineering, Tokyo, Apr 5-8, 2005. Washington: IEEE Computer Society, 2005: 360-371.
[16] ZHU A D, LIN W, WANG S, et al. Reachability queries on large dynamic graphs: a total order approach[C]//Proceedings of the 2014 International Conference on Management of Data, Snowbird, Jun 22-27, 2014. New York: ACM, 2014: 1323-1334.
[17] CHENG J, HUANG S, WU H, et al. TF-label: a topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD Inter-national Conference on Management of Data, New York,Jun 22-27, 2013. New York: ACM, 2013: 193-204.
[18] JIN R, WANG G. Simple, fast, and scalable reachability oracle[J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1978-1989.
[19] VAN SCHAIK S J, DE MOOR O. A memory efficient reachability data structure through bit vector compression[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Jun 12-16, 2011. New York: ACM, 2011: 913-924.
[20] YILDIRIM H, CHAOJI V, ZAKI M J. GRAIL: scalable reachability index for large graphs[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 276-284.
[21] TRISSL S, LESER U. Fast and practical indexing and querying of very large graphs[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, Beijing, Jun 12-14, 2007. New York: ACM, 2007: 845-856.
[22] WEI H, YU J X, LU C, et al. Reachability querying: an independent permutation labeling approach[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1191-1202.
[23] SU J, ZHU Q, WEI H, et al. Reachability querying: can it be even faster?[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(3): 683-697.
[24] CHEN L, GUPTA A, KURUL M E. Stack-based algorithms for pattern matching on dags[C]//Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Aug 30-Sep 2, 2005. New York: ACM, 2005: 493-504.
[25] ZHOU S, YUAN P, LIU L, et al. MGTag: a multi-dimensional graph labeling scheme for fast reachability queries[C]//Proceedings of the 34th IEEE International Conference on Data Engineering, Paris, Apr 16-19, 2018. Washington: IEEE Computer Society, 2018: 1372-1375.
[26] VELOSO R R, CERF L, JR W M, et al. Reachability queries in very large graphs: a fast refined online search approach[C]//Proceedings of the 17th International Conference on Extending Database Technology, Athens, Mar 24-28, 2014: 511-522.
[27] SEUFERT S, ANAND A, BEDATHUR S, et al. FERRARI: flexible and efficient reachability range assignment for graph indexing[C]//Proceedings of the 29th IEEE International Conference on Data Engineering, Brisbane, Apr 8-12, 2013. Washington: IEEE Computer Society, 2013: 1009-1020.
[28] TARJAN R. Depth-first search and linear graph algorithms[C]//Proceedings of the 12th Annual Symposium on Switching and Automata Theory, East Lansing, Oct 13-15, 1971. Washington: IEEE Computer Society, 1971: 114-121.
[29] TARJAN R E. Applications of path compression on balanced trees[J]. Journal of the ACM, 1979, 26(4): 690-715.