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

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

5.2.3 最短路径查询算法比较
本节针对最短路径查询问题, 将本文提出的基于统一索引的最短路径查询算法 SPUI 同现有的 Bit-parallel
BFS 算法、IS-Label 算法 [36] 和基于 H2H 索引的最短路径查询算法的执行效率做以比较. 首先随机选取 10 000 对
查询顶点 u 和 v, 在 4 组数据集上执行上述 4 种最短路径查询算法, 查找顶点 u 到顶点 v 的最短路径的距离 D s (u,
v), 查询时间取 10 000 次查询时间的平均值. 然后为了使结果更有意义, 这里选取顶点的规则同可达查询算法比较
时选取顶点的规则相同, 即保证顶点 u 的出度大于 0, 顶点 v 的入度大于 0, 确保每次查询无论顶点 u 和顶点 v 之
间是否存在路径, 必定会访问一些顶点并消耗一定的时间.
Bit-parallel BFS、IS-Label 算法、基于 H2H 索引和本文基于统一索引提出的 SPUI 这 3 种最短路径查询算法
在不同数据集上所消耗的时间如图 12 所示, 同样为了方便比较, 将统一索引结构和 H2H 索引在不同数据集上所
消耗的空间也展示在了图 12 中. 可以看出, 基于 H2H 索引的查询算法和 SPUI 算法与 Bit-parallel BFS 算法进行
对比, 执行效率提高 13%–33%; 与 IS-Label 算法进行对比, 在前 3 个数据集下执行效率提高 6%–11%, 但在规模较
大的 Facebook 数据集下略差于 IS-Label 算法. H2H 算法和 SPUI 算法的流程相似, 最终 D s (u, v) 的结果都是由 3
D s = D s (u,v) = D s (u,u )+ D s (u ,v )+ D s (v,v ). 除此之外, 基于统一索引的 SPUI 算法与基于 H2H 索引
∗
∗
∗
∗
部分构成, 即
的查询算法的执行效率相似, 且在大规模图中 H2H 算法的查询效率略快一些. 以上 IS-Label 算法和基于 H2H 索
引的最短路径查询算法是现有大图查询处理机制针对最短路径距离查询提出的高效算法, 相似的结果证明了基于
统一索引的 SPUI 算法仍可高效地解决最短路径查询问题, 并且 SPUI 算法中涉及的统一索引在大规模图中占用
较少的存储空间.

20 60
H2H-index
18
SPUI-index
16 B-P BFS 50
H2H
14
Running time (ms) 12 8 IS-Label 30 Space cost (MB)
SPUI
40
10
4 6 20
10
2
0 0
WordNet DBLP US Patent Facebook
图 12 最短路径查询算法的效率比较

5.2.4 关键字查询算法比较
本节针对关键字查询问题, 首先验证了查询关键字组 q k 中关键字的个数对本文提出的基于统一索引的关键
字查询算法 KSUI 的影响, 随后, 将 KSUI 算法与现有的双向搜索算法, 以及结合最新索引技术 BiG-index 加速后
的 BLINKS 算法 (命名为 BLINKS-BiG) 在执行效率上进行了对比分析.
本文在 4 组数据集的标签上随机选取 10 000 个查询关键字组, 每组含有 k 个关键字, 其中 k≤10. 执行 KSUI
算法得到关键字匹配的查询结果, 图 13 给出了 KSUI 算法的执行效率与查询关键字组中含有关键字个数的关系.
可以看出, 整体趋势上关键字组 q k 中含有的关键字个数越多, 其查询响应的时间越长. 除此之外, 数据集中所含的
标签数量越多, 标签分布越稀疏, 当查找的关键字较多时, 前向搜索需计算最短路径的顶点对反而越少, 从而可以

提高整体的查询效率. 例如, DBLP 数据集中的标签分布较为稀疏, 当查询的关键字变多时, KSUI 算法的查询效率
并没有像在 US Patent 和 Facebook 数据集上那样呈线性增长, 反而比较平缓.
本文在各组数据集的标签集合中随机选 10 000 组关键字, 为避免上述查询关键字组中关键字的个数对算法的
影响, 每组关键字统一含有 4 个关键字, 执行上述 3 种关键字匹配算法, 查找与该组关键字匹配的结果, 查询时间取