10.3969/j.issn.2095-2163.2021.01.003
有向图上k步可达查询处理
给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径.k步可达查询是一种基本的图操作并在过去十年间被广泛地研究.已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等.本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间.实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理.
有向图、k步可达查询、图压缩
11
TP301.6(计算技术、计算机技术)
国家重点研发计划2017YFB0309800
2021-03-23(万方平台首次上网日期,不代表论文的发表时间)
共7页
8-13,19