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

2236 软件学报 2026 年第 37 卷第 5 期

efficient index structure is constructed for large-scale graph data, upon which four query processing algorithms are designed, supporting
reachability, shortest path, keyword search, and graph pattern matching. To build the unified index structure, the graph data is partitioned,
and important vertices are extracted based on the characteristics of the four queries. The resulting unified index is smaller in size than the
original graph and efficiently supports all four queries. Finally, the effectiveness and scalability of the unified index and the proposed
algorithms are validated through experiments on four real-world datasets.
Key words: unified index; reachable query; shortest path query; keyword search; graph matching query

近年来, 随着语义网络、社交网络、生物网络等新型领域的飞速发展, 数据的结构越来越复杂, 图作为一种特
殊的数据存储模型, 更具有一般性表示能力 [1] . 现实世界中的许多应用场景都需要用图数据表示, 比如, 传统应用
中的最优运输路线的确定、科技文献的引用关系等; 新兴应用中的社交网络分析、人脑网络等都可以看作是大图
数据的应用. 大图上的查询处理也有着广泛的应用, 人们为及时准确地从大图中查询信息并进行有效的分析, 提出
了许多不同类型的查询问题. 例如可达、最短路径、关键字、图匹配、PageRank、SimRank、k-core、k-truss 和
Clique 等查询问题 [2−6] .
可达、最短路径、关键字和图匹配是最基础的查询, 覆盖了图查询中最核心的 4 大典型任务, 分别对应内容
检索、结构匹配、连通性判定与路径优化. 这些查询类型广泛应用于知识图谱、社交网络、交通路径规划等实际
场景, 具有良好的代表性和通用性, 现已存在很多算法用以解决这 4 种查询问题. Wu 等人 [7] 总结了 SILC 和 CH
等 4 种可达和最短路径查询算法, Zhang 等人 [8] 提出了构建索引 SPTI 加速最短路径查询. Bhalotia 等人 [9] 提出了
可解决关键字查询的后向搜索算法, 并且可通过构建双层索引并采用双向搜索加速关键字查询.
He 等人 [10] 和 Cheng 等人 [11] 分别提出了 R-join 和 GraphQL 算法并构建相应的索引完成图匹配查询, Gao 等
人 [12] 提出将模式图划分成新框架以加速图匹配查询. Moayed 等人 [13] 提出一种特征分解剪枝策略以加速图匹配查询.
由现有研究成果可以看出, 针对特定的查询问题, 人们倾向于提出相应的查询处理算法, 并构建不同的索引结构
来加速查询, 是非统一的查询处理机制, 其框架如图 1 所示. 然而, 现实应用中需求的多样化以及图数据规模爆炸式
的增长使得现有研究方法存在两方面挑战. 第一, 同一个图数据在应用中会涉及多种查询, 不同查询问题的处理机制
和索引结构均不相同, 因此在设计图数据库时需构建多个索引结构和相应的查询算法; 第二, 索引的规模通常比原图
数据的规模大, 多个索引同时存在会占用大量的系统空间, 导致图数据库的性能急剧下降, 不能被真正应用.

索引1 可达查询算法

索引2 最短路径查询算法
构
构 加
加
图数据G 建 速
建
速
索引3 关键字查询算法
索引4 图匹配查询算法
… …
图 1 非统一查询处理机制框架

为解决上述挑战, 本文提出了一种统一的大图数据查询处理机制, 其框架如图 2 所示, 即为大图构建统一且高
效的索引结构, 并基于统一索引结构设计了可达、最短路径、关键字和图匹配这 4 种查询算法.
但现有的索引和查询算法都是针对某一查询问题提出的, 它们在结构和处理机制上均不相同, 不能直接应用
在统一的查询处理机制中. 因此, 本文首先基于图数据的疏密性对大图进行划分, 并根据可达、最短路径、关键字
和图匹配这 4 种查询的特点提取出各划分区域的重要顶点来构建统一索引结构. 为保证该统一索引结构的空间复
杂度小, 并可高效支持上述 4 种查询, 其由中心索引、临界顶点集合, 以及关键字的倒排索引这 3 部分构成. 除此
之外, 本文基于统一索引结构设计了上述 4 种查询相应的处理算法, 分别加速了基于宽度优先遍历搜索的可达和
最短路径查询算法、基于双向搜索思想的关键字查询算法以及先匹配模式子图再连接取并集的图匹配算法.