{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T08:29:26Z","timestamp":1778660966925,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["IIS-1527984"],"award-info":[{"award-number":["IIS-1527984"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,11,2]]},"DOI":"10.1145\/3474717.3484267","type":"proceedings-article","created":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T22:59:49Z","timestamp":1636066789000},"page":"616-625","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Tiering in Contraction and Edge Hierarchies for Stochastic Route Planning"],"prefix":"10.1145","author":[{"given":"Payas","family":"Rajan","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering University of California Riverside, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chinya V.","family":"Ravishankar","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering University of California Riverside, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996964"},{"key":"e_1_3_2_1_2_1","volume-title":"Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks. In 2018 19th IEEE International Conference on Mobile Data Management (MDM). 40--45","author":"Andonov Georgi","year":"2018","unstructured":"Georgi Andonov and Bin Yang . 2018 . Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks. In 2018 19th IEEE International Conference on Mobile Data Management (MDM). 40--45 . Georgi Andonov and Bin Yang. 2018. Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks. In 2018 19th IEEE International Conference on Mobile Data Management (MDM). 40--45."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820836"},{"key":"e_1_3_2_1_4_1","volume-title":"Algorithm Engineering","author":"Bast Hannah","unstructured":"Hannah Bast , Daniel Delling , Andrew Goldberg , Matthias M\u00fcller-Hannemann , Thomas Pajor , Peter Sanders , Dorothea Wagner , and Renato F Werneck . 2016. Route Planning in Transportation Networks . In Algorithm Engineering . Springer , Cham , 19--80. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias M\u00fcller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route Planning in Transportation Networks. In Algorithm Engineering. Springer, Cham, 19--80."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791220.2791230"},{"key":"e_1_3_2_1_6_1","volume-title":"Experimental Algorithms","author":"Batz Gernot Veit","unstructured":"Gernot Veit Batz , Robert Geisberger , Sabine Neubauer , and Peter Sanders . 2010. Time-Dependent Contraction Hierarchies and Approximation . In Experimental Algorithms . Springer Berlin Heidelberg , 166--177. Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, and Peter Sanders. 2010. Time-Dependent Contraction Hierarchies and Approximation. In Experimental Algorithms. Springer Berlin Heidelberg, 166--177."},{"key":"e_1_3_2_1_7_1","volume-title":"Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algorithmics 18 (Dec","author":"Batz Gernot Veit","year":"2013","unstructured":"Gernot Veit Batz , Robert Geisberger , Peter Sanders , and Christian Vetter . 2013. Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algorithmics 18 (Dec . 2013 ), 1.1-1.43. Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. 2013. Minimum time-dependent travel times with contraction hierarchies. J. Exp. Algorithmics 18 (Dec. 2013), 1.1-1.43."},{"key":"e_1_3_2_1_8_1","volume-title":"Search-space size in contraction hierarchies. Theor. Comput. Sci. 645 (Sept","author":"Bauer Reinhard","year":"2016","unstructured":"Reinhard Bauer , Tobias Columbus , Ignaz Rutter , and Dorothea Wagner . 2016. Search-space size in contraction hierarchies. Theor. Comput. Sci. 645 (Sept . 2016 ), 112--127. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. 2016. Search-space size in contraction hierarchies. Theor. Comput. Sci. 645 (Sept. 2016), 112--127."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0003498-3"},{"key":"e_1_3_2_1_10_1","unstructured":"Johannes Blum and Sabine Storandt. 2020. Lower bounds and approximation algorithms for search space sizes in contraction hierarchies. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik.  Johannes Blum and Sabine Storandt. 2020. Lower bounds and approximation algorithms for search space sizes in contraction hierarchies. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_11_1","first-page":"4","article-title":"How to Approximate a Histogram by a Normal","volume":"47","author":"Brown Lawrence D","year":"1993","unstructured":"Lawrence D Brown and J T Gene Hwang . 1993 . How to Approximate a Histogram by a Normal Density. Am. Stat. 47 , 4 (Nov. 1993), 251--255. Lawrence D Brown and J T Gene Hwang. 1993. How to Approximate a Histogram by a Normal Density. Am. Stat. 47, 4 (Nov. 1993), 251--255.","journal-title":"Density. Am. Stat."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2014.6957826"},{"key":"e_1_3_2_1_13_1","unstructured":"Lily Chai and Morgan Herlocker. 2019. Generating accurate speed estimations using aggregated telemetry data.  Lily Chai and Morgan Herlocker. 2019. Generating accurate speed estimations using aggregated telemetry data."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/atr.5670390104"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/15472450.2013.806851"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021926"},{"key":"e_1_3_2_1_17_1","first-page":"1","article-title":"On the Liapunoff limit of error in the theory of probability","volume":"28","author":"Esseen Carl-Gustav","year":"1942","unstructured":"Carl-Gustav Esseen . 1942 . On the Liapunoff limit of error in the theory of probability . Ark. Mat. Astron. Fys. A28 , 9 (1942), 1 -- 19 . Carl-Gustav Esseen. 1942. On the Liapunoff limit of error in the theory of probability. Ark. Mat. Astron. Fys. A28, 9 (1942), 1--19.","journal-title":"Ark. Mat. Astron. Fys."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.4.583"},{"key":"e_1_3_2_1_19_1","volume-title":"Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Experimental Algorithms","author":"Geisberger Robert","year":"2008","unstructured":"Robert Geisberger , Peter Sanders , Dominik Schultes , and Daniel Delling . 2008 . Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Experimental Algorithms . Springer, Berlin , Heidelberg , 319--333. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Experimental Algorithms. Springer, Berlin, Heidelberg, 319--333."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1909.136.210"},{"key":"e_1_3_2_1_22_1","volume-title":"More Hierarchy in Route Planning Using Edge Hierarchies. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)","author":"Hespe Demian","year":"2019","unstructured":"Demian Hespe and Peter Sanders . 2019 . More Hierarchy in Route Planning Using Edge Hierarchies. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) (OpenAccess Series in Informatics (OASIcs)). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern\/Saarbruecken, Germany, Dagstuhl, Germany, 10:1--10:14. Demian Hespe and Peter Sanders. 2019. More Hierarchy in Route Planning Using Edge Hierarchies. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) (OpenAccess Series in Informatics (OASIcs)). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern\/Saarbruecken, Germany, Dagstuhl, Germany, 10:1--10:14."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0494-9"},{"key":"e_1_3_2_1_24_1","volume-title":"UniTE - The Best of Both Worlds: Unifying Function-Fitting and Aggregation-Based Approaches to Travel Time and Travel Speed Estimation. (April","author":"Jepsen Tobias Skovgaard","year":"2021","unstructured":"Tobias Skovgaard Jepsen , Christian S Jensen , and Thomas Dyhre Nielsen . 2021. UniTE - The Best of Both Worlds: Unifying Function-Fitting and Aggregation-Based Approaches to Travel Time and Travel Speed Estimation. (April 2021 ). arXiv:2104.13321 [cs.LG] Tobias Skovgaard Jepsen, Christian S Jensen, and Thomas Dyhre Nielsen. 2021. UniTE - The Best of Both Worlds: Unifying Function-Fitting and Aggregation-Based Approaches to Travel Time and Travel Speed Estimation. (April 2021). arXiv:2104.13321 [cs.LG]"},{"key":"e_1_3_2_1_25_1","volume-title":"Pruning Techniques for the Stochastic on-time Arrival Problem - An Experimental Study. (July","author":"Kobitzsch Moritz","year":"2014","unstructured":"Moritz Kobitzsch , Samitha Samaranayake , and Dennis Schieferdecker . 2014. Pruning Techniques for the Stochastic on-time Arrival Problem - An Experimental Study. (July 2014 ). arXiv:1407.8295 [cs.DS] Moritz Kobitzsch, Samitha Samaranayake, and Dennis Schieferdecker. 2014. Pruning Techniques for the Stochastic on-time Arrival Problem - An Experimental Study. (July 2014). arXiv:1407.8295 [cs.DS]"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.95"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_3_2_1_28_1","volume-title":"Robotics: Science and Systems","volume":"8","author":"Lim Sejoon","year":"2013","unstructured":"Sejoon Lim , Christian Sommer , Evdokia Nikolova , and Daniela Rus . 2013 . Practical route planning under delay uncertainty: Stochastic shortest path queries . In Robotics: Science and Systems , Vol. 8 . books.google.com, 249--256. Sejoon Lim, Christian Sommer, Evdokia Nikolova, and Daniela Rus. 2013. Practical route planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems, Vol. 8. books.google.com, 249--256."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442942.2442949"},{"key":"e_1_3_2_1_31_1","volume-title":"Experimental Algorithms","author":"Niknami Mehrdad","unstructured":"Mehrdad Niknami and Samitha Samaranayake . 2016. Tractable Pathfinding for the Stochastic On-Time Arrival Problem . In Experimental Algorithms . Springer International Publishing , 231--245. Mehrdad Niknami and Samitha Samaranayake. 2016. Tractable Pathfinding for the Stochastic On-Time Arrival Problem. In Experimental Algorithms. Springer International Publishing, 231--245."},{"key":"e_1_3_2_1_32_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Nikolova Evdokia","unstructured":"Evdokia Nikolova . 2010. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer Berlin Heidelberg , 338--351. Evdokia Nikolova. 2010. Approximation Algorithms for Reliable Stochastic Combinatorial Optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer Berlin Heidelberg, 338--351."},{"key":"e_1_3_2_1_33_1","volume-title":"Optimal Route Planning under Uncertainty. ICAPS","author":"Nikolova Evdokia","year":"2006","unstructured":"Evdokia Nikolova , M Brand , and David R Karger . 2006. Optimal Route Planning under Uncertainty. ICAPS ( 2006 ). Evdokia Nikolova, M Brand, and David R Karger. 2006. Optimal Route Planning under Uncertainty. ICAPS (2006)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_50"},{"key":"e_1_3_2_1_35_1","volume-title":"Stochastic Shortest Paths and Risk Measures. (Aug","author":"Parmentier Axel","year":"2014","unstructured":"Axel Parmentier and Fr\u00e9d\u00e9ric Meunier . 2014. Stochastic Shortest Paths and Risk Measures. (Aug . 2014 ). arXiv:1408.0272 [cs.DS] Axel Parmentier and Fr\u00e9d\u00e9ric Meunier. 2014. Stochastic Shortest Paths and Risk Measures. (Aug. 2014). arXiv:1408.0272 [cs.DS]"},{"key":"e_1_3_2_1_36_1","volume-title":"Fast stochastic routing under time-varying uncertainty. VLDB J. (Oct","author":"Pedersen Simon Aagaard","year":"2019","unstructured":"Simon Aagaard Pedersen , Bin Yang , and Christian S Jensen . 2019. Fast stochastic routing under time-varying uncertainty. VLDB J. (Oct . 2019 ). Simon Aagaard Pedersen, Bin Yang, and Christian S Jensen. 2019. Fast stochastic routing under time-varying uncertainty. VLDB J. (Oct. 2019)."},{"key":"e_1_3_2_1_37_1","unstructured":"Mark Semenovich Pinsker. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day.  Mark Semenovich Pinsker. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day."},{"key":"e_1_3_2_1_38_1","volume-title":"2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 138--146","author":"Sabran Guillaume","year":"2013","unstructured":"Guillaume Sabran , Samitha Samaranayake , and Alexandre Bayen . 2013 . Precomputation techniques for the stochastic on-time arrival problem . In 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 138--146 . Guillaume Sabran, Samitha Samaranayake, and Alexandre Bayen. 2013. Precomputation techniques for the stochastic on-time arrival problem. In 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 138--146."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1064562410060062"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_3_2_1_44_1","volume-title":"Solving two-stage stochastic route-planning problem in milliseconds via end-to-end deep learning. Complex & Intelligent Systems 7","author":"Zheng Jie","year":"2021","unstructured":"Jie Zheng , Ling Wang , Shengyao Wang , Yile Liang , and Jize Pan . 2021. Solving two-stage stochastic route-planning problem in milliseconds via end-to-end deep learning. Complex & Intelligent Systems 7 , 3 June 2021 ), 1207--1222. Jie Zheng, Ling Wang, Shengyao Wang, Yile Liang, and Jize Pan. 2021. Solving two-stage stochastic route-planning problem in milliseconds via end-to-end deep learning. Complex & Intelligent Systems 7, 3 June 2021), 1207--1222."},{"key":"e_1_3_2_1_45_1","volume-title":"A Time-Dependent Shortest Path Algorithm for Real-Time Intelligent Vehicle\/Highway System. Transportation Research Record Journal of the Transportation Research Board 1408 (Jan","author":"Ziliaskopoulos Athanasios K","year":"1993","unstructured":"Athanasios K Ziliaskopoulos and Hani S Mahmassani . 1993. A Time-Dependent Shortest Path Algorithm for Real-Time Intelligent Vehicle\/Highway System. Transportation Research Record Journal of the Transportation Research Board 1408 (Jan . 1993 ), 94--100. Athanasios K Ziliaskopoulos and Hani S Mahmassani. 1993. A Time-Dependent Shortest Path Algorithm for Real-Time Intelligent Vehicle\/Highway System. Transportation Research Record Journal of the Transportation Research Board 1408 (Jan. 1993), 94--100."}],"event":{"name":"SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems","location":"Beijing China","acronym":"SIGSPATIAL '21","sponsor":["SIGSPATIAL ACM Special Interest Group on Spatial Information"]},"container-title":["Proceedings of the 29th International Conference on Advances in Geographic Information Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474717.3484267","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474717.3484267","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474717.3484267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:46Z","timestamp":1750191106000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474717.3484267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,2]]},"references-count":44,"alternative-id":["10.1145\/3474717.3484267","10.1145\/3474717"],"URL":"https:\/\/doi.org\/10.1145\/3474717.3484267","relation":{},"subject":[],"published":{"date-parts":[[2021,11,2]]},"assertion":[{"value":"2021-11-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}