Seamless Interpolation Between Contraction Hierarchies and Hub Labels for Fast and Space-Efficient Shortest Path Queries in Road Networks
Seamless Interpolation Between Contraction Hierarchies and Hub Labels for Fast and Space-Efficient Shortest Path Queries in Road Networks
复制标题
收缩层次结构和集线器标签之间的无缝插值，用于道路网络中快速且节省空间的最短路径查询
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Funke
中科院分区：
文献类型：
--
作者：
S. Funke
我们提出了一个概念上的简单但非常有效的扩展，对众所周知的收缩层次结构（CH）加速技术，将查询时间改善了道路网络中最短路径的查询时间，一个数量级，头顶上的空间非常适中。使用我们的方案，我们能够在标准工作站硬件上的微秒范围内在大陆大小的道路网络上回答大陆大小的道路网络的查询。以前的方法比CH的速度要快得多，仅用于最短的路径距离查询（恢复实际路径需要额外的努力和空间），或者遭受巨大的空间消费障碍，阻碍了其实用性对于大型现实世界的道路网络。我们的方法可以解释为收缩层次结构和集线器标签之间的无缝插值。
We propose a conceptually simple, yet very effective extension of the highly popular Contraction Hierarchies (CH) speedup technique improving query times for shortest paths in road networks by one order of magnitude with very modest space overhead. Using our scheme we are able to answer queries on continental-sized road networks with more than half a billion edges in the microseconds range on standard workstation hardware. Previous approaches that are considerably faster than CH were only for shortest path distance queries (recovering the actual path required additional effort and space) or suffered from humongous space consumption hindering their practicality for large real-world road networks. Our approach can be interpreted as a seamless interpolation between Contraction Hierarchies and Hub Labels.
DOI：
10.1007/978-3-319-49487-6_2
发表时间：
2016-01-01
期刊：
ALGORITHM ENGINEERING: SELECTED RESULTS AND SURVEYS
影响因子：
--
作者：
Bast, Hannah;Delling, Daniel;Werneck, Renato F.
通讯作者：
Werneck, Renato F.