DOS: a spatial system offering extremely high-throughput road distance computations
DOS: a spatial system offering extremely high-throughput road distance computations
复制标题
DOI：
10.1145/3274895.3274898
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Shangfu Peng;Jagan Sankaranarayanan;H. Samet
中科院分区：
文献类型：
--
作者：
Shangfu Peng;Jagan Sankaranarayanan;H. Samet
在道路网络上的大型分析应用，包括模拟、物流、基于位置的广告和交通规划，需要提供高吞吐量(即每秒的距离/时间计算)的最短距离/时间方法。我们之前的工作讨论了如何在大型道路网络上的PostgreSQL数据库中处理图形距离计算，例如每台机器每秒60K距离计算，如何通过使用Spark集群实现每台机器每秒73.8K距离计算的横向扩展，以及如何在内存中为城市规模的道路网络获得极高吞吐量的解决方案，例如每秒6.7m距离计算。然而，没有一种解决方案可以为大型公路网实现超过100万的吞吐量。在工业环境中，即使使用多线程，大多数最先进的解决方案也能在每台机器上实现每秒5K-10K的最短距离计算。在本文中，我们提出了一种新的用于大型路网的距离预言系统(DOS)。它可以解决大多数空间分析查询，其吞吐量达到每秒5M距离计算，即使在整个美国公路网上也是如此。例如，10K×10K原点距离(OD)矩阵可以在20秒内计算出来。
Large analytic applications on road networks including simulations, logistics, location-based advertisement, and transportation planning require shortest distance/time methods that provide high throughput (i.e., distance/time computations per second). Our previous work discussed how to process graph distance computations in a PostgreSQL database on a large road network, e.g., 60K distance computations per second per machine, how to "scale out" by using a Spark cluster to achieve 73.8K distance computations per second per machine, and how to obtain a extremely high-throughput solution in memory for city-sized road networks, e.g., 6.7M distance computations per second. However, there is no solution that could achieve more than 1M throughput for large road networks. In an industrial setting, most state-of-the-art solutions yield 5K - 10K shortest distance computations per second per machine even with multi-threads. In this paper, we propose a new distance oracle system (DOS) for large road networks. It can solve most spatial analytic queries, and its throughput achieves 5M distance computations per second even on the whole USA road network. For example, a 10K × 10K origin-distance (OD) matrix can be computed in 20 seconds.