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

摘要

For the high cost of reachability index of the large-scale graph,an index method based on dual interval labeling is proposed.Each node is assigned a main interval and an auxiliary interval by GIDIL.The two intervals are applied to store the reachability information of the original graph.The reachability information of the spanning tree is recorded by the main interval,and the reachability information of non-tree edge is recorded by the auxiliary interval.The reachability algorithm based on the index method is designed to effectively process the reachability query of graph.Experimental results show that the method can ensure reachability query performance,build the index more quickly and can be extended to large scale graph.%针对大规模图的可达性索引代价过大问题,提出一种基于双区间标签的索引方法.该方法为每个节点分配主区间和辅助区间,应用这2个区间保存原图的可达性信息,主区间记录生成树的可达性信息,辅助区间记录非树边可达性信息.基于此索引设计了可达性算法,可实现图的可达性查询.实验结果表明,该方法能够在保证可达性查询性能的情况下,更快地构建可达性索引,并且可以扩展到大规模图.