Ziqiang Yu
Xiaohui Yu
ABSTRACT
The problem of identifying the k -shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the (i+1)-th shortest path is generated based on the i-th shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifying k-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.
Supplemental Material
- Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM SIGMOD International Conference on Management of Data, 2013. 349--360.Google Scholar
Digital Library
- Anonymous. 2019. Anonymous technique report. (2019).Google Scholar
- Sabeur Aridhi, Philippe Lacomme, Libo Ren, and Benjamin Vincent. 2015. A MapReduce-based approach for shortest path problem in large-scale networks. Engineering Applications of Artificial Intelligence, Vol. 41 (2015), 151--165.Google ScholarDigital Library
- Baruch Awerbuch. 1989. Distributed Shortest Paths Algorithms. In Proceedings of the 21th annual ACM symposium on Theory of computing, 1998. 490--500.Google Scholar
- Fleischmann Bernhard, Gietz Martin, and Gnutzmann Stefan. 2004. Time-Varying Travel Times in Vehicle Routing. Transportation Science, Vol. 38, 2 (2004), 121--255.Google Scholar
- K Mani Chandy and Jayadev Misra. 1982. Distributed computation on graphs: Shortest path algorithms. Programming Techniques and Data Structures (1982), 833--837.Google ScholarDigital Library
- Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Jian Pei. 2015. Efficiently computing top-k shortest path join. In Proceedings of the 18th International Conference on Extending Database Technology (EDBT), 2015. 133--144.Google Scholar
- DIMACS. 2005. http://users.diag.uniroma1.it/challenge9. (2005).Google Scholar
- Michael Elkin. 2017. Distributed exact shortest paths in sublinear time. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, 2017. 757--770.Google ScholarDigital Library
- David Eppstein. 1998. Finding the k shortest paths. SIAM Journal on computing, Vol. 28, 2 (1998), 652--673.Google Scholar
- Wenfei Fan, Xin Wang, and Yinghui Wu. 2012. Performance guarantees for distributed reachability queries. In Proceedings of the VLDB Endowment, 2012, Vol. 5. 1304--1316.Google ScholarDigital Library
- Sebastian Forster and Danupon Nanongkai. 2018. A Faster Distributed Single-Source Shortest Paths Algorithm. In IEEE 59th Annual Symposium on Foundations of Computer Science, 2018 .Google ScholarCross Ref
- Jun Gao, Huida Qiu, Xiao Jiang, Tengjiao Wang, and Dongqing Yang. 2010. Fast top-k simple shortest paths discovery in graphs. In 19th ACM International Conference on Information and Knowledge Management, 2010. 509--518.Google ScholarDigital Library
- Jun Gao, Jeffrey Yu, Huida Qiu, Xiao Jiang, Tengjiao Wang, and Dongqing Yang. 2012. Holistic top-k simple shortest path join in graphs. IEEE Transactions on Knowledge and Data Engineering, Vol. 24, 4 (2012), 665--677.Google ScholarDigital Library
- Mohsen Ghaffari and Jason Li. 2018. Improved Distributed Algorithms for Exact Shortest Paths. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018 .Google ScholarDigital Library
- Jiawei Han, Jian Pei, and Yiwen Yin. 2000. Mining frequent patterns without candidate generation. In ACM SIGMOD International Conference on Management of Data, 2000. 1--12.Google ScholarDigital Library
- Bast Hannah, Delling Daniel, Goldberg Andrew, Muller-Hannemann Matthias, Pajor Thomas, Sanders Peter, Wagner Dorothea, and Renato F. Werneck. 2016. Route Planning in Transportation Networks. Algorithm Engineering (2016), 19--80.Google Scholar
- John Hershberger, Matthew Maxel, and Subhash Suri. 2007. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, Vol. 3, 4 (2007).Google ScholarDigital Library
- John Hershberger and Subhash Suri. 2001. Vickrey prices and shortest paths: What is an edge worth?. In IEEE International Conference on Cluster Computing, 2001. 252--259.Google ScholarCross Ref
- Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. 1982. An efficient algorithm for k shortest simple paths. Networks, Vol. 12, 4 (1982), 411--427.Google ScholarCross Ref
- Huiping Liu, Cheqing Jin, Bin Yang, and Aoying Zhou. 2018. Finding top-k shortest paths with diversity. IEEE Transactions on Knowledge and Data Engineering, Vol. 30, 3 (2018), 488--502.Google ScholarCross Ref
- Kun Qiu, Yuanyang Zhu, Jing Yuan, Jin Zhao, Xin Wang, and Tilman Wolf. 2018. ParaPLL: Fast Parallel Shortest-path Distance Query on Large-scale Weighted Graphs. In Proceedings of the 47th International Conference on Parallel Processing, 2018 .Google ScholarDigital Library
- Grégoire Scano, Marie-José Huguet, and Sandra Ulrich Ngueveu. 2015. Adaptations of k-shortest path algorithms for transportation networks. In International Conference on Industrial Engineering and Systems Management, 2015. 663--669.Google ScholarCross Ref
- Rahul C Shah and Jan M Rabaey. 2002. Energy aware routing for low energy ad hoc sensor networks. In IEEE Wireless Communications and Networking Conference Record, Vol. 1. 350--355.Google ScholarCross Ref
- Apache Storm. 2019. http://storm.apache.org/.Google Scholar
- Dingyu Yang, Dongxiang Zhang, Kian-Lee Tan, Jian Cao, and Frédéric Le Mouël. 2014. CANDS: continuous optimal navigation via distributed stream processing. In Proceedings of the VLDB Endowment, 2014. 137--148.Google ScholarDigital Library
- Jin Y. Yen. 1971. Finding the k shortest loopless paths in a network. Management Science, Vol. 17, 11 (1971), 712--716.Google ScholarDigital Library
- Libin Zheng, Lei Chen, and Jieping Ye. 2018. Order Dispatch in Price-aware Ridesharing. In Proceedings of the VLDB Endowment, 2018 .Google ScholarDigital Library
- Libin Zheng, Peng Cheng, and Lei Chen. 2019. Auction-Based Order Dispatch and Pricing in Ridesharing. In IEEE 35th International Conference on Data Engineering (ICDE), 2019 .Google Scholar
Index Terms
- Distributed Processing of k Shortest Path Queries over Dynamic Road Networks
Recommendations
Processing time-dependent shortest path queries without pre-computed speed information on road networks
Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations ...
Dynamic Shortest Path Queries over Moving Objects on Road Networks
Spatial Data and IntelligenceAbstractWith the development of intelligent mobile devices and communication technology, moving objects have become a hot research topic. This paper studies the moving objects on the road network, and a dynamic shortest path query algorithm is proposed to ...
Low time complexity algorithms for path computation in Cayley Graphs
AbstractWe study the problem of path computation in Cayley Graphs (CG) from an approach of word processing in groups. This approach consists in encoding the topological structure of CG in an automaton called Diff, then techniques of word ...
Comments