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

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

O(N V ·logN V ); 第二, 执行图划分算法 (算法 1), 每个顶
在图划分前需对图中所有顶点按照度值进行排序, 复杂度为
O(N V + N E ); 第三, 执行中心索引构建算法
点在 ε 步广度优先遍历中最多访问一个邻域, 其复杂度在最坏情况下为
(算法 2), 对所有顶点进行局部遍历以生成中心索引图, 最坏情况下每个顶点都需访问整个图, 则其复杂度最多为
O(N V ·(N V + N E )); 第四, 临界顶点集合的提取与处理时间复杂度可视为 O(N V ) 因其最多只需遍历所有顶点一次; 第
五, 倒排标签索引的构建为线性扫描过程, 时间复杂度为 O(N V ). 综上, 构建统一索引的总体时间复杂度为: O(N V ·
logN V + N V + N E + N V ·(N V + N E )), 即最终简化为: O(N V ·(N V + N E )).
统一索引的空间复杂度主要由存储中心索引图、临界顶点集合以及倒排标签索引这 3 部分构成. 第一, 中心
2
索引图在最坏情况下需存储所有顶点之间的连边, 空间复杂度为 O(N ); 第二, 临界顶点集合通过对每个顶点打标
V
记存储, 消耗 O(N V ) 的空间; 第三, 倒排标签索引存储时需要记录每个标签对应的划分区域, 以及划分区域中对应
的顶点, 同样需遍历所有顶点及其标签, 整体空间复杂度为 O(N V ). 综上, 构建统一索引的总空间复杂度为
2
O(N + N V ).
V
需要指出的是, 在实际应用中, 图数据通常是稀疏的, 中心顶点集合远小于总体顶点数, 实际的时间和空间开
销远低于上述最坏情况.
4 查询算法

本节将分别介绍基于统一索引设计的可达、最短路径、关键字和图匹配这 4 种查询处理算法.
4.1 可达查询算法
根据上述划分算法可知, 图 G 中任意顶点 u, 在广度优先遍历 2ε 步后, 至少会访问到一个中心顶点. 因此, 当
给定数据图 G 和图中的两顶点 u, v 后, 可达查询算法的主要思想是: 先判断顶点 u 和顶点 v 是否在同一划分区域,
若在同一划分区域, 则由顶点 u 广度优先遍历 ε 步, 若访问到顶点 v 则直接返回可达, 否则直接返回不可达; 若不
在同一划分区域, 则由顶点 u 前向遍历 2ε 步并记录下访问到的中心顶点并构成集合 U , 再由顶点 v 反向遍历 2ε
∗
∗
∗ ∗ V 中是否存在可达的顶
步并记录下访问到的中心顶点并构成集合 V , 最终通过中心索引来查询集合 U 和集合
点对, 从而返回最终结果.
可达查询算法 RQUI (reachability query on unified index) 的流程如算法 2 所示, 第 1 行将存放中心顶点的集合
∗ V 初始化. 第 行讨论当顶点 和顶点 v 在同一划分区域的情况. 第 行从顶点 开始广度优先遍历
∗
U 和 2–9 u 3–7 u
2ε. 第 4 行若访问到顶点 v 返回 true, 否则返回 false. 第 10 行记录下由顶点 u 前向遍历 2ε 步内访问到的中心顶点.
第 11 行记录下顶点 v 反向遍历 2ε 步内访问到的中心顶点. 第 12–18 行用于查找集合 U 和集合 V 中是否存在可
∗
∗
达的一对顶点, 若存在则返回 true, 否则返回 false.
算法 2. 可达查询算法 RQUI.
输入: 图 G, 顶点 u, 顶点 v, 中心索引图 G CI ;
输出: 顶点 u 是否可达顶点 v.

1. U ← ∅, V ← ∅;
∗
∗
2. IF u, v in the same partition THEN
3. FOR each w that u visits in 2ε steps DO
4. IF w == v THEN
5. RETURN true;
6. END IF
7. END FOR
8. RETURN false;
9. END IF
10. U ← center vertices that u visits in 2ε forward BFS;
∗