软件学报

作者：陈迪，袁野，潘雅妮，王国仁

单位：陈迪，东北大学 计算机科学与工程学院, 辽宁 沈阳 11016911,袁野，北京理工大学 计算机学院, 北京 10008102,潘雅妮，东北大学 计算机科学与工程学院, 辽宁 沈阳 11016903,王国仁，北京理工大学 计算机学院, 北京 10008104

关键词：统一索引;可达查询;最短路径查询;关键字查询;图匹配查询

基金：国家重点研发计划(2022YFB2702100); 国家自然科学基金(62225203, U21A20516)

现实世界中许多应用场景都可以用图数据表示, 图上的查询也具有广泛的应用, 如可达、最短路径、关键字、图匹配、PageRank、SimRank、k-core、k-truss和Clique等. 针对特定的查询问题, 目前的研究方法可概括为: 提出相应的查询处理算法, 并构建索引结构来加速查询. 然而, 现实应用中需求的多样化以及图数据规模爆炸式的增长为该研究方法带来了两方面挑战: 第一, 同一个图数据在应用中会涉及多种查询, 但针对不同查询问题的处理机制和索引结构均不相同, 因此在设计图数据库时需构建多个索引和相应的查询算法; 第二, 索引的规模通常比原图数据的规模大, 多个索引同时存在会占用大量的系统空间, 导致图数据库的性能急剧下降, 不能被真正地应用. 为应对上述挑战, 提出一种统一的查询处理机制, 即为大图数据构建统一且高效的索引结构, 并基于统一索引结构设计可达、最短路径、关键字和图匹配这4种查询处理算法. 为构建统一索引结构, 对大图数据进行划分, 并根据可达、最短路径、关键字和图匹配这4种查询的特点提取出图数据中的重要顶点, 该统一索引结构规模比图数据规模小, 并且能高效地支持上述4种查询. 最后, 通过在4组真实数据上的实验验证了统一索引结构和4种查询处理算法的高效性和扩展性.

来源：2026年第5期

《软件学报》期刊编辑部

查看软件学报杂志2026年第5期