Shortest path and distance queries on road networks: towards bridging theory and practice
Shortest path and distance queries on road networks: towards bridging theory and practice
复制标题
DOI：
10.1145/2463676.2465277
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Diwen Zhu;Hui Ma;Xiaokui Xiao;Siqiang Luo;Youze Tang;Shuigeng Zhou
中科院分区：
文献类型：
--
作者：
Diwen Zhu;Hui Ma;Xiaokui Xiao;Siqiang Luo;Youze Tang;Shuigeng Zhou
给定道路网络中的两个位置s和t，距离查询返回从s到t的最小网络距离，而最短路径查询计算达到最小距离的实际路线。这两种类型的查询在实践中找到了重要的应用，并且在过去的几十年中已经提出了大量的解决方案。现有的解决方案，但是，优化的实际或渐近性能，但不是两者兼而有之。特别是，具有增强实用效率的技术大多是基于启发式的，并且它们在空间和时间方面提供了没有吸引力的最坏情况保证。另一方面，最坏情况下有效的方法通常需要禁止预处理或空间开销，这使得它们不适用于现代地图应用中常用的大型道路网络（具有数百万个节点）。本文提出了动脉层次（AH），一个索引结构，缩小了理论和实践之间的差距差距回答最短路径和距离查询的道路网络。在理论方面，我们证明了在一个现实的假设下，AH在n（log α）时间内回答任何距离查询，其中α = dmax/dmin，dmax（resp. dmin）是最大的（相应地，最小）道路网络中任意两个节点之间的L∞距离。此外，任何最短路径查询都可以在k（k + log α）时间内得到回答，其中k是最短路径上的节点数。在实践方面，我们在一个拥有多达2000万个节点的真实的道路网络上对AH进行了实验评估，我们证明了（i）AH在查询时间方面优于现有技术，（ii）其空间和预计算开销适中。
Given two locations s and t in a road network, a distance query returns the minimum network distance from s to t, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications. This paper presents Arterial Hierarchy (AH), an index structure that narrows the gap between theory and practice in answering shortest path and distance queries on road networks. On the theoretical side, we show that, under a realistic assumption, AH answers any distance query in Õ(log α) time, where α = dmax/dmin, and dmax (resp. dmin) is the largest (resp. smallest) L∞ distance between any two nodes in the road network. In addition, any shortest path query can be answered in Õ(k + log α) time, where k is the number of nodes on the shortest path. On the practical side, we experimentally evaluate AH on a large set of real road networks with up to twenty million nodes, and we demonstrate that (i) AH outperforms the state of the art in terms of query time, and (ii) its space and pre-computation overheads are moderate.