Dingyu Yang
Abstract
Shortest path query over a dynamic road network is a prominent problem for the optimization of real-time traffic systems. Existing solutions rely either on a centralized index system with tremendous pre-computation overhead, or on a distributed graph processing system such as Pregel that requires much synchronization effort. However, the performance of these systems degenerates with frequent route path updates caused by continuous traffic condition change.
In this paper, we build CANDS, a distributed stream processing platform for continuous optimal shortest path queries. It provides an asynchronous solution to answering a large quantity of shortest path queries. It is able to efficiently detect affected paths and adjust their paths in the face of traffic updates. Moreover, the affected paths can be quickly updated to the optimal solutions throughout the whole navigation process. Experimental results demonstrate that the performance for answering shortest path queries by CANDS is two orders of magnitude better than that of GPS, an open-source implementation of Pregel. In addition, CANDS provides fast response to traffic updates to guarantee the optimality of answering shortest path queries.
- Apache Giraph. http://giraph.apache.org/.Google Scholar
- Apache S4. http://incubator.apache.org/s4/.Google Scholar
- DIMACS. http://www.dis.uniroma1.it/challenge9/download.shtml/.Google Scholar
- GPS. http://infolab.stanford.edu/gps/.Google Scholar
- Infosphere Streams. http://www-01.ibm.com/software/data/infosphere/streams/.Google Scholar
- Spark. http://spark.incubator.apache.org/.Google Scholar
- Twitter Storm. https://github.com/nathanmarz/storm.Google Scholar
- I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In SODA, pages 782--793, 2010. Google ScholarDigital Library
- T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, pages 349--360, 2013. Google ScholarDigital Library
- H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566--566, 2007.Google ScholarCross Ref
- A. Biem, E. Bouillet, H. Feng, A. Ranganathan, A. Riabov, O. Verscheure, H. Koutsopoulos, and C. Moran. Ibm infosphere streams for scalable, real-time, intelligent transportation services. In SIGMOD, pages 1093--1104. ACM, 2010. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms, pages 319--333. Springer, 2008. Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In SODA, pages 156--165, 2005. Google ScholarDigital Library
- A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for a*: Efficient point-to-point shortest path algorithms. In ALENEX, volume 6, pages 129--143, 2006.Google ScholarCross Ref
- H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag. Adaptive fastest path computation on a road network: a traffic mining approach. In VLDB, pages 794--805. VLDB Endowment, 2007. Google ScholarDigital Library
- J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, pages 17--30, 2012. Google ScholarDigital Library
- A. Guerrero-Ibáñez, C. Flores-Cortés, P. Damián-Reyes, M. Andrade-Aréchiga, and J. Pulido. Emerging technologies for urban traffic management. Technical report, 2012.Google Scholar
- T. Hunter, T. M. Moldovan, M. Zaharia, S. Merzgui, J. Ma, M. J. Franklin, P. Abbeel, and A. M. Bayen. Scaling the mobile millennium system in the cloud. In SOCC, page 28, 2011. Google ScholarDigital Library
- G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359--392, 1998. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146. ACM, 2010. Google ScholarDigital Library
- N. Malviya, S. Madden, and A. Bhattacharya. A continuous query system for dynamic route planning. In ICDE, pages 792--803, 2011. Google ScholarDigital Library
- M. Rice and V. J. Tsotras. Graph indexing of road networks for shortest path queries with label restrictions. VLDB, 4(2):69--80, 2010. Google ScholarDigital Library
- P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In ESA, pages 568--579. Springer, 2005. Google ScholarDigital Library
- A. Thiagarajan, L. Ravindranath, K. LaCurts, S. Madden, H. Balakrishnan, S. Toledo, and J. Eriksson. Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones. In SenSys, pages 85--98. ACM, 2009. Google ScholarDigital Library
- H. Wei, Y. Wang, G. Forman, Y. Zhu, and H. Guan. Fast viterbi map matching with tunable weight functions. In SIGSPATIAL GIS, pages 613--616. ACM, 2012. Google ScholarDigital Library
- J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In SIGSPATIAL GIS, pages 99--108. ACM, 2010. Google ScholarDigital Library
- Y. Zheng, Y. Liu, J. Yuan, and X. Xie. Urban computing with taxicabs. In Ubicomp, pages 89--98, 2011. Google ScholarDigital Library
- A. D. Zhu, H. Ma, X. Xiao, S. Luo, Y. Tang, and S. Zhou. Shortest path and distance queries on road networks: towards bridging theory and practice. In SIGMOD, pages 857--868, 2013. Google ScholarDigital Library
Index Terms
- CANDS: continuous optimal navigation via distributed stream processing
Recommendations
A label-setting algorithm for finding a quickest path
The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate nondominated paths with distinct capacity, and then ...
Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Comments