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

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

12 000 250
H2H H2H
10 000 BiG-index 200 BiG-index
BI
Running time (ms) 8 000 Space cost (MB) 150 Total
BI
Total
6 000
100
4 000
2 000 50
0 0
WordNet DBLP US Patent Facebook
WordNet DBLP US Patent Facebook
(a) 时间消耗 (b) 空间消耗
图 10 建立非统一索引结构消耗的时间和空间

表 3 建立非统一索引结构消耗的时间 (s) 表 4 建立非统一索引结构消耗的空间 (MB)

数据集 H2H BiG-index BI 总计 数据集 H2H BiG-index BI 总计
WordNet 25.8 35.2 10.5 71.5 WordNet 10.2 6.3 11.2 27.7
DBLP 292.1 603.6 202.6 1 098.3 DBLP 15.5 10.6 18.9 45.0
US Patent 1 200.6 1 535.8 543.2 3 279.6 US Patent 25.3 19.5 31.6 76.4
Facebook 4 100.8 4 980.7 1 710.2 10 791.7 Facebook 68.8 60.7 83.2 212.7

5.2.2 可达查询算法比较
本节针对可达查询问题, 将本文提出的基于统一索引的可达查询算法 RQUI 同现有的无索引广度优先遍历算
法和基于 H2H 索引算法的执行效率做以比较. 首先随机选取 10 000 对查询顶点 u 和 v, 在 4 组数据集上执行上述
3 种可达查询算法, 查找顶点 u 是否可达顶点 v, 查询时间取 10 000 次查询的平均值. 然后为使比较结果更有意义,
每次随机从出度大于 0 的顶点中选取顶点 u, 从入度大于 0 的顶点中选取顶点 v, 确保每次查询无论顶点 u 和 v 是
否可达, 必定会访问一些顶点并消耗一定的时间.
Bit-parallel BFS [35] 、基于 H2H 索引和本文基于统一索引提出的 RQUI 这 3 种可达查询算法在不同数据集上
所消耗的时间如图 11 所示, 为方便比较, 将统一索引结构和 H2H 索引在不同数据集上所消耗的存储空间也展示
在了图 11 中. 可以看出, 基于 H2H 索引结构的算法和 RQUI 算法与 Bit-parallel BFS (图中以 B-P BFS 代替) 算法
进行对比, 执行效率提高了 20%–28%. 还可以看出, 基于统一索引的 RQUI 算法与基于 H2H 索引的算法执行效率
相似, 在大规模图中基于 H2H 索引的算法执行效率稍快一些, 其可基于索引直接给出答案, 而 RQUI 算法还需在
中心索引上查询中心顶点的可达性, 但大规模图中 H2H 索引消耗的空间大于统一索引结构消耗的空间. 因此, 可
以得出 RQUI 算法在保证尽量少的占用系统空间的前提下还能保证较为高效的查询效率.

20 80
H2H-index
18
RQUI-index 70
16 B-P BFS
H2H 60
14
Running time (ms) 12 8 40 Space cost (MB)
RQUI
50
10
30
6
20
4
10
2
0 0
WordNet DBLP US Patent Facebook
图 11 可达查询算法的效率比较