{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T12:17:38Z","timestamp":1790943458519,"version":"4.1.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n                    The current widespread use of location-based services and GPS technologies has revived interest in very fast and scalable shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid shortest path (e.g., dynamically restricting the type of roads or modes of travel which may be considered in a multimodal transportation network). We formalize this problem as a specific variant of formal language constrained shortest path problems, which we call the\n                    <jats:italic>Kleene Language Constrained Shortest Paths<\/jats:italic>\n                    problem. To efficiently support this type of dynamically constrained shortest path query for large-scale datasets, we extend the hierarchical graph indexing technique known as Contraction Hierarchies. Our experimental evaluation using the North American road network dataset (with over 50 million edges) shows an average query speed and search space improvement of over 3 orders of magnitude compared to the na\u00efve adaptation of the standard Dijkstra's algorithm to support this query type. We also show an improvement of over 2 orders of magnitude compared to the only previously-existing indexing technique which could solve this problem without additional preprocessing.\n                  <\/jats:p>","DOI":"10.14778\/1921071.1921074","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"69-80","source":"Crossref","is-referenced-by-count":56,"title":["Graph indexing of road networks for shortest path queries with label restrictions"],"prefix":"10.14778","volume":"4","author":[{"given":"Michael","family":"Rice","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vassilis J.","family":"Tsotras","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"27","volume-title":"AAIM","author":"Barrett C. L.","year":"2008"},{"key":"e_1_2_1_2_1","first-page":"126","volume-title":"ESA","author":"Barrett C. L.","year":"2002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_4_1","first-page":"303","volume-title":"WEA","author":"Bauer R.","year":"2008"},{"key":"e_1_2_1_5_1","first-page":"52","volume-title":"WEA","author":"Delling D.","year":"2007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra E. W.","year":"1959","journal-title":"Numerische Mathematik"},{"key":"e_1_2_1_7_1","volume-title":"Institut fur Theoretische Informatik Universitat Karlsruhe","author":"Geisberger R.","year":"2008"},{"key":"e_1_2_1_8_1","first-page":"319","volume-title":"WEA","author":"Geisberger R.","year":"2008"},{"key":"e_1_2_1_9_1","first-page":"156","volume-title":"SODA","author":"Goldberg A. V.","year":"2005"},{"key":"e_1_2_1_10_1","first-page":"26","volume-title":"ALENEX\/ANALCO","author":"Goldberg A. V.","year":"2005"},{"key":"e_1_2_1_11_1","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart P. E.","year":"1968","journal-title":"IEEE Transactions on System Science and Cybernetics"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412239"},{"key":"e_1_2_1_13_1","volume-title":"ALENEX","author":"Knopp S.","year":"2007"},{"key":"e_1_2_1_14_1","first-page":"804","volume-title":"ESA","author":"Sanders P.","year":"2006"},{"key":"e_1_2_1_15_1","first-page":"732","volume-title":"ESA","author":"Sanders P.","year":"2008"},{"key":"e_1_2_1_16_1","first-page":"66","volume-title":"WEA","author":"Schultes D.","year":"2007"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1921071.1921074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:51:13Z","timestamp":1672203073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1921071.1921074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.14778\/1921071.1921074"],"URL":"https:\/\/doi.org\/10.14778\/1921071.1921074","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}