Page 376 - 《软件学报》2026年第5期

陈迪 等: 大图数据的统一查询处理机制 2255

6 总 结

本文研究了统一的大图查询处理机制, 即为大图构建统一且高效的索引结构, 并基于统一索引结构设计了可
达、最短路径、关键字和图匹配这 4 种查询算法, 该统一索引结构规模比图数据规模小, 并且能高效地支持上述
4 种查询. 最后, 通过在 4 组真实数据上的实验验证了统一索引结构和 4 种查询处理算法的高效性和扩展性. 在未
来的工作中将会做如下的深入研究: (1) 考虑动态图中统一索引的更新问题; (2) 考虑其他查询问题的统一查询处
理机制, 如 PageRank、SimRank、k-core、k-truss 和 Clique 等, 以建立最少的索引结构解决最多的查询问题为最终
研究目标; (3) 考虑将统一查询处理机制融合到现有的图数据库中.

References
[1] Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-based Systems, 2018, 151:
78–94. [doi: 10.1016/j.knosys.2018.03.022]
[2] Chen NY, Litvak N, Olvera-Cravioto M. Generalized PageRank on directed configuration networks. Random Structures & Algorithms,
2017, 51(2): 237–274. [doi: 10.1002/rsa.20700]
[3] Liu Y, Zheng BL, He XD, Wei ZW, Xiao XK, Zheng K, Lu JH. Probesim: Scalable single-source and top-k simrank computations on
dynamic graphs. Proc. of the VLDB Endowment, 2017, 11(1): 14–26. [doi: 10.14778/3151113.3151115]
[4] Li Y Z, Zhu YY, Zhong M. k-core filtered influence maximization algorithms in social networks. Journal of Computer Applications,
2018, 38(2): 464–470 (in Chinese with English abstract). [doi: 10.11772/j.issn.1001-9081.2017071820]
[5] Huang X, Cheng H, Qin L, Tian WT, Yu JX. Querying k-truss community in large and dynamic graphs. In: Proc. of the 2014 ACM
SIGMOD Int’l Conf. on Management of Data. Snowbird: ACM, 2014. 1311–1322. [doi: 10.1145/2588555.2610495]
[6] Zeume T. The dynamic descriptive complexity of k-clique. Information and Computation, 2017, 256: 9–22. [doi: 10.1016/j.ic.2017.04.
005]
[7] Wu LK, Xiao XK, Deng DX, Cong G, Zhu AD, Zhou SG. Shortest path and distance queries on road networks: An experimental
evaluation. Proc. of the VLDB Endowment, 2012, 5(5): 406–417. [doi: 10.14778/2140436.2140438]
[8] Zhang YF, Wang GR. SPTI: Efficient answering the shortest path query on large graphs. In: Proc. of the 2013 IEEE Int’l Congress on Big
Data. Santa Clara: IEEE, 2013. 195–202. [doi: 10.1109/BigData.Congress.2013.34]
[9] Bhalotia G, Hulgeri A, Nakhe C, Chakrabarti S, Sudarshan S. Keyword searching and browsing in databases using BANKS. In: Proc. of
the 18th Int’l Conf. on Data Engineering. San Jose: IEEE, 2002. 431–440. [doi: 10.1109/ICDE.2002.994756]
[10] He H, Wang HX, Yang J, Yu PS. BLINKS: Ranked keyword searches on graphs. In: Proc. of the 2007 ACM SIGMOD Int’l Conf. on
Management of data. Beijing: ACM, 2007. 305–316. [doi: 10.1145/1247480.1247516]
[11] Cheng JF, Yu JX, Ding BL, Yu PS, Wang HX. Fast graph pattern matching. In: Proc. of the 24th IEEE Int’l Conf. on Data Engineering.
Cancun: IEEE, 2008. 913–922. [doi: 10.1109/ICDE.2008.4497500]
[12] Gao JR, Chen W, Xu JJ, Liu A, Li ZX, Yin HZ, Zhao L. An efficient framework for multiple subgraph pattern matching models. Journal
of Computer Science and Technology, 2019, 34(6): 1185–1202. [doi: 10.1007/s11390-019-1969-x]
[13] Moayed H, Mansoori EG, Moosavi MR. An efficient pruning method for subgraph matching in large-scale graphs. The Journal of
Supercomputing, 2023, 79(10): 10511–10532. [doi: 10.1007/s11227-023-05061-1]
[14] Claude F, Navarro G. Fast and compact Web graph representations. ACM Trans. on the Web (TWEB), 2010, 4(4): 16. [doi: 10.1145/
1841909.1841913]
2
[15] Brisaboa NR, Ladra S, Navarro G. k -trees for compact Web graph representation. In: Proc. of the 16th Int’l Symp. on String Processing
and Information Retrieval. Saariselkä: Springer, 2009. 18–30. [doi: 10.1007/978-3-642-03784-9_3]
[16] Rossi RA, Zhou R. GraphZIP: A clique-based sparse graph compression method. Journal of Big Data, 2018, 5(1): 10. [doi: 10.1186/
s40537-018-0121-z]
[17] Yu CY, Ren TM, Li WY, Liu HM, Ma HT, Zhao YH. BL: An efficient index for reachability queries on large graphs. IEEE Trans. on Big
Data, 2024, 10(2): 108–121. [doi: 10.1109/TBDATA.2023.3327215]
[18] Agrawal R, Jagadish HV. Algorithms for searching massive graphs. IEEE Trans. on Knowledge and Data Engineering, 1994, 6(2):
225–238. [doi: 10.1109/69.277767]
[19] Yang YJ, Li ZF, Wang X, Hu QH. Finding the shortest path with vertex constraint over large graphs. Complexity, 2019, 2019: 8728245.
[doi: 10.1155/2019/8728245]
[20] Wang Y, Wang Q, Koehler H, Lin Y. Query-by-Sketch: Scaling shortest path graph queries on very large networks. In: Proc. of the 2021