基于双向双区间标签实现k步可达性查询

摘要：

近年来,图的可达性查询已经成为一个研究热点.传统的可达性查询算法———GRAIL在处理 k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的 k步可达性查询.为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了 k步可达性查询问题.最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证.实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能.

关键词：k步可达性查询、不同分支、双向、双区间

所属期刊栏目：45

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61673159;河北省自然科学基金F2016202145;黑龙江省自然科学基金F2017019;河北省科技计划项目15210325;河北省教育厅青年基金Q N2014192

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

页数：共4页

页码：178-181