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

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

数据集 1 表示了英语单词之间的关系 (http://snap.stanford.edu/data/). 数据集 2 是基于 DBLP XML 数据生成的
带标签的有向图 (http://dblp.uni-trier.de/xml/), 首先在原始 XML 数据上为含有引用关系的论文添加有向边, 并删除
大多数未引用或未被引用的论文. 数据集 3 中记录了美国专利的引用 (http://vlado.fmf.uni-lj.si/pub/networks/data/).
数据集 4 是基于 Facebook 用户数据生成的带标签有向图.
除此之外, 为保证数据集为 DAG 图, 通过深度优先遍历一次将图中的强连通分量拟合成一个顶点.
5.2 实验结果与分析
5.2.1 索引比较
本节将对比统一查询处理机制和非统一查询处理机制在解决 4 种查询问题时构建统一索引和非统一索引所
消耗的时间和空间.
统一大图查询处理机制, 即构建统一索引, 便可进行可达、最短路径、关键字和图匹配这 4 种查询. 首先利用
本文提出的图划分算法并给定 ε=2 对 4 组图数据集进行划分, 然后为每组数据集建立统一索引结构, 在 4 种数据
集上构建统一索引所消耗的时间和占用的空间如图 9 所示. 由图 9(a) 可知, 构建统一索引的时间由划分图数据和
生成统一索引结构两部分构成, 由图 9(b) 可知, 统一索引结构所占用的空间用于存储中心索引图、临界顶点集合
和倒排索引这 3 部分内容, 为更好地与非统一查询处理机制进行对比, 本文将建立统一索引所消耗的时间和空间
的总和总结如表 2 所示.

8 000 50
GD
Center index (CI) Center index graph
B set 40 B set
KP & KN index
6 000
Running time (s) 4 000 Space cost (MB) 30
Inverted index (II)
Total
Total
20
2 000
10
0 0
WordNet DBLP US Patent Facebook WordNet DBLP US Patent Facebook
(a) 时间消耗 (b) 空间消耗
图 9 建立统一索引结构消耗的时间和空间

表 2 建立统一索引结构消耗的时间和空间

数据集 时间 (s) 空间 (MB)
WordNet 43.4 4.2
DBLP 1 081.6 6.0
US Patent 2 751.8 16.4
Facebook 7 521.3 47.6

现有的非统一查询处理机制, 即针对一种查询问题构建一种索引, 各索引的结构均不相同. 我们在 4 组数据集
合中分别构建 Ouyang 等人 [34] 于 2023 年提出的 H2H 索引解决可达和最短路径查询、构建 Jiang 等人 [23] 于 2021
年提出的 BiG-index 索引解决关键字匹配查询, 以及构建 Sun 等人 [33] 于 2020 年提出的索引结构 BI 解决图匹配问
题. 在 4 组数据集上, 构建上述 3 组索引消耗的时间与空间如图 10(a) 和 (b) 所示. 此外, 3 种索引在 4 组数据集上
分别消耗的时间和空间如表 3 和表 4 所示.
由表 2–表 4 可以看出, 针对同一个图进行可达、最短路径、关键字和图匹配这 4 种查询时, 统一查询处理机
制在构建统一索引过程中, 相较于现有非统一机制分别为多类查询单独构建索引, 最多可节省 39% 的构建时间,
并显著减少 77%–85% 的存储空间开销.