基于大规模网络的可达性研究

Research on the Reachability of Large Scale Network

大多数现有的可达性索引方法在中小型网络上表现良好,但在规模约为100万个顶点/边的网络中遇到可扩展性的瓶颈。随着网络规模的日益扩大,可扩展性正迅速成为当今可达性查询的主要挑战。提出一个统一的可达性查询框架MRN(多解析度网络):它不仅可以扩展现有的只能在中等规模的网络上执行的可达性索引方法,否则构建和工作,还可以加快可达性查询。实验结果表明,MRN可以在数百万个顶点/边缘的网络上执行,也比一些最先进的可伸缩性索引方法快得多。

Most of existing reachability indices perform well on small-to-medium size network, but reach a scalability bottleneck around one million vertices/edges. As the scales of networks become increasingly large, scalability is quickly becoming the major research challenge for the reachability query today. Proposes MRN, a unified reachability query framework： it not only can scale the existing state-of-the-art reach- ability indices, which otherwise could only be constructed and work on moderate size networks, but also can help speed up the online query answering approaches. The experimental results demonstrate that MRN can perform on networks with millions of vertices/edges and is also much faster than some the state-of-the-art scalability index approach.