{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:09:55Z","timestamp":1775912995342,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p>Shortest path query over a dynamic road network is a prominent problem for the optimization of real-time traffic systems. Existing solutions rely either on a centralized index system with tremendous pre-computation overhead, or on a distributed graph processing system such as Pregel that requires much synchronization effort. However, the performance of these systems degenerates with frequent route path updates caused by continuous traffic condition change.<\/jats:p>\n          <jats:p>In this paper, we build CANDS, a distributed stream processing platform for continuous optimal shortest path queries. It provides an asynchronous solution to answering a large quantity of shortest path queries. It is able to efficiently detect affected paths and adjust their paths in the face of traffic updates. Moreover, the affected paths can be quickly updated to the optimal solutions throughout the whole navigation process. Experimental results demonstrate that the performance for answering shortest path queries by CANDS is two orders of magnitude better than that of GPS, an open-source implementation of Pregel. In addition, CANDS provides fast response to traffic updates to guarantee the optimality of answering shortest path queries.<\/jats:p>","DOI":"10.14778\/2735471.2735475","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"137-148","source":"Crossref","is-referenced-by-count":20,"title":["CANDS"],"prefix":"10.14778","volume":"8","author":[{"given":"Dingyu","family":"Yang","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongxiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Cao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Le Mou\u00ebl","sequence":"additional","affiliation":[{"name":"University of Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Giraph. http:\/\/giraph.apache.org\/.  Apache Giraph. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Apache S4. http:\/\/incubator.apache.org\/s4\/.  Apache S4. http:\/\/incubator.apache.org\/s4\/."},{"key":"e_1_2_1_3_1","unstructured":"DIMACS. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml\/.  DIMACS. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml\/."},{"key":"e_1_2_1_4_1","unstructured":"GPS. http:\/\/infolab.stanford.edu\/gps\/.  GPS. http:\/\/infolab.stanford.edu\/gps\/."},{"key":"e_1_2_1_5_1","unstructured":"Infosphere Streams. http:\/\/www-01.ibm.com\/software\/data\/infosphere\/streams\/.  Infosphere Streams. http:\/\/www-01.ibm.com\/software\/data\/infosphere\/streams\/."},{"key":"e_1_2_1_6_1","unstructured":"Spark. http:\/\/spark.incubator.apache.org\/.  Spark. http:\/\/spark.incubator.apache.org\/."},{"key":"e_1_2_1_7_1","unstructured":"Twitter Storm. https:\/\/github.com\/nathanmarz\/storm.  Twitter Storm. https:\/\/github.com\/nathanmarz\/storm."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1137521"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807291"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-540-68552-4_24","volume-title":"Experimental Algorithms","author":"Geisberger R.","year":"2008","unstructured":"R. Geisberger , P. Sanders , D. Schultes , and D. Delling . Contraction hierarchies: Faster and simpler hierarchical routing in road networks . In Experimental Algorithms , pages 319 -- 333 . Springer , 2008 . R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms, pages 319--333. Springer, 2008."},{"key":"e_1_2_1_13_1","first-page":"156","volume-title":"SODA","author":"Goldberg A. V.","year":"2005","unstructured":"A. V. Goldberg and C. Harrelson . Computing the shortest path: A search meets graph theory . In SODA , pages 156 -- 165 , 2005 . A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In SODA, pages 156--165, 2005."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.13"},{"key":"e_1_2_1_15_1","first-page":"794","volume-title":"VLDB","author":"Gonzalez H.","year":"2007","unstructured":"H. Gonzalez , J. Han , X. Li , M. Myslinska , and J. P. Sondag . Adaptive fastest path computation on a road network: a traffic mining approach . In VLDB , pages 794 -- 805 . VLDB Endowment , 2007 . H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag. Adaptive fastest path computation on a road network: a traffic mining approach. In VLDB, pages 794--805. VLDB Endowment, 2007."},{"key":"e_1_2_1_16_1","first-page":"17","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . Powergraph: Distributed graph-parallel computation on natural graphs . In OSDI , pages 17 -- 30 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, pages 17--30, 2012."},{"key":"e_1_2_1_17_1","volume-title":"Emerging technologies for urban traffic management. Technical report","author":"Guerrero-Ib\u00e1\u00f1ez A.","year":"2012","unstructured":"A. Guerrero-Ib\u00e1\u00f1ez , C. Flores-Cort\u00e9s , P. Dami\u00e1n-Reyes , M. Andrade-Ar\u00e9chiga , and J. Pulido . Emerging technologies for urban traffic management. Technical report , 2012 . A. Guerrero-Ib\u00e1\u00f1ez, C. Flores-Cort\u00e9s, P. Dami\u00e1n-Reyes, M. Andrade-Ar\u00e9chiga, and J. Pulido. Emerging technologies for urban traffic management. Technical report, 2012."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038944"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767844"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921074"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424430"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2030112.2030126"},{"key":"e_1_2_1_28_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\/2735471.2735475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:23:04Z","timestamp":1672219384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735471.2735475"}},"subtitle":["continuous optimal navigation via distributed stream processing"],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2735471.2735475"],"URL":"https:\/\/doi.org\/10.14778\/2735471.2735475","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}