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

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

10. END IF
∗
11. U ← center vertices that u visits in 2ε forward BFS;
12. V ← center vertices that v visits in 2ε backward BFS;
∗
∗
∗
∗
13. FOR each u ∈ U , each v ∈ V DO
∗
14. D s (u,v) = min(D s (u,u )+ D s (u ,v )+ D s (v ,v));
∗
∗
∗
∗
15. END FOR
16. RETURN (u, v).
例如, 给定 ε=2, 在图 3 中查询顶点 2 到顶点 14 的最短路径距离时, 顶点 2 与顶点 14 在同一划分区域, 则由
顶点 2 开始前向广度优先遍历, 遍历 3 步后访问到顶点 14, 因此 D s (2, 14)=3. 当查询顶点 17 和顶点 10 的最短路
径距离时, 这两个顶点不在同一划分区域, 于是由顶点 17 前向广度优先遍历 4 步, 记录下访问到的中心顶点和相
U = {< 0,1 >,< 8,4 >}, 同理由顶点 10 后向广度优先遍历 4 V = {< 8,2 >}, 因此 D s (17, 10)
∗
∗
应的距离, 得到 步得到
即为 D s (17, 0) D s (0, 8) D s (8, 10) 与 D s (17, 8) D s (8, 8) D s (8, 10) 两者的最小值 6.
最短路径查询算法的时间复杂度与可达查询算法的时间复杂度相同, 即最差情况下为 O(N 2ε (u)+E 2ε (u)+ N E CI ).
4.3 关键字查询算法
当给定图 G 和一组关键字 q k =(w 1 , w 2 ,…, w m ) 后, 关键字查询算法基于统一索引中的中心索引和倒排索引得
以加速实现. 其主要思想为: 首先基于倒排索引获取包含各关键字的顶点集合 Node(k i ), 选取出顶点集合中包含元
素个数最少的关键字 k i 以及其集合中的顶点, 构成后向搜索列表 BL(k i ), 其数据结构为 (node, dist), dist 初始化为
0; 然后逐一遍历后向搜索列表中的元素, 每遍历一个新顶点 u, 则最短路径算法查找到其他关键字 k j 的最短距离
∑ m
dist j , 得到以顶点 u 为根顶点的查询结果 t=<u, (n 1 , n 2 , …, n m ) >, 并根据 score(t) = dist i 评价函数来判断是否
i=1
要更新当前最优结果; 接着将顶点 u 后向遍历一步访问到的新顶点添加到后向搜索列表中; 直到遍历结束返回查
询结果.
为加快关键字查询算法的查询效率, 本文还将给出相应的剪枝策略. 根据后向搜索列表 BL(k i ) 的头元素
(node, dist), 可得到目前未被访问的顶点中到关键字 k i 距离最近的是顶点 node, 且距离为 dist. 因此, 若此时后向搜
索列表头元素的 dist 值已经大于当前最优结果 t 的评价函数, 则说明后向搜索列表中不存在更优的结果, 可提前
终止查询.
关键字查询算法 KSUI (keyword search on unified index) 的流程如算法 4 所示. 第 1 行初始化最终结果, 并将最
优的评价函数置为无穷大, 以及申请了布尔类型的一维数组用于记录各顶点的访问情况. 第 2 行根据统一索引中的
倒排索引获得各关键字的顶点集合, 并选取相应关键字初始化后向搜索列表 BL(k i ). 第 4 行获取后向搜索列表的头
元素, 每获取头元素需初始化两项内容. 第 5 行将顶点 node 到其他关键字 k j 的距离 dist j 置为无穷大, 并将其中的
dist i 置为 dist, 除此之外还初始化了一棵新结果树 newr, 用于记录下到达关键字 k j 的顶点 n j . 第 6–8 行用于判断是
否可以剪枝, 若可以直接返回结果树. 第 9–15 行基于中心索引获取当前顶点到其他关键字的最短距离, 其中第 12
行记录下最短距离和相应的顶点. 第 16–18 行用于判断当前顶点的评价函数是否优于当前最优结果, 若优于则更新
结果和当前最优评价函数. 第 20–24 行更新后向搜索列表. 直到后向搜索列表为空, 第 26 行返回最优结果.

算法 4. 关键字查询算法 KSUI.
输入: 图 G, q k =(k 1 , k 2 ,…,k m ), 中心索引 G CI , 倒排索引 II;
输出: 最优结果 t.

1. t ←< ∅,(∅,∅,...,∅) >,t ← ∞,visited(v i ) ← false;
2. get Node(k i ) and initialize BL(k i );
3. WHILE BL(k i ) is not empty DO