有向图上k步可达查询处理

摘要：

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径.k步可达查询是一种基本的图操作并在过去十年间被广泛地研究.已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等.本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间.实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理.

关键词：有向图、k步可达查询、图压缩

所属期刊栏目：11

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家重点研发计划2017YFB0309800

在线出版日期：2021-03-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：8-13,19