面向大规模图数据的分布式可达性索引与查询策略

摘要

Aiming at the problem of long construction time,high storage cost and long response time of reachability index of large graph,a Distributed Reachability Index and Query (DRIQ) strategy is proposed in this paper.Large graph is partitioned into several small subgraphs without destroying the reachability of the nodes.And reachability indexes are created for each subgraph distributed and parallel to improve the efficiency of index creating.Some methods are designed to keep the reachability of the nodes in the subgraphs and the reachability of the nodes between the subgraphs in DRIQ,which can ensure the correctness of the reachability query based on DRIQ.Experimental results show that the strategy is highly efficient and scalable,compared with the traditional reachability query method.%针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ).在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率.给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性.实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性.