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

摘要

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