Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks
Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks
复制标题
DOI：
10.14778/3015274.3015277
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Sibo Wang;Xiaokui Xiao;Y. Yang;Wenqing Lin
中科院分区：
文献类型：
--
作者：
Sibo Wang;Xiaokui Xiao;Y. Yang;Wenqing Lin
在约束最短路径(CSP)查询中，道路网络中的每条边都与长度和成本相关联。在给定起点S、终点t和费用约束θ的情况下，目标是找到从S到t的总费用不超过θ的最短路径。由于精确CSP问题是NP难的，以往的工作主要集中在近似解上。即便如此，现有的方法对于大型公路网来说仍然昂贵得令人望而却步。两个主要原因是：(I)它们没有利用道路网络的特殊性质；(Ii)它们中的大多数处理没有索引的查询；现有的少数几个索引消耗了大量的内存，但在降低查询成本方面效果有限。受此启发，我们提出了COLA，这是第一个针对大型路网上的近似CSP处理的实用解决方案。Cola利用了这样一个事实，即道路网络可以被有效地划分，并且存在一组相对较小的标志性顶点，这些顶点通常出现在CSP结果中。相应地，COLA对位于分区边界上的顶点进行索引，并应用一种名为α-DIJK的动态算法进行分区内的路径计算，该算法基于地标有效地修剪路径。广泛的实验表明，在大陆大小的道路网络上，Cola在亚秒级的时间内回答一个近似的CSP查询，而现有的方法需要几个小时。有趣的是，即使没有索引，可乐中的α-Dijk算法的性能仍然比以前的解决方案高出一个数量级以上。
In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, previous work mostly focuses on approximate solutions. Even so, existing methods are still prohibitively expensive for large road networks. Two main reasons are (i) that they fail to utilize the special properties of road networks and (ii) that most of them process queries without indices; the few existing indices consume large amounts of memory and yet have limited effectiveness in reducing query costs. Motivated by this, we propose COLA, the first practical solution for approximate CSP processing on large road networks. COLA exploits the facts that a road network can be effectively partitioned, and that there exists a relatively small set of landmark vertices that commonly appear in CSP results. Accordingly, COLA indexes the vertices lying on partition boundaries, and applies an on-the-fly algorthm called α-Dijk for path computation within a partition, which effectively prunes paths based on landmarks. Extensive experiments demonstrate that on continent-sized road networks, COLA answers an approximate CSP query in sub-second time, whereas existing methods take hours. Interestingly, even without an index, the α-Dijk algorithm in COLA still outperforms previous solutions by more than an order of magnitude.