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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(5):2235−2256 [doi: 10.13328/j.cnki.jos.007493] [CSTR: 32375.14.jos.007493] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
大图数据的统一查询处理机制

陈 迪 1 , 袁 野 2 , 潘雅妮 1 , 王国仁 2

1
(东北大学 计算机科学与工程学院, 辽宁 沈阳 110169)
2
(北京理工大学 计算机学院, 北京 100081)
通信作者: 袁野, E-mail: yuan-ye@bit.edu.cn

摘 要: 现实世界中许多应用场景都可以用图数据表示, 图上的查询也具有广泛的应用, 如可达、最短路径、关键
字、图匹配、PageRank、SimRank、k-core、k-truss 和 Clique 等. 针对特定的查询问题, 目前的研究方法可概括为:
提出相应的查询处理算法, 并构建索引结构来加速查询. 然而, 现实应用中需求的多样化以及图数据规模爆炸式的
增长为该研究方法带来了两方面挑战: 第一, 同一个图数据在应用中会涉及多种查询, 但针对不同查询问题的处理
机制和索引结构均不相同, 因此在设计图数据库时需构建多个索引和相应的查询算法; 第二, 索引的规模通常比原
图数据的规模大, 多个索引同时存在会占用大量的系统空间, 导致图数据库的性能急剧下降, 不能被真正地应用.
为应对上述挑战, 提出一种统一的查询处理机制, 即为大图数据构建统一且高效的索引结构, 并基于统一索引结构
设计可达、最短路径、关键字和图匹配这 4 种查询处理算法. 为构建统一索引结构, 对大图数据进行划分, 并根据
可达、最短路径、关键字和图匹配这 4 种查询的特点提取出图数据中的重要顶点, 该统一索引结构规模比图数据
规模小, 并且能高效地支持上述 4 种查询. 最后, 通过在 4 组真实数据上的实验验证了统一索引结构和 4 种查询处
理算法的高效性和扩展性.
关键词: 统一索引; 可达查询; 最短路径查询; 关键字查询; 图匹配查询
中图法分类号: TP311

中文引用格式: 陈迪, 袁野, 潘雅妮, 王国仁. 大图数据的统一查询处理机制. 软件学报, 2026, 37(5): 2235–2256. http://www.jos.org.
cn/1000-9825/7493.htm
英文引用格式: Chen D, Yuan Y, Pan YN, Wang GR. Unified Query Processing Mechanism over Large-scale Graph Data. Ruan Jian
Xue Bao/Journal of Software, 2026, 37(5): 2235–2256 (in Chinese). http://www.jos.org.cn/1000-9825/7493.htm

Unified Query Processing Mechanism over Large-scale Graph Data
2
1
1
CHEN Di , YUAN Ye , PAN Ya-Ni , WANG Guo-Ren 2
1
(School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China)
2
(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)
Abstract: Graph data can represent a wide range of real-world application scenarios, and query processing over graphs plays a crucial role
in various tasks, such as reachability, shortest path, keyword search, graph pattern matching, PageRank, SimRank, k-core, k-truss, and
Clique. For specific query problems, existing approaches typically propose corresponding query processing algorithms and build index
structures to speed up the query. However, the diversification of application demands and the explosive growth in graph data scale present
two major challenges to this methodology. First, a single graph dataset may involve multiple types of queries in practice, yet each query
type often requires distinct processing mechanisms and index structures. Consequently, multiple indexes and corresponding query
algorithms need to be constructed when designing a graph database. Second, index structures are often larger than the original graph data,
and maintaining multiple indexes simultaneously can lead to significant space overhead, resulting in sharp performance degradation and
limited practical applicability. To address these challenges, this study proposes a unified query processing mechanism. A unified and

* 基金项目: 国家重点研发计划 (2022YFB2702100); 国家自然科学基金 (62225203, U21A20516)
收稿时间: 2025-01-15; 修改时间: 2025-04-11; 采用时间: 2025-06-13; jos 在线出版时间: 2025-12-17
CNKI 网络首发时间: 2025-12-25