判定大型图中可到达性的随机区间标记索引

Annotated random intervals indexing for reachability determination in large graphs

提出一种基于随机区间标记理论的可到达判定的方法 RIABG,它可以有效地处理非常大型的图,并且具有良好的可扩展性。RIABG具有线性的检索时间和空间复杂度,查询时间可以是常数时间,也可以根据图的大小而进行线性变化。真实数据集上的实验表明,RIABG可以有效处理大规模有向图的可达性判定问题。

This paper presented an indexing method based on the theory of annotated random intervals, called RIABG, to determine reachability, which could effectively execute on very large graph and provide good scalability. RIABG bore the linear indexing time and space complexity, its query time ranged from constant time to the size of the graph linearly. The experiments on real datasets show RIABG can effectively deal with reachability decision problem in large-scale directed graphs.