Dian Ouyang
Skip Abstract Section
Abstract
Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index, of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.
- Crowdsourcing Transportation Systems Data, Michigan Department of Transportation. Available at https://www.michigan.gov/documents/mdot/02-14-2015_Crowd_Sourced_Mobile_Applications_483062_7.pdf.Google Scholar
- https://www.tomtom.com/automotive/products-services/connected-services/tomtom-traffic/.Google Scholar
- Road traffic injuries. https://www.who.int/news-room/fact-sheets/detail/road-traffic-injuries.Google Scholar
- Statistical Report on Internet Development in China, China Internet Network Information Center. Available at https://cnnic.com.cn/IDR/ReportDownloads/201807/P020180711391069195909.pdf.Google Scholar
- Taxi and Ridehailing Usage in New York City. https://toddwschneider.com/dashboards/nyc-taxi-ridehailing-uber-lyft-data/.Google Scholar
- TomTom Real Time Traffic Information, TomTom White Paper. Available at https://www.tomtom.com/lib/img/REAL_TIME_TRAFFIC_WHITEPAPER.pdf.Google Scholar
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Proceedings of SEA, pages 230--241, 2011.Google ScholarCross Ref
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of ESA, pages 24--35, 2012.Google ScholarDigital Library
- T. Akiba, Y. Iwata, K. Kawarabayashi, and Y. Kawata. Fast shortest-path distance queries on road networks by pruned highway labeling. In Proceedings of ALENEX, pages 147--154, 2014.Google ScholarCross Ref
- J. Arz, D. Luxen, and P. Sanders. Transit node routing reconsidered. In Proceedings of SEA, pages 55--66, 2013.Google ScholarCross Ref
- H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. In Algorithm engineering, pages 19--80. 2016.Google ScholarCross Ref
- H. Bast, S. Funke, and D. Matijevic. Ultrafast shortest-path queries via transit nodes. In Proceedings of DIMACS, The Shortest Path Problem Workshop, pages 175--192, 2006.Google Scholar
- G. V. Batz, D. Delling, P. Sanders, and C. Vetter. Time-dependent contraction hierarchies. In Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, pages 97--105, 2009.Google ScholarCross Ref
- G. V. Batz, R. Geisberger, S. Neubauer, and P. Sanders. Time-dependent contraction hierarchies and approximation. In Proceedings of SEA,, pages 166--177, 2010.Google ScholarDigital Library
- P. Carbone, A. Katsifodimos, S. Ewen, V. Markl, S. Haridi, and K. Tzoumas. Apache flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4), 2015.Google Scholar
- K. L. Cooke and E. Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14(3):493--498, 1966.Google ScholarCross Ref
- D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566--591, 2017.Google ScholarCross Ref
- E. Djikstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269--271, 1959.Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of WEA, pages 319--333, 2008.Google ScholarCross Ref
- R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388--404, 2012.Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of SODA, pages 156--165, 2005.Google Scholar
- M. S. Hassan, W. G. Aref, and A. M. Aly. Graph indexing for shortest-path finding over dynamic sub-graphs. In Proceedings of SIGMOD, pages 1183--1197, 2016.Google ScholarDigital Library
- R. Jin, N. Ruan, Y. Xiang, and V. Lee. A highway-centric labeling approach for answering distance queries on large sparse graphs. In Proceedings of SIGMOD, pages 445--456, 2012.Google ScholarDigital Library
- S. Jung and S. Pramanik. An efficient path computation model for hierarchically structured topographical road maps. IEEE TKDE, 14(5):1029--1046, 2002.Google Scholar
- S. C. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. D. Zaroliagis. Analysis and experimental evaluation of time-dependent distance oracles. In Proceedings of ALENEX, pages 147--158, 2015.Google ScholarCross Ref
- S. C. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. D. Zaroliagis. Engineering oracles for time-dependent road networks. In Proceedings of ALENEX, pages 1--14, 2016.Google ScholarCross Ref
- S. C. Kontogiannis, D. Wagner, and C. D. Zaroliagis. Hierarchical oracles for time-dependent networks. CoRR, abs/1502.05222, 2015.Google Scholar
- H. Li, Y. Ge, R. Hong, and H. Zhu. Point-of-interest recommendations: Learning potential check-ins from friends. In Proceedings of SIGKDD, pages 975--984, 2016.Google ScholarDigital Library
- Y. Li, L. H. U, M. L. Yiu, and N. M. Kou. An experimental study on hub labeling based shortest path algorithms. PVLDB, 11(4):445--457, 2017.Google Scholar
- B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou. Efficient (α, β)-core computation: an index-based approach. In Proceedings of WWW, pages 1130--1141, 2019.Google Scholar
- Y. Liu, T. Pham, G. Cong, and Q. Yuan. An experimental evaluation of point-of-interest recommendation in location-based social networks. PVLDB, 10(10):1010--1021, 2017.Google ScholarDigital Library
- D. Ouyang, L. Qin, L. Chang, X. Lin, Y. Zhang, and Q. Zhu. When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In Proceedings of SIGMOD, pages 709--724, 2018.Google ScholarDigital Library
- D. Ouyang, L. Yuan, F. Zhang, L. Qin, and X. Lin. Towards efficient path skyline computation in bicriteria networks. In Proceedings of International Conference on Database Systems for Advanced Applications, pages 239--254, 2018.Google ScholarDigital Library
- I. Pohl. Bidirectional and heuristic search in path problems. Technical report, 1969.Google Scholar
- P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proceedings of ESA, pages 568--579, 2005.Google ScholarDigital Library
- A. Sharma, V. Ahsani, and S. R. and. Evaluation of opportunities and challenges of using inrix data for real-time performance monitoring and historical trend assessment (2017). Reports and White Papers. 24. Available at https://lib.dr.iastate.edu/ccee_reports/24.Google Scholar
- Y. Wang, G. Li, and N. Tang. Querying shortest paths on time dependent road networks. PVLDB, 12(11):1249--1261, 2019.Google ScholarDigital Library
- L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou. Shortest path and distance queries on road networks: An experimental evaluation. PVLDB, 5(5):406--417, 2012.Google ScholarDigital Library
- X. Wu, L. Yuan, X. Lin, S. Yang, and W. Zhang. Towards efficient k-tripeak decomposition on large graphs. In Proceedings of International Conference on Database Systems for Advanced Applications, pages 604--621, 2019.Google ScholarDigital Library
- G. Xu and Y. Xu. GPS: theory, algorithms and applications. Springer, 2016.Google ScholarCross Ref
- L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. Diversified top-k clique search. VLDB Journal., 25(2):171--196, 2016.Google ScholarDigital Library
- L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. I/O efficient ECC graph decomposition via graph reduction. PVLDB, 9(7):516--527, 2016.Google ScholarDigital Library
- L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. Effective and efficient dynamic graph coloring. PVLDB, 11(3):338--351, 2017.Google ScholarDigital Library
- L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. I/O efficient ECC graph decomposition via graph reduction. VLDB Journal., 26(2):275--300, 2017.Google ScholarDigital Library
- L. Yuan, L. Qin, W. Zhang, L. Chang, and J. Yang. Index-based densest clique percolation community search in networks. IEEE TKDE, 30(5):922--935, 2018.Google Scholar
- D. Zhang, D. Yang, Y. Wang, K.-L. Tan, J. Cao, and H. T. Shen. Distributed shortest path query processing on dynamic road networks. The VLDB Journal, 26(3):399--419, 2017.Google ScholarDigital Library
- J. Zhang, C. Kamga, H. Gong, and L. Gruenwald. U2 sod-db: a database system to manage large-scale ubiquitous urban sensing origin-destination data. In Proceedings of SIGKDD Workshop on Urban Computing, 2012, pages 163--171, 2012.Google Scholar
- Y. Zheng, L. Capra, O. Wolfson, and H. Yang. Urban computing: Concepts, methodologies, and applications. ACM TIST, 5(3):38:1--38:55, 2014.Google ScholarDigital Library
- Y. Zheng, Y. Liu, J. Yuan, and X. Xie. Urban computing with taxicabs. In Proceedings of the 13th ACM International Conference on Ubiquitous Computing, 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 Proceedings of SIGMOD, pages 857--868, 2013.Google ScholarDigital Library
Index Terms
- Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees
Index terms have been assigned to the content through auto-classification.
Recommendations
Distributed Processing of k Shortest Path Queries over Dynamic Road Networks
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataThe 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 ...
Disk-based shortest path discovery using distance index over large dynamic graphs
The persistent alternation of the internet world is changing networks rapidly. Shortest path discovery, especially over dynamic networks such as web page links, telephone or route networks, and ontologies, has received intense attention because of its ...
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Comments