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

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

图匹配查询, 该算法通过代价模型生成优化匹配顺序, 并离线构建 BI 索引以记录候选顶点及其筛选邻居, 从而在
查询阶段高效执行子图同构匹配.
本文在每组数据集上随机选择一个顶点, 从该顶点开始深度优先遍历, 利用遍历到的前 k 个顶点形成待匹配
的模式图 q k , 其中 k≤10, 如此反复, 生成 10 000 个规模不等的模式图 q k . 在 4 组数据集上分别执行 PMUI 算法, 查
询不同规模下模式图 q k 的匹配子图, 图 15 给出了 PMUI 算法查询效率与模式图规模大小的关系, 其中横坐标为
模式图 q k 中含有的顶点个数. 可以看出, 整体趋势上模式图的规模越大图匹配的查询响应时间越长. 但在数据集
WordNet、US Patent 和 Facebook 中, 具有 10 个顶点的模式子图查询的执行时间却比具有 9 个顶点模式图的查询
的执行时间低一些, 说明 PMUI 算法对中间顶点的约束导致其中间结果减少, 从而减少了连接操作消耗的时间, 降
低了整体响应时间.

100
WordNet
90
DBLP
80 US Patent
Running time (s) 60
70
Facebook
50
40
30
20
10
0
3 4 5 6 7 8 9 10
模式图规模
图 15 模式图规模对 PMUI 算法的影响

为避免模式图的规模对查询算法的影响, 采用上述实验生成的顶点个数为 5 和 10 的模式图, 在 4 组数据集上
执行上述两种图匹配的查询算法, 查询两种规模的模式图的子图匹配, 消耗的时间为查询 10 000 次后的平均时间,
为避免某一模式图的匹配子图过多从而消耗大量时间, 则规定当查找到 1 024 个结果后即结束查询.
基于 BI 的 VC 算法与基于统一索引的 PMUI 算法在不同数据集上的运行时间如图 16 所示. 为便于对比, 图
中还展示了两种索引结构在不同数据集上的空间开销. 由图 16 可见, PMUI 算法在执行效率上与现有的 VC 算法
相近, 当模式图规模较大时, VC 在运行时间上略占优势. 然而, 统一索引结构显著降低了系统的存储压力, 使得
PMUI 在空间消耗上具有明显优势. 鉴于 VC 算法是专门针对图匹配查询设计的, 该实验结果表明, 基于统一索引
结构的 PMUI 算法不仅能够高效支持图匹配查询, 还展现出良好的扩展性.

80 90
BI
70 PMUI-index 80
VC-5
60 PMUI-5 70
Running time (ms) 50 50 Space cost (MB)
VC-10
60
PMUI-10
40
40
30
20 30
20
10 10
0 0
WordNet DBLP US Patent Facebook
图 16 图匹配查询算法的效率比较