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

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

本文的主要贡献如下.
(1) 提出了统一的大图数据查询处理机制, 即基于统一索引结构便可解决大图上的多种查询问题.
(2) 构建了统一的索引结构, 其规模比原图数据要小, 且能支持可达、最短路径、关键字和图匹配这 4 种查询.
(3) 基于统一索引结构, 设计了可达、最短路径、关键字和图匹配这 4 种查询算法.
(4) 通过在 4 组真实数据集上的实验验证了统一索引结构和查询处理算法的高效性与扩展性.

可达查询算法

最短路径查询算法
图数据G 构 统一索引 加
建
速
关键字查询算法

图匹配查询算法
图 2 统一查询处理机制框架

本文第 1 节介绍相关工作. 第 2 节介绍大图和本文重点研究的 4 种查询问题的基础知识, 并给出本文研究内
容的问题定义. 第 3 节介绍大图划分和统一索引结构的构建. 第 4 节介绍基于统一索引结构设计的可达、最短路
径、关键字和图匹配这 4 种查询算法. 第 5 节介绍在 4 组不同数据集上进行实验并分析结果. 第 6 节进行工作总结.

1 相关工作

由于最短路径查询算法普遍也可解决可达查询, 因此本节将对现有的大图压缩技术以及最短路径、关键字和
图匹配这 3 种查询算法做简要介绍与对比.
1.1 大图压缩技术
目前人们倾向于存储预处理信息或者建立索引来压缩大图数据. 大图的存储压缩主要包括对邻接链表和邻接
矩阵的压缩, 或者结合图的特征进行压缩.
Claude 等人 [14] 提出了 Re-Pair 算法完成对邻接链表的压缩, 该算法将邻接链表存储为一个字符序列, 重复在
这个字符序列中寻找最频繁的字符对, 用新字符替换频繁字符对, 并将新字符和频繁字符对的映射关系存储到字
2
典中, 直到字符序列中所有字符仅出现一次停止替换. k 树算法 [15] 可对邻接矩阵进行压缩, 该算法将邻接矩阵等
2
2
分成 k 个正方形, 每个正方形中都含有叶顶点和内顶点, 每个顶点都用 1 bit 来表示, 使得 k 树中存在很多数值为
0 的内顶点, 从而会减少内存空间. 压缩邻接矩阵或者邻接链表这些方法可以减少对内存的消耗, 但这些方法并没
有利用到图数据本身的特点, 很难做到有效地提高查询效率.
结合图特征压缩后形成的预处理信息或是索引结构均可明显加快算法的执行速度, 越来越多的研究人员开始重
视这一领域的研究内容. 现有 3 种结合图特征的压缩方法: 其一是基于聚合进行压缩, 其使用超级顶点和超级边来构
建索引, 有助于理解和可视化复杂图数据, 并可以减少存储内存; 其二是基于属性进行压缩, 利用拓扑结构和大图中
点边之间的相关属性形成小规模图, Rossi 等人 [16] 提到了一种将大图分解成多个团以减少大图中边的数量的方法;
其三是采用编码技术进行压缩. 其中最适合我们所研究的带有标签的有向加权无环图的解决方法是上述压缩方法中
的第 2 种. Yu 等人 [17] 提出的 BL 图索引技术只需要线性的时间和空间. 使用 BL 可以在不到 16 ms 的时间内回答平
均有 160 万个节点的图数据的可达性查询. 但是其压缩后的小规模图仅适合进行可达查询, 并不适合于最短路径、
关键字以及图匹配这 3 种查询. 本文提出的统一大图索引技术所压缩后的小规模图将同时适用于以上 4 种图查询.
1.2 最短路径查询算法
现已存在很多经典的最短路径查询算法, 比如对于无权图数据而言, 即边的权重始终为 1, 则可以采用广度优
先遍历的方法进行最短路径查询; 再如对于有权图数据而言, Dijkstra 算法和 Floyd 算法均被广泛用于解决最短路