Efficient Algorithms for Distance Problems in Large Networks

大型网络中距离问题的高效算法

• 批准号: RGPIN-2018-04607
• 负责人: Gu, Qianping
• 金额: $ 1.68万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750560
• 关键词: Efficient; Algorithms; Distance; Problems; Large

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.

图表中最短的距离/路径问题是计算机算法中最根本的问题之一，并且在运输，社交和信息网络等领域有许多应用。新的应用程序，例如地理信息系统，智能运输系统，社交网络分析系统和计算机网络管理系统的应用程序，希望在大型网络中获得远程查询的实时答案。对于这些新的挑战，这些新挑战最近受到了很多关注，经典的最短路径算法效率低下。解决新挑战的一种主要方法是开发两相算法，以预先计算一些距离信息，并将信息保留在数据结构中，称为Oracle，在第一阶段，并在第二阶段的甲骨文协助下回答距离查询。查询时间（第二阶段的时间）和Oracle大小（Oracle所需的存储空间）是评估算法的主要标准。具有较小查询时间和甲骨文大小的两阶段算法对于应对新挑战至关重要。已经开发了大量的两相算法。但是，这些算法存在局限性：对于大型网络中的新应用程序，它们的甲骨文尺寸太大；大多数算法都是复杂且难以实施的，因此在理论上只会变得有趣。这项研究的目标是开发新的两阶段算法，这些算法易于实现，并且在大型网络（例如运输网络，计算机网络和复杂的社交网络）中的理论和实践中都有较小的查询时间和甲骨文大小。