CDO: extremely high-throughput road distance computations on city road networks
CDO: extremely high-throughput road distance computations on city road networks
复制标题
DOI：
10.1145/2996913.2996921
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Shangfu Peng;H. Samet
中科院分区：
文献类型：
--
作者：
Shangfu Peng;H. Samet
道路网络上的一些分析查询通常集中在一个跨越几个城市的局部区域，需要高吞吐量的解决方案，例如每秒执行数百万次最短距离计算。然而，大多数现有的解决方案即使在多线程的情况下，每台机器每秒的最短距离计算也不到5000次。我们展示了一个名为城市距离Oracle的解决方案，使用我们之前开发的ε-Distance Oracle，在城市道路网络上实现了每台商品机器每秒多达700万次最短距离计算，即10K×10K原点-距离(OD)矩阵可以在14秒内完成。
Some analytic queries on road networks, usually concentrating in a local area spanning several cities, need a high-throughput solution such as performing millions of shortest distance computations per second. However, most existing solutions achieve less than 5, 000 shortest distance computations per second per machine even with multi-threads. We demonstrate a solution, termed City Distance Oracles (CDO), using our previously developed ε-distance oracle to achieve as many as 7 million shortest distance computations per second per commodity machine on a city road network, i.e., 10K × 10K origin-distance (OD) matrix can be finished in 14 seconds.