An reachability index for large-scale graph based on dual interval labeling
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.
国家科技期刊平台
NSTL
万方数据
维普
