Efficient Algorithms for Distance Problems in Large Networks

图中最短距离/路径问题是计算机算法中最基本的问题之一，在交通、社会和信息网络等领域有许多应用。地理信息系统、智能交通系统、社会网络分析系统和计算机网络管理系统等新应用期望在大型网络中获得距离查询的实时答案。经典的最短路径算法对于这些近年来备受关注的新挑战是低效的。解决新挑战的主要方法是开发两阶段算法，该算法在第一阶段预先计算一些距离信息并将信息保存在一个称为oracle的数据结构中，在第二阶段在oracle的帮助下回答距离查询。查询时间（第二阶段的时间）和oracle大小（oracle所需的内存空间）是评估算法的主要标准。一种查询时间短、数据库大小小、适用于广泛应用的两阶段算法对于解决这些新挑战具有重要意义。大量的两阶段算法已经被开发出来。然而，这些算法也有局限性：它们的oracle大小对于大型网络中的新应用来说太大了；大多数算法都很复杂，难以实现，这使得它们只在理论上有趣。本研究的目标是开发新的两阶段算法，该算法在理论和实践上都简单，易于实现，查询时间和oracle大小都小，适用于交通网络、计算机网络和复杂的社会网络等大型网络的新应用

The shortest distance/path problems in graphs are among the most fundamental problems in computer algorithms and have numerous applications in areas such as transportation, social and information networks. New applications such as those in Geographic Information Systems, intelligent transportation systems, social network analysis systems, and computer network management systems expect to get a real time answer for a distance query in large networks. Classical shortest path algorithms are inefficient for these new challenges which have received much attention recently. A major approach to address the new challenges is to develop two-phase algorithms which pre-compute some distance information and keep the information in a data structure, called oracle, in phase one and answer distance queries with the assistance of the oracle in phase two. The query time (time in phase two) and oracle size (memory space required by the oracle) are major criteria for evaluating the algorithms. A two-phase algorithm with a small query time and oracle size for a wide range of applications is of great importance to address the new challenges. A large number of two-phase algorithms have been developed. However there are limitations in these algorithms: their oracle sizes are too large for new applications in large networks; most algorithms are complex and difficult to implement, making them only theoretically interesting. The goals of this research are to develop new two-phase algorithms which are simple and easy to implement, and have small query time and oracle size in both theory and practice for new applications in large networks such as transportation networks, computer networks and complex social networks.**