{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:53:46Z","timestamp":1784840026188,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>\n            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,\n            <jats:italic>shortcut index<\/jats:italic>\n            , 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\n            <jats:italic>shortcut index.<\/jats:italic>\n            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\n            <jats:italic>shortcut index<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3377369.3377371","type":"journal-article","created":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T18:58:53Z","timestamp":1582138733000},"page":"602-615","source":"Crossref","is-referenced-by-count":72,"title":["Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees"],"prefix":"10.14778","volume":"13","author":[{"given":"Dian","family":"Ouyang","sequence":"first","affiliation":[{"name":"Nanjing University of Science and Technology, Nanjing, China and The University of Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[{"name":"Nanjing University of Science and Technology, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,19]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"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.  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."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/www.tomtom.com\/automotive\/products-services\/connected-services\/tomtom-traffic\/.  https:\/\/www.tomtom.com\/automotive\/products-services\/connected-services\/tomtom-traffic\/."},{"key":"e_1_2_1_3_1","unstructured":"Road traffic injuries. https:\/\/www.who.int\/news-room\/fact-sheets\/detail\/road-traffic-injuries.  Road traffic injuries. https:\/\/www.who.int\/news-room\/fact-sheets\/detail\/road-traffic-injuries."},{"key":"e_1_2_1_4_1","unstructured":"Statistical Report on Internet Development in China China Internet Network Information Center. Available at https:\/\/cnnic.com.cn\/IDR\/ReportDownloads\/201807\/P020180711391069195909.pdf.  Statistical Report on Internet Development in China China Internet Network Information Center. Available at https:\/\/cnnic.com.cn\/IDR\/ReportDownloads\/201807\/P020180711391069195909.pdf."},{"key":"e_1_2_1_5_1","unstructured":"Taxi and Ridehailing Usage in New York City. https:\/\/toddwschneider.com\/dashboards\/nyc-taxi-ridehailing-uber-lyft-data\/.  Taxi and Ridehailing Usage in New York City. https:\/\/toddwschneider.com\/dashboards\/nyc-taxi-ridehailing-uber-lyft-data\/."},{"key":"e_1_2_1_6_1","unstructured":"TomTom Real Time Traffic Information TomTom White Paper. Available at https:\/\/www.tomtom.com\/lib\/img\/REAL_TIME_TRAFFIC_WHITEPAPER.pdf.  TomTom Real Time Traffic Information TomTom White Paper. Available at https:\/\/www.tomtom.com\/lib\/img\/REAL_TIME_TRAFFIC_WHITEPAPER.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20662-7_20"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"e_1_2_1_12_1","first-page":"175","volume-title":"Proceedings of DIMACS, The Shortest Path Problem Workshop","author":"Bast H.","year":"2006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972894.10"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_15"},{"key":"e_1_2_1_15_1","volume-title":"Apache flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4)","author":"Carbone P.","year":"2015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0579"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_21_1","first-page":"156","volume-title":"Proceedings of SODA","author":"Goldberg A. V.","year":"2005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882933"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"issue":"5","key":"e_1_2_1_24_1","first-page":"1029","article-title":"An efficient path computation model for hierarchically structured topographical road maps","volume":"14","author":"Jung S.","year":"2002","journal-title":"IEEE TKDE"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973754.13"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.1"},{"key":"e_1_2_1_27_1","volume-title":"Hierarchical oracles for time-dependent networks. CoRR, abs\/1502.05222","author":"Kontogiannis S. C.","year":"2015"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939767"},{"issue":"4","key":"e_1_2_1_29_1","first-page":"445","article-title":"An experimental study on hub labeling based shortest path algorithms","volume":"11","author":"Li Y.","year":"2017","journal-title":"PVLDB"},{"key":"e_1_2_1_30_1","first-page":"1130","volume-title":"Proceedings of WWW","author":"Liu B.","year":"2019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115407"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91452-7_16"},{"key":"e_1_2_1_34_1","volume-title":"Technical report","author":"Pohl I.","year":"1969"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_36_1","volume-title":"Evaluation of opportunities and challenges of using inrix data for real-time performance monitoring and historical trend assessment","author":"Sharma A.","year":"2017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-18576-3_36"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-50367-6_10"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904484"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157802"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0451-4"},{"issue":"5","key":"e_1_2_1_45_1","first-page":"922","article-title":"Index-based densest clique percolation community search in networks","volume":"30","author":"Yuan L.","year":"2018","journal-title":"IEEE TKDE"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0457-6"},{"key":"e_1_2_1_47_1","first-page":"163","volume-title":"Proceedings of SIGKDD Workshop on Urban Computing, 2012","author":"Zhang J.","year":"2012"},{"issue":"3","key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2629592","article-title":"Urban computing: Concepts, methodologies, and applications","volume":"5","author":"Zheng Y.","year":"2014","journal-title":"ACM TIST"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2030112.2030126"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465277"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3377369.3377371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:31:31Z","timestamp":1672219891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3377369.3377371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":50,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.14778\/3377369.3377371"],"URL":"https:\/\/doi.org\/10.14778\/3377369.3377371","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}