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

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

2. FOR P i ∈ P DO
3. g(i) ← ∅, flag ← false;
∈ sp DO
4. FOR sp j
5. sg j (i) ← sub-PM(P i , sp j );
6. IF sg j (i) is empty THEN
7. flag ← true;
8. BREAK;
9. END IF
10. END FOR
11. IF flag == false THEN
12. g(i) ←⋈ sg j (i);
13. END IF
14. END FOR
∪
15. g ← g(i);
16. RETURN g.
例如, 在图 3 中匹配图 8(a) 所示的模式图 q m 时, 由于在划分区域 P 1 、P 2 和 P 4 中都无法匹配模式子图 sq 1 ,
即 sg 1 (1)= ∅、sg 1 (2)= ∅ 且 sg 1 (4)= ∅, 则可直接返回 g(1)= ∅、g(2)= ∅ 和 g(4)= ∅. 第 4.4.2 节中我们给出划分区域
P 3 中匹配模式子图 sq 1 的过程, 在此不再赘述. 当在 P 3 中分别匹配模式子图 sq 2 和 sq 3 时, 都可找到相应的匹配顶
点, 各匹配子图做连接操作后可得 g = ∪ 4 g(i) = g(3).
g(3)={17, 0, 1, 3, 2, 7}. 则最终结果
i=1
图匹配查询算法的时间复杂度主要由 3 部分构成, 其一是划分模式图 q m 消耗一定的时间, 计算各顶点的选择
性并进行排序需消耗时间 O( N V m ·logN V m ), 其中 N V m 是模式图中顶点的总数; 还需消耗时间 O( E V m ) 逐一覆盖模式
图 q m 为模式图 q m 中边的总数. 其二是在各划分区域 P i 中匹配模式图 q m 消耗一定时间, 匹配一
中的边, 其中
E V m
个模式子图需消耗的时间为 O(N j · (N 1 (u) + E 1 (u))), 若模式图 q m 可划分为 n 个模式子图 sq j , 则匹配模式图 q m 的
时间为匹配一个模式子图时间的 n 倍, 即 n · O(N j · (N 1 (u) + E 1 (u))), 最终连接 n 个模式子图 sq j 的匹配子图所需的
2
时间为 O(N j ), 其中 N j 为模式子图 sq j 中顶点的个数, N 1 (u) 和 E 1 (u) 为从顶点 u 广度优先遍历一步访问到的顶点
数和边数. 其三则是消耗常量时间对各划分区域的匹配结果做并集操作.
5 实验分析

本文选取了 4 组真实数据集, 为每组数据构建统一索引结构, 并执行本文提出的查询算法, 与现有非统一处理
机制和高效的查询算法进行比较.
5.1 实验环境与数据集

实验环境: CPU 为 i5@3.30 GHz, 内存 8 GB, 硬盘 500 GB, 编程环境 GNU C.
实验数据集: 本文 4 组数据集的详细信息见表 1, 都是稀疏有向并带有标签的无环大规模数据图.

表 1 实验数据集

编号 数据集 顶点数 (k) 边数 (k) 标签数
1 WordNet 82 133 5
2 DBLP 409 591 6k
3 US Patent 3 774 16 522 416
4 Facebook 17 672 103 576 22 104k