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

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

4.4 图匹配查询算法
当给定图 G 和模式图 q m 后, 图匹配算法首先将模式图划分为多个模式子图 sq j ; 然后在各划分区域 P i 中匹配
模式子图 sq j , 并得到匹配子图 sg j (i); 接着在划分区域一定的情况下, 对所有匹配子图做连接操作, 得到该划分区域
下对模式图的匹配结果 g(i); 最终对所有 g(i) 做并集操作得到查询结果.
4.4.1 模式图划分
划分模式图的主要思想是: 按照边覆盖原则将模式图划分为多个三层树结构的模式子图, 每个模式子图含有
一个中间顶点, 第 1 层为中间顶点后向搜索一步访问到的顶点, 第 3 层为中间顶点前向搜索一步访问到的顶点,
第 1 层或第 3 层可不存在. 例如, 图 8(a) 所示的模式图的划分如图 8(b) 所示的 3 个模式子图.

1 {a}
1 {a}
2 {a} {d} 3 5 {a}
2 {a}
{d} 3 5 {a} {f} 4 6 {d}
{d} 3 5 {a}
{f} 4 6 {d} sq 1 sq 2 sq 3
(a) 模式图 (b) 模式子图
图 8 模式图划分

经研究发现, 模式子图的数量以及模式子图的匹配顺序会影响图匹配算法的效率, 模式子图越少, 连接操作越
少, 算法效率越高; 后匹配的模式子图中已被匹配的标签越多, 算法的效率越高. 为得到最少的模式子图和最优的
子图匹配顺序, 本文遵循以下策略划分模式图: 在模式图中首选与已选过的边相连且与选择性高的顶点有联系的
边 e=(u, v), 生成以选择性高的顶点为中间顶点的模式子图, 并移除模式图中与该顶点有关的边, 直到模式图中不
存在可选的边时停止划分. 其中, 顶点的度越大, 且含有标签出现的频率越低, 则该顶点的选择性越高.
4.4.2 模式子图匹配
当给定划分区域 P i 和模式子图 sq j 后, 匹配模式子图的策略是: 首先基于倒排索引 II 中的 L KN (P, k) 列表去寻
找可匹配中间顶点的顶点, 并构成候选顶点集合; 然后再逐一访问该集合中的顶点, 探索该顶点后向遍历一步访问
的顶点是否可匹配第 1 层顶点, 该顶点前向遍历一步访问到的顶点是否可以匹配第 3 层顶点. 若都可找到匹配顶
点, 则可获得划分区域 P i 对模式子图 sq j 的匹配结果 sg j (i).
但需注意一种特殊情况, 即候选顶点集合中可能存在边界顶点, 在匹配模式子图 sq j 时会涉及跨划分区域匹
配, 从而需要考虑当前划分区域的扩展问题. 因此, 在遍历候选顶点集合中的顶点时, 首先基于临界顶点集合来判
断该顶点是否为边界顶点, 若该顶点在临界顶点集合中, 且其 value 值标记为 1 (2) 则为入 (出) 边界顶点, 需判断
其入 (出) 顶点 v 是否可以匹配模式子图第 1 (3) 层顶点的某个顶点, 若可以匹配, 此时划分区域 P i 则为 P i 与 P j 的
并集, 使得当前进行匹配的划分区域得以扩展, 其中 P j 则为顶点 v 所属的划分区域.
模式子图的匹配算法 sub-PM (pattern subgraph matching) 的流程如算法 5 所示. 第 1 行对最终结果初始化, 并
将候选顶点集合 Q 置为空. 第 2 行获取中间顶点标签. 第 3 行根据中间顶点标签获取候选顶点. 第 4–15 行逐一访
问候选顶点集合中的顶点, 每访问到一个新顶点 u, 第 5 行和第 6 行分别去匹配模式子图的第 1 层和第 3 层顶点.
当以顶点 u 匹配中间顶点并且第 1、3 层顶点都有相应匹配的顶点时, 第 8 行则将匹配的子图压入最终结果 sg j (i)
中; 若完成匹配并且顶点 u 为边界顶点时, 第 11 行则扩展当前匹配的划分区域; 直到候选顶点集合中的顶点都被
访问过一次后, 便可返回最终结果 sg j (i).

算法 5. 模式子图的匹配算法 sub-PM.
输入: 划分区域 P i , 模式子图 sq j , 临界顶点集合, 倒排索引;
输出: 匹配子图 sg j (i).