{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T11:28:32Z","timestamp":1779103712934,"version":"3.51.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2016,12,8]],"date-time":"2016-12-08T00:00:00Z","timestamp":1481155200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Microsoft Research Silicon Valley"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,12,20]]},"abstract":"<jats:p>Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up online queries. In practice, the best algorithms have storage overhead comparable to the graph size and answer queries very fast, while examining a small fraction of the graph. In this article, we complement the experimental evidence with the first rigorous proofs of efficiency for some of the speedup techniques developed over the past decade or variations thereof. We define highway dimension, which strengthens the notion of doubling dimension. Under the assumption that the highway dimension is low (at most polylogarithmic in the graph size), we show that, for some algorithms or their variants, preprocessing can be implemented in polynomial time, the resulting auxiliary data increases the storage requirements by a polylogarithmic factor, and queries run in polylogarithmic time. This gives a unified explanation for the performance of several seemingly different approaches. Our best bounds are based on a result that may be of independent interest: we show that unique shortest paths induce set systems of low VC-dimension, which makes them combinatorially simple.<\/jats:p>","DOI":"10.1145\/2985473","type":"journal-article","created":{"date-parts":[[2016,12,8]],"date-time":"2016-12-08T16:14:38Z","timestamp":1481213678000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Highway Dimension and Provably Efficient Shortest Path Algorithms"],"prefix":"10.1145","volume":"63","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Delling","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Fiat","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,8]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"Werneck","author":"Abraham Ittai","year":"2011","unstructured":"Ittai Abraham , Daniel Delling , Amos Fiat , Andrew V. Goldberg , and Renato F . Werneck . 2011 a. VC-dimension and shortest path algorithms. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP\u201911), Lecture Notes in Computer Science , Vol. 6755 . Springer , 690--699. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2011a. VC-dimension and shortest path algorithms. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP\u201911), Lecture Notes in Computer Science, Vol. 6755. Springer, 690--699."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424365"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science","volume-title":"Werneck","author":"Abraham Ittai","year":"2011","unstructured":"Ittai Abraham , Daniel Delling , Andrew V. Goldberg , and Renato F . Werneck . 2011 b. A hub-based labeling algorithm for shortest paths on road networks. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA\u201911), Lecture Notes in Computer Science , Vol. 6630 . Springer , 230--241. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011b. A hub-based labeling algorithm for shortest paths on road networks. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA\u201911), Lecture Notes in Computer Science, Vol. 6630. Springer, 230--241."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2444016.2444019"},{"key":"e_1_2_1_6_1","volume-title":"Werneck","author":"Abraham Ittai","year":"2010","unstructured":"Ittai Abraham , Amos Fiat , Andrew V. Goldberg , and Renato F . Werneck . 2010 . Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA\u201910). 782--793. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA\u201910). 782--793."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_7"},{"key":"e_1_2_1_9_1","volume-title":"DIMACS Book","volume":"74","author":"Bast Holger","year":"2009","unstructured":"Holger Bast , Stefan Funke , and Domagoj Matijevic . 2009 . Ultrafast shortest-path queries via transit nodes. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.) . DIMACS Book , Vol. 74 . American Mathematical Society, 175--192. Holger Bast, Stefan Funke, and Domagoj Matijevic. 2009. Ultrafast shortest-path queries via transit nodes. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74. American Mathematical Society, 175--192."},{"key":"e_1_2_1_10_1","volume-title":"Fast routing in road networks with transit nodes. Science 316, 5824","author":"Bast Holger","year":"2007","unstructured":"Holger Bast , Stefan Funke , Peter Sanders , and Dominik Schultes . 2007. Fast routing in road networks with transit nodes. Science 316, 5824 ( 2007 ), 566. Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. 2007. Fast routing in road networks with transit nodes. Science 316, 5824 (2007), 566."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1537599"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20382"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880586.1880592"},{"key":"e_1_2_1_16_1","volume-title":"Four surveyors of Caesar: Mapping the world! International Federation of Surveyers 1","author":"Brock John F.","year":"2012","unstructured":"John F. Brock . 2012. Four surveyors of Caesar: Mapping the world! International Federation of Surveyers 1 ( 2012 ), 1--14. John F. Brock. 2012. Four surveyors of Caesar: Mapping the world! International Federation of Surveyers 1 (2012), 1--14."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21961"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645929.672705"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.02.007"},{"key":"e_1_2_1_23_1","series-title":"Lecture Notes in Computer Science","volume-title":"Werneck","author":"Delling Daniel","year":"2011","unstructured":"Daniel Delling , Andrew V. Goldberg , Thomas Pajor , and Renato F . Werneck . 2011 a. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA\u201911), Lecture Notes in Computer Science , Vol. 6630 . Springer , 376--387. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2011a. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA\u201911), Lecture Notes in Computer Science, Vol. 6630. Springer, 376--387."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.108"},{"key":"e_1_2_1_25_1","volume-title":"Werneck","author":"Delling Daniel","year":"2012","unstructured":"Daniel Delling , Moritz Kobitzsch , Dennis Luxen , and Renato F . Werneck . 2012 . Robust mobile route planning with limited connectivity. In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX\u201912). SIAM , 150--159. Daniel Delling, Moritz Kobitzsch, Dennis Luxen, and Renato F. Werneck. 2012. Robust mobile route planning with limited connectivity. In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX\u201912). SIAM, 150--159."},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Werneck","author":"Delling Daniel","year":"2013","unstructured":"Daniel Delling and Renato F . Werneck . 2013 . Faster customization of road networks. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA\u201913), Lecture Notes in Computer Science , Vol. 7933 . Springer , 30--42. Daniel Delling and Renato F. Werneck. 2013. Faster customization of road networks. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA\u201913), Lecture Notes in Computer Science, Vol. 7933. Springer, 30--42."},{"key":"e_1_2_1_27_1","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge. DIMACS Book","volume":"74","author":"Demetrescu Camil","unstructured":"Camil Demetrescu , Andrew V. Goldberg , and David S . Johnson (Eds.). 2009 . The Shortest Path Problem: Ninth DIMACS Implementation Challenge. DIMACS Book , Vol. 74 . American Mathematical Society. Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). 2009. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. DIMACS Book, Vol. 74. American Mathematical Society."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.1.161"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790265.2790279"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463455"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/070698774"},{"key":"e_1_2_1_37_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson . 2005 . Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA\u201905). SIAM , 156--165. Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA\u201905). SIAM, 156--165."},{"key":"e_1_2_1_38_1","volume-title":"Werneck","author":"Goldberg Andrew V.","year":"2009","unstructured":"Andrew V. Goldberg , Haim Kaplan , and Renato F . Werneck . 2009 . Reach for A*: Shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74 . American Mathematical Society , 93--139. Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck. 2009. Reach for A*: Shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74. American Mathematical Society, 93--139."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 534--543","author":"Gupta A.","unstructured":"A. Gupta , R. Krauthgamer , and J. R. Lee . 2003. Bounded geometries, fractals, and low-distortion embeddings . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 534--543 . A. Gupta, R. Krauthgamer, and J. R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 534--543."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX\u201904)","author":"Gutman Ronald J.","year":"2004","unstructured":"Ronald J. Gutman . 2004 . Reach-based routing: A new approach to shortest path algorithms optimized for road networks . In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX\u201904) . SIAM, 100--111. Ronald J. Gutman. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX\u201904). SIAM, 100--111."},{"key":"e_1_2_1_42_1","volume-title":"DIMACS Book","volume":"74","author":"Hilger Moritz","year":"2009","unstructured":"Moritz Hilger , Ekkehard K\u00f6hler , Rolf H. M\u00f6hring , and Heiko Schilling . 2009 . Fast point-to-point shortest path computations with arc-flags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.) . DIMACS Book , Vol. 74 . American Mathematical Society, 41--72. Moritz Hilger, Ekkehard K\u00f6hler, Rolf H. M\u00f6hring, and Heiko Schilling. 2009. Fast point-to-point shortest path computations with arc-flags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74. American Mathematical Society, 41--72."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412239"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129077"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a005"},{"key":"e_1_2_1_49_1","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V","author":"Lauther Ulrich","unstructured":"Ulrich Lauther . 2009. An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags . In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V . Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol . 74. American Mathematical Society , 19--40. Ulrich Lauther. 2009. An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74. American Mathematical Society, 19--40."},{"key":"e_1_2_1_50_1","first-page":"60","article-title":"The small world problem","volume":"1","author":"Milgram Stanley","year":"1967","unstructured":"Stanley Milgram . 1967 . The small world problem . Psychology Today 1 , 1 (1967), 60 -- 67 . Stanley Milgram. 1967. The small world problem. Psychology Today 1, 1 (1967), 60--67.","journal-title":"Psychology Today"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442942.2442949"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3%26lt;%26gt;1.0.CO;2-Y"},{"key":"e_1_2_1_53_1","volume-title":"Machine Intelligence.","author":"Pohl Ira","unstructured":"Ira Pohl . 1971. Bi-directional search . In Machine Intelligence. Vol. 6 . Edinburgh University Press , Edinburgh , 124--140. Ira Pohl. 1971. Bi-directional search. In Machine Intelligence. Vol. 6. Edinburgh University Press, Edinburgh, 124--140."},{"key":"e_1_2_1_54_1","unstructured":"PTV AG - Planung Transport Verkehr. 1979. http:\/\/www.ptv.de. (1979).  PTV AG - Planung Transport Verkehr. 1979. http:\/\/www.ptv.de. (1979)."},{"key":"e_1_2_1_55_1","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V","author":"Sanders Peter","unstructured":"Peter Sanders and Dominik Schultes . 2009. Robust , almost constant time shortest-path queries in road networks . In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V . Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol . 74. American Mathematical Society , 193--218. Peter Sanders and Dominik Schultes. 2009. Robust, almost constant time shortest-path queries in road networks. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). DIMACS Book, Vol. 74. American Mathematical Society, 193--218."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2133803.2330080"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00053-Y"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989368"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Robert Tarjan. 1983. Data Structures and Network Algorithms. SIAM.   Robert Tarjan. 1983. Data Structures and Network Algorithms. SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2985473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2985473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:32Z","timestamp":1750217972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2985473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,8]]},"references-count":61,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,12,20]]}},"alternative-id":["10.1145\/2985473"],"URL":"https:\/\/doi.org\/10.1145\/2985473","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,8]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}