{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T10:13:53Z","timestamp":1781086433727,"version":"3.54.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.<\/jats:p>","DOI":"10.14778\/3551793.3551863","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3199-3212","source":"Crossref","is-referenced-by-count":33,"title":["Diversified top-\n            <i>k<\/i>\n            route planning in road network"],"prefix":"10.14778","volume":"15","author":[{"given":"Zihan","family":"Luo","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mengxuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Iowa State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen","family":"Hua","sequence":"additional","affiliation":[{"name":"The University of Queensland, Brisbane, QLD, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yehong","family":"Xu","sequence":"additional","affiliation":[{"name":"The University of Queensland, Brisbane, QLD, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"9th DIMACS Implementation Challenge - Shortest Paths","unstructured":"[n.d.]. 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/users.diag.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"Alternative routes in road networks","volume":"18","author":"Abraham Ittai","year":"2013","unstructured":"Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. 2013. Alternative routes in road networks. Journal of Experimental Algorithmics (JEA) 18 (2013), 1--1.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00214-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.06.003"},{"key":"e_1_2_1_7_1","volume-title":"EDBT 2015-18th International Conference on Extending Database Technology, Proceedings.","author":"Chang Lijun","year":"2015","unstructured":"Lijun Chang, Xuemin Lin, Lu Qin, Jeffrey Xu Yu, and Jian Pei. 2015. Efficiently computing top-k shortest path join. In EDBT 2015-18th International Conference on Extending Database Technology, Proceedings."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644212"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820858"},{"key":"e_1_2_1_10_1","volume-title":"20th International Conference on Extending Database Technology: EDBT","author":"Chondrogiannis Theodoros","year":"2017","unstructured":"Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper, and Ulf Leser. 2017. Exact and approximate algorithms for finding k-shortest paths with limited overlap. In 20th International Conference on Extending Database Technology: EDBT 2017. 414--425."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274903"},{"key":"e_1_2_1_12_1","volume-title":"Finding k-shortest paths with limited overlap. The VLDB Journal","author":"Chondrogiannis Theodoros","year":"2020","unstructured":"Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper, Ulf Leser, and David B Blumenthal. 2020. Finding k-shortest paths with limited overlap. The VLDB Journal (2020), 1--25."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113313"},{"key":"e_1_2_1_14_1","volume-title":"A note on two problems in connexion with graphs. Numerische mathematik 1, 1","author":"Dijkstra Edsger W","year":"1959","unstructured":"Edsger W Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269--271."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_1_16_1","volume-title":"Hazardous materials transportation. Handbooks in operations research and management science 14","author":"Erkut Erhan","year":"2007","unstructured":"Erhan Erkut, Stevanus A Tjandra, and Vedat Verter. 2007. Hazardous materials transportation. Handbooks in operations research and management science 14 (2007), 539--621."},{"key":"e_1_2_1_17_1","volume-title":"Modeling of transport risk for hazardous materials. Operations research 46, 5","author":"Erkut Erhan","year":"1998","unstructured":"Erhan Erkut and Vedat Verter. 1998. Modeling of transport risk for hazardous materials. Operations research 46, 5 (1998), 625--642."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871504"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Andrew","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the Shortest Path: A Search Meets Graph Theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Vancouver, British Columbia) (SODA '05). Society for Industrial and Applied Mathematics, USA, 156--165."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/202"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3474717.3483955"},{"key":"e_1_2_1_22_1","volume-title":"Proc. ICSNC","author":"Henao-Mazo Wilton","year":"2012","unstructured":"Wilton Henao-Mazo and Angel Bravo-Santos. 2012. Finding diverse shortest paths for the routing task in wireless sensor networks. Proc. ICSNC (2012), 53--58."},{"key":"e_1_2_1_23_1","volume-title":"A protocol to convert spatial polyline data to network formats and applications to world urban road networks. Scientific data 3, 1","author":"Karduni Alireza","year":"2016","unstructured":"Alireza Karduni, Amirhassan Kermanshah, and Sybil Derrible. 2016. A protocol to convert spatial polyline data to network formats and applications to world urban road networks. Scientific data 3, 1 (2016), 1--7."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1183--1192","author":"Bruce Reed Kawarabayashi","year":"2009","unstructured":"Ken-ichi Kawarabayashi and Bruce Reed. 2009. A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1183--1192."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_52"},{"key":"e_1_2_1_27_1","volume-title":"Hua Lu, Mohammed Eunus Ali, and Adel N Toosi.","author":"Li Lingxiao","year":"2021","unstructured":"Lingxiao Li, Muhammad Aamir Cheema, Hua Lu, Mohammed Eunus Ali, and Adel N Toosi. 2021. Comparing alternative route planning techniques: A comparative user study on Melbourne, Dhaka and Copenhagen road networks. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"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","volume-title":"2012 IEEE International Conference on Robotics and Automation. IEEE, 2873--2879","author":"Lim Sejoon","year":"2012","unstructured":"Sejoon Lim and Daniela Rus. 2012. Stochastic distributed multi-agent planning and applications to traffic. In 2012 IEEE International Conference on Robotics and Automation. IEEE, 2873--2879."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12205-010-0061-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2773492"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00058"},{"key":"e_1_2_1_37_1","volume-title":"Efficient Constrained Shortest Path Query Answering with Forest Hop Labeling. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). 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 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 1763--1774."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the VLDB Endowment 15","author":"Liu Ziyi","year":"2022","unstructured":"Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, and Xiaofang Zhou. 2022. FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints. Proceedings of the VLDB Endowment 15 (2022)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_23"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767844"},{"key":"e_1_2_1_41_1","first-page":"121","article-title":"A new implementation of Yen's ranking loopless paths algorithm","volume":"1","author":"Martins Ernesto QV","year":"2003","unstructured":"Ernesto QV Martins and Marta MB Pascoal. 2003. A new implementation of Yen's ranking loopless paths algorithm. Quarterly Journal of the Belgian, French and Italian Operations Research Societies 1, 2 (2003), 121--133.","journal-title":"Quarterly Journal of the Belgian, French and Italian Operations Research Societies"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4225\/13"},{"key":"e_1_2_1_43_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2013.2260422"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595916500421"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00574-9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3015274.3015277"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29038-1_41"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0378-1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732941"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389735"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424574"},{"key":"e_1_2_1_58_1","volume-title":"Dynamic Hub Labeling for Road Networks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). 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 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 336--347."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00-69"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3010005"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476267"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T23:12:23Z","timestamp":1720480343000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":62,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551863"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551863","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}