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

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

径查询问题. 然而, 这些经典的最短路径查询算法都需在内存中得以实现, 当图规模很大时, 这些算法则不再适用,
它们无法支持大规模图的在线查询.
为解决上述问题, 研究者们提出了一个重要思路, 即先离线预处理存储图中部分最短路径信息, 待在线查询时
便基于预处理信息给出最终的查询结果. 例如, Agrawal 等人 [18] 对存储了大图中所有核心顶点间的最短路径进行
预处理. 除此之外, Yang 等人 [19] 还提出了一种基于顶点优先排列的方法来存储顶点间的最短路径. Wang 等人 [20]
通过草图查询离线标记 (即预先计算的标签) 高效地引导在线搜索. 然而, 存储大量的预处理信息会消耗过多的内
存空间从而加重存储代价, 因此近年来人们一直在研究以减少预处理信息为目标的最短路径查询算法. 例如,
TEDI [21] 则提出将图分解为树结构, 树上每个顶点代表图顶点的一个子集, 查询算法会并行预处理存储每个树顶点
中各图顶点到彼此的最短路径. Wu 等人 [7] 总结了路网中用于解决最短路径的查询算法, 并将其分为两类, 其一是
基于空间相关性的算法, 如 SILC 算法和 PCPD 算法; 其二是基于顶点重要性的算法, 如 CH 算法和 TNR 算法. 其
中基于顶点重要性的算法不仅会选取出较为重要的地标顶点, 也会忽略一些并不重要的顶点. 除此之外, Zhang 等
人 [8] 提出了最短路径树桩 SPT 和最短路径树桩索引 SPTI 来加快最短路径查询.
总之, 现有的高效最短路径查询算法都是基于预处理信息来加速的. 人们仍在进一步研究如何减少预处理信
息的存储代价, 以及如何更多地利用最短路径本身的一些固有结构特征.
1.3 关键字查询算法
最为基础的关键字查询算法便是基于 Dijkstra 算法进行后向搜索查询, 如 Bhalotia 等人 [9] 提出了 BANKS 算
法, 其主要思想是: 首先定义了顶点集合 E i , 其存放可达关键字 k i 的顶点, 初始化后的 E i 仅存放含有关键字 k i 的
顶点; 然后在后向搜索的过程中更新顶点集合 E i , 在每一轮的搜索过程中, 选取集合 E i 中到关键字 k i 距离最近且
未被访问过的顶点 v, 将顶点 v 后向广度优先搜索一步访问到的新顶点添加到 E i 中; 最后的返回结果是所有顶点
集合中共同含有的顶点.
后向搜索算法虽然易于理解, 但难扩展到大规模图上, 双向搜索算法 BLINKS [22] 可加速关键字匹配, 其主要的
思想是: 首先从含有关键字 k i 的顶点或可达关键字 k i 的顶点后向搜索一轮访问新顶点; 然后每访问到一个新顶点
u 时, 便前向搜索查询该顶点到其他关键字的最短距离 dist j (1≤j≤m, i≠j), 其中 m 为关键字的个数, 并计算以 u 为
根顶点的评价函数, 若此时根顶点 u 的评价函数小于当前最优结果的评价函数, 则把该顶点记作当前最优结果; 最
后待达到搜索的停止条件时, 返回当前的最优结果. He 等人 [10] 还提出了划分大图数据并构建双层索引结构加速双
向搜索查询. 除此之外, 为加快关键字查询, Jiang 等人 [23] 提出了一种通用本体索引框架 BiG-index, 通过迭代式构
建多层次的摘要图 (summary graph) 索引, 结合本体引导的查询重写与早期剪枝策略, 在保证查询语义准确性的同
时, 有效缩小了搜索空间, 大幅提升了关键词查询的效率, 实验结果显示对现有方法如 BLINKS 具有显著加速效
果. Ghanbarpour 等人 [24] 提出一种最小覆盖 r-clique 对现有模型进行扩展, 解决了现有算法中存在冗余节点的问题
并能够以分布式方式执行.
1.4 图匹配查询算法
图匹配查询问题根据查询语义的不同, 可分为图同构匹配查询和图模拟匹配查询. 图匹配问题可分为图模式
匹配和图模拟匹配. 图模式匹配是在图数据 G 中找到与模式图 P 同构的所有子图, 是 P 中边与 G 中边匹配的问
题, 其为 NP 难问题. 图模拟匹配试图找到语义或概念上与模式图相似的子图, 是 P 中边与 G 中路径匹配的问题,
模拟匹配降低了整体匹配的复杂度, 可在多项式时间内解决 [25] , Bouhenni 等人 [26] 给出了不同的图模拟匹配算法.
本文将重点研究同构匹配查询, 现已存在很多优秀的模式匹配算法. 最为经典的是 1976 年提出的 Ullmann 算
法 [27] , 该算法采用深度优先遍历的方法, 逐一枚举出与模式图同构的子图, 在遍历的过程中通过检查匹配点对的
邻接顶点来进行剪枝, 尽早识别出不可匹配的顶点. 接下来 VF2 算法 [28] 在 Ullmann 算法的基础上加以改进, 也可
用于解决精确图匹配问题. 还有许多查询算法通过建立索引来加速匹配过程, 比如 GraphGrep 算法 [29] 将带有语义
信息的顶点编码后建立索引, 还可以基于简单的路径、树以及其他简单的结构对图数据中的每个节点进行编码描
述来建立索引. Spath 算法 [30] 为原数据图和模式图中的每一个顶点建立到该点最短距离小于 k 的邻居签名, 从而来