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

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

其中, r 为查询结果的根, n i 是查询结果对 q k 中每个关键字 w i 的匹配. 由上述的连接性可知查询结果是一棵
子树, 其根顶点 r 可达的顶点包含了待查询的所有关键字. 例如, 我们在图 3 所示的 G 中查找关于关键字组 q k =(b,
f) 时, 可得到 t 1 =< 1,(1,3) > 和 t 2 =< 0,(0,8) > 等多种查询结果.
关键字匹配查询往往会返回多个查询结果 t i , 而一般情况仅需最优或 top-k 结果, 因此需对返回的 t i 进行评价,
∑
m
评价函数 S (t) = D s (r,n i ), 其中 t =< r,(n 1 ,n 2 ,...,n m ) >, D s (r, n i ) 为在图 G 中根顶点 r 到含有关键字 w i 顶点 n i
i=1
的最短路径的距离, 评价函数值越小, 其结果越优. 例如, 对于上文中 t 1 =< 1,(1,3) > 和 t 2 =< 0,(0,8) > 这两种查询
结果而言, S(t 1 ) = 1, S(t 2 )=3, 则可说 t 1 的结果优于 t 2 .
定义 5. 图匹配查询. 给定图 G 和模式图 q m =(V q , E q , L q ), 返回的子图 g 与模式图 q m 图同构. 若子图 g=(V g , E g ,
L g ) 同构于模式图 q m , 则存在一种映射关系 f, 使得模式图 q m 中的顶点可一一映射到子图 g 中的顶点, 即
f : V q → V g , 且满足如下两个条件.
(1) 顶点映射: 对于模式图 q m 中任意顶点, 其标签与映射顶点的标签相同, 即 ∀v ∈ V q , L q (v) = L( f(v)).
(2) 边映射: 对于模式图 q m 中的每一条边 (u, v), 顶点 u 和顶点 v 映射的顶点在子图 g 中也存在一条边, 即
∀e = (u,v) ∈ E q , ( f(u), f(v)) ∈ E g .
定义 6. 统一的大图查询处理机制. 当给定图数据 G 后, 构建统一索引结构, 并基于统一索引结构实现图 G 中
可达、最短路径、关键字和图匹配这 4 种查询问题.
3 统一索引的构建

本节将介绍统一索引结构的构建, 主要思想是: 首先基于疏密性对图数据进行划分; 然后根据可达、最短路径、
关键字和图匹配这 4 种查询的特点提取出各划分区域的重要顶点; 最后基于划分和提取出的重要顶点构建统一的
索引结构.
3.1 图划分算法
映射现实世界的大图数据全局来看是稀疏的, 而局部来看却是稠密的 [10] , 因此本文基于疏密性对图数据进行
划分. 基于疏密性划分后, 每一划分区域中存在一些重要顶点, 它们决定着该区域的拓扑结构 [8] , 本文在划分后还
需记录这些重要顶点, 供统一索引结构构建时使用.
每一划分区域是由未被划分的顶点 u, 以及与顶点 u 距离小于等于 ε 且未被划分的顶点集合构成. 其中, 顶点
u 为该划分区域的中心顶点; 该划分区域中入度大于 0 且存在顶点来源于其他划分区域的顶点为入边界顶点; 该
划分区域中出度大于 0 且存在顶点指向其他划分区域的顶点为出边界顶点.
P = (P 1 ,P 2 ,...,P k ), k 为划分区域的个数, 并且
当所有顶点都有所属的划分区域后则停止划分, 得到划分覆盖
∪
满足 P i = V, 当 i , j 时, P i ∩ P j = ∅. 为得到最小划分覆盖, 本文的划分策略是: 总是选取当前不属于任何划分区
域且度最大的顶点作为新划分区域的中心顶点, 这里的度是指出度与入度的和, 并从该顶点开始 ε 步的双向广度
优先遍历得到新的划分区域. 因此在划分前, 需将图 G 中的顶点按照度的大小进行排序, 以加速启发式地生成最
小划分覆盖.
图划分算法 GD (graph division) 的流程如算法 1 所示. 第 1 行对结果初始化. 第 2 行将图 G 中的顶点按照度
排序并存放在队列 Q 中. 第 3–12 行生成以 u 为中心顶点的划分区域 P i . 第 5 行将顶点 u 添加到中心顶点集合 C
和当前划分区域 P i 中. 第 6–10 行将从 u 双向广度优先遍历并找到距离小于 ε 的新顶点添加到 P i 中. 第 11 行将新
得到的划分区域 P i 压入近优划分覆盖 P 中; 直到 Q 为空停止循环, 得到近优的划分覆盖 P. 第 13 行在将遍历图
G 并获得各划分区域的入边界顶点集合和出边界顶点集合. 图划分算法 GD 结束后, 便直接返回近优划分覆盖 P、
中心顶点集合 C、出边界顶点集合 OUT 和入边界顶点集合 IN 这 4 部分内容.
算法 1. 图划分算法 GD.
输入: 图数据 G, 非负整数 ε;
输出: 近优划分覆盖 P, 中心顶点集合 C, 入边界顶点集合 IN, 以及出边界顶点集合 OUT.