基于双区间标签的大规模图可达性索引

摘要：

针对大规模图的可达性索引代价过大问题,提出一种基于双区间标签的索引方法.该方法为每个节点分配主区间和辅助区间,应用这2个区间保存原图的可达性信息,主区间记录生成树的可达性信息,辅助区间记录非树边可达性信息.基于此索引设计了可达性算法,可实现图的可达性查询.实验结果表明,该方法能够在保证可达性查询性能的情况下,更快地构建可达性索引,并且可以扩展到大规模图.

关键词：区间标签、可达性、图、索引

所属期刊栏目：37

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

资助基金：广西自然科学基金2016GXNSFDA380006

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

页数：共5页

页码：302-306