{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:36:03Z","timestamp":1791912963791,"version":"4.3.4"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>\n            Shortest path computation is a building block of various network applications. Since real-life networks evolve as time passes, the\n            <jats:italic>Dynamic Shortest Path (DSP)<\/jats:italic>\n            problem has drawn lots of attention in recent years. However, as\n            <jats:italic>DSP<\/jats:italic>\n            has many factors related to network topology, update patterns, and query characteristics, existing works only test their algorithms on limited situations without sufficient comparisons with other approaches. Thus, it is still hard to choose the most suitable method in practice. To this end, we first identify the\n            <jats:italic>determinant dimensions and constraint dimensions<\/jats:italic>\n            of the\n            <jats:italic>DSP<\/jats:italic>\n            problem and create a complete problem space to cover all possible situations. Then we evaluate the state-of-the-art\n            <jats:italic>DSP<\/jats:italic>\n            methods under the same implementation standard and test them systematically under a set of synthetic dynamic networks. Furthermore, we propose the concept of\n            <jats:italic>dynamic degree<\/jats:italic>\n            to classify the dynamic environments and use\n            <jats:italic>throughput<\/jats:italic>\n            to evaluate their performance. These results can serve as a guideline to find the best solution for each situation during system implementation and also identify research opportunities. Finally, we validate our findings on real-life dynamic networks.\n          <\/jats:p>","DOI":"10.14778\/3476249.3476267","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2127-2140","source":"Crossref","is-referenced-by-count":37,"title":["An experimental evaluation and guideline for path finding in weighted dynamic network"],"prefix":"10.14778","volume":"14","author":[{"given":"Mengxuan","family":"Zhang","sequence":"first","affiliation":[{"name":"The University of Queensland, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[{"name":"The University of Queensland, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_2_1_4_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_2_1_5_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 , 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, 19--80."},{"key":"e_1_2_1_6_1","volume-title":"9th DIMACS Implementation Challenge---Shortest Path.","author":"Bast Holger","unstructured":"Holger Bast , Stefan Funke , and Domagoj Matijevi\u0107 . 2006. Transit: ultrafast shortest-path queries with linear-time preprocessing . In 9th DIMACS Implementation Challenge---Shortest Path. Holger Bast, Stefan Funke, and Domagoj Matijevi\u0107. 2006. Transit: ultrafast shortest-path queries with linear-time preprocessing. In 9th DIMACS Implementation Challenge---Shortest Path."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791220.2791230"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0274-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299901"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133063"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_41"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070455"},{"key":"e_1_2_1_19_1","volume-title":"Workshop on Algorithm Engineering and Experiments (ALENEX) 4","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 . Workshop on Algorithm Engineering and Experiments (ALENEX) 4 (2004), 100--111. Ronald J Gutman. 2004. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. Workshop on Algorithm Engineering and Experiments (ALENEX) 4 (2004), 100--111."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 7th Python in Science Conference, Ga\u00ebl Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 -- 15","author":"Hagberg Aric A.","unstructured":"Aric A. Hagberg , Daniel A. Schult , and Pieter J. Swart . 2008. Exploring Network Structure, Dynamics, and Function using NetworkX . In Proceedings of the 7th Python in Science Conference, Ga\u00ebl Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 -- 15 . Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In Proceedings of the 7th Python in Science Conference, Ga\u00ebl Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 -- 15."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372722"},{"key":"e_1_2_1_27_1","volume-title":"IEEE International Conference on Data Engineering. IEEE, 871--882","author":"Li Jianxin","year":"2017","unstructured":"Jianxin Li , Xinjue Wang , Ke Deng , Xiaochun Yang , Timos Sellis , and Jeffrey Xu Yu . 2017 . Most influential community International Symposium on Experimental Algorithmsrch over large social networks . In IEEE International Conference on Data Engineering. IEEE, 871--882 . Jianxin Li, Xinjue Wang, Ke Deng, Xiaochun Yang, Timos Sellis, and Jeffrey Xu Yu. 2017. Most influential community International Symposium on Experimental Algorithmsrch over large social networks. In IEEE International Conference on Data Engineering. IEEE, 871--882."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00085"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2981062"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00107"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0499-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_35_1","volume-title":"Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling. In IEEE International Conference on Data Engineering. IEEE, 1763--1774","author":"Liu Ziyi","year":"2021","unstructured":"Ziyi Liu , Lei Li , Mengxuan Zhang , Wen Hua , Pingfu Chao , and Xiaofang Zhou . 2021 . Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling. In IEEE International Conference on Data Engineering. IEEE, 1763--1774 . Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, Pingfu Chao, and Xiaofang Zhou. 2021. Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling. In IEEE International Conference on Data Engineering. IEEE, 1763--1774."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40235-7_21"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216585"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397248"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00585-6"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732225"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0421-1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_71"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097093"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.889971"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213872"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1103378"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_2_1_53_1","volume-title":"Collective dynamics of `small-world'networks. nature 393, 6684","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz . 1998. Collective dynamics of `small-world'networks. nature 393, 6684 ( 1998 ), 440--442. Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of `small-world'networks. nature 393, 6684 (1998), 440--442."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389718"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389735"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0457-6"},{"key":"e_1_2_1_61_1","volume-title":"International Conference on Database Systems for Advanced Applications. In International Conference on Database Systems for Advanced Applications. Springer, 255--271","author":"Zhang Mengxuan","year":"2020","unstructured":"Mengxuan Zhang , Lei Li , Pingfu Chao , Wen Hua , and Xiaofang Zhou . 2020 . International Conference on Database Systems for Advanced Applications. In International Conference on Database Systems for Advanced Applications. Springer, 255--271 . Mengxuan Zhang, Lei Li, Pingfu Chao, Wen Hua, and Xiaofang Zhou. 2020. International Conference on Database Systems for Advanced Applications. In International Conference on Database Systems for Advanced Applications. Springer, 255--271."},{"key":"e_1_2_1_62_1","volume-title":"Dynamic Hub Labeling for Road Networks. In IEEE International Conference on Data Engineering. IEEE, 336--347","author":"Zhang Mengxuan","year":"2021","unstructured":"Mengxuan Zhang , Lei Li , Wen Hua , Rui Mao , Pingfu Chao , and Xiaofang Zhou . 2021 . Dynamic Hub Labeling for Road Networks. In IEEE International Conference on Data Engineering. IEEE, 336--347 . Mengxuan Zhang, Lei Li, Wen Hua, Rui Mao, Pingfu Chao, and Xiaofang Zhou. 2021. Dynamic Hub Labeling for Road Networks. In IEEE International Conference on Data Engineering. IEEE, 336--347."},{"key":"e_1_2_1_63_1","volume-title":"Efficient Batch Processing of Shortest Path Queries in Road Networks. In IEEE International Conference on Mobile Data Management. IEEE, 100--105","author":"Zhang Mengxuan","year":"2019","unstructured":"Mengxuan Zhang , Lei Li , Wen Hua , and Xiaofang Zhou . 2019 . Efficient Batch Processing of Shortest Path Queries in Road Networks. In IEEE International Conference on Mobile Data Management. IEEE, 100--105 . Mengxuan Zhang, Lei Li, Wen Hua, and Xiaofang Zhou. 2019. Efficient Batch Processing of Shortest Path Queries in Road Networks. In IEEE International Conference on Mobile Data Management. IEEE, 100--105."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3010005"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498297"},{"key":"e_1_2_1_67_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\/3476249.3476267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:59:02Z","timestamp":1672221542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":67,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476267"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476267","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}