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

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

10 000 次查询的平均值. 为避免随机生成的关键字组并不存在查询结果而消耗太多时间, 规定各算法超过 90 s 则
直接结束.

90
WordNet
80
DBLP
70
US Patent
Running time (s) 50
60
Facebook
40
30
20
10
0
2 3 4 5 6 7 8 9 10
关键字个数
图 13 关键字个数对 KSUI 算法的影响

双向搜索、BLINKS-BiG 和本文提出的基于统一索引的 KSUI 这 3 种关键字查询算法在不同数据集上所消耗
的时间如图 14 所示, 为方便比较, 将统一索引结构和 BLINKS-BiG 算法的索引结构 BiG-index 在不同数据集上所
消耗的空间也展示在了图 14 中. 由图 14 可以看出, BLINKS-BiG 算法和 KSUI 算法, 与无索引的双向搜索算法对
比, 执行效率至少提高了 30%, 在 DBLP 数据集上提高近 75%. BLINKS-BiG 算法和 KSUI 算法采用的都是双向搜
索的思想, 并都是基于索引结构加速了双向搜索的过程. 其中 BLINKS-BiG 算法利用 BiG-index 预先构建的多层
次摘要图结构, 在前向搜索时仅需在摘要图上定位包含查询关键字的摘要节点, 进而减少原图上的遍历开销, 而基
于统一索引的 KSUI 算法前向搜索时需通过统一索引结构计算顶点与关键字的距离, 因此 KSUI 算法的执行效率
低于 BLINKS-BiG 算法, 但整体上较为相似. 除此之外, 统一索引结构在空间上的优势较为明显, BLINKS-BiG 算
法中涉及的 BiG-index 索引结构记录了过多的多层次摘要图信息, 从而增加系统的存储压力. BLINKS-BiG 算法是
现有非统一查询处理机制专门针对关键字问题提出的, 图 14 中较为近似的查询效率和较为优越的空间占用率, 证
明了基于统一索引的 KSUI 算法可高效地解决关键字查询问题.

200 70
BiG-index
180
KSUI-index 60
160
双向搜索 50
140
Running time (ms) 120 KSUI 40 Space cost (MB)
BLINKS-BiG
100
30
80
60
40 20
10
20
0 0
WordNet DBLP US Patent Facebook
图 14 关键字查询算法的效率比较

5.2.5 图匹配查询算法比较
本节针对图匹配查询问题, 首先验证模式图的大小对本文基于统一索引提出的图匹配查询算法 PMUI 执行效
率的影响, 然后将 PMUI 算法与现有的图匹配算法的执行效率做比较. Sun 等人 [33] 提出了 VC 算法用于加快精确