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

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

和入边界顶点集合 IN. 最终提取重要顶点的结果如图 4 所示, 每一划分区域中, 十字交叉背景的顶点为出边界顶点,

斜线背景的顶点为入边界顶点, 即入边界顶点集合 IN = {{2,3},{12},∅,{5}}, 出边界顶点集合 OUT = {{4,10},∅,{1,0},∅}.
3.2 构建索引
本文提出的统一索引结构由 3 部分组成: 其一是基于中心顶点集合建立中心索引, 其二是基于各划分区域的
重要顶点得到临界顶点集合, 其三是基于最小划分覆盖建立关键字的倒排索引.
中心索引是一个索引图 G CI (V CI , E CI ), 可用于加速可达、最短路径和关键字的查询. 其顶点集合 V C 即为算法 1
I
得到的中心顶点集合 C, 为保证不破坏图 G 中原有的可达性, 需为这些顶点添加带有准确权值的有向边. 根据上
述划分策略可知, 两个可达的中心顶点的距离不大于 2ε. 因此, 生成中心索引图边集合 E C 的主要思想是: 对于集
I
合 V C 中任意顶点 u 做距离 2ε 的前向广度优先遍历, 若在 2ε 距离内访问到其他中心顶点 v, 则说明顶点 u 和顶点
I
v 在图 G 中可达, 需为 u 和 v 添加一条边, 即 (u, v) ∈ E CI , 并且该条边的权值是 u 到 v 的最短路径距离. 例如, 图 3
的中心索引图 G C 如图 5 所示.
I

0
3
4
8
3 3

5 12
图 5 中心索引

临界顶点集合 B, 采用 key-value 的形式存储第 3.1 节中提取出的入边界顶点集合和出边界顶点集合, 可用于
加速图匹配查询. 其中 key 为入边界顶点集合和出边界顶点集合中的顶点, value 可取{1, 2, 3}这 3 个整数中的任
意一个, 其中 1 代表顶点 key 为入边界顶点, 2 代表顶点 key 为出边界顶点, 3 代表顶点 key 既为入边界顶点又为出
边界顶点. 待图匹配查询时, value 中存放的值可以给出当前划分区域应向哪个方向进行扩展. 例如, 基于图 4 的近
优划分结果和提取出的重要顶点, 可以得到图 3 的临界顶点集合 B={<2, 1>, <3, 1>, <5, 1>, <12, 1>, <0, 2>, <1, 2>,
<4, 2>, <10, 2>}.
倒排索引 II (inverted index), 也采用 key-value 的形式存储标签的分布情况, 可用于加速关键字和图匹配的查
询速度. 倒排索引 II 包含两部分, 其一是关键字与划分区域 (KP) 映射的关系列表 L KP (k), 记录着含有关键字 k 的
划分区域, 其中 key 为关键字, value 为划分区域, 基于图 4 的划分结果可得到如图 6(a) 所示的 L KP (k); 其二是各划
分区域中关键字和顶点 (KN) 的关系列表 L KN (P, k), 记录着划分区域 P 中含有关键字 k 的顶点, 其中 key 为划分区
域和关键字的二元组, value 为顶点, 基于图 4 的划分结果可得到如图 6(b) 所示的 L KN (P, k).

L KP (a)={P 1 ,P 3 } L KN (P 4 , d)={11}
L KN (P 1 , a)={2}
L KP (d)={P 1 ,P 2 ,P 3 ,P 4 } L KN (P 3 , a)={0,17} L KN (P 1 , e)={7,8,9}
L KP (e)={P 1 }
L KN (P 1 , d)={7} L KN (P 1 , h)={3,4}
L KP (h)={P 1 ,P 2 ,P 4 } L KN (P 2 , d)={16} L KN (P 2 , h)={12,15,16}
L KN (P 4 , h)={5}
L KN (P 3 , d)={1}
(a) L KP (k) (b) L KN (P, k)
图 6 倒排索引

3.3 复杂度分析
构建统一索引结构的时间复杂度主要包括 5 个部分, 总体可以简化为图中顶点数 N V 与边数 N E 的函数: 第一,