{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:09:57Z","timestamp":1775912997238,"version":"3.50.1"},"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":[[2022,7]]},"abstract":"<jats:p>\n            Multi-Constraint Shortest Path (\n            <jats:italic>MCSP<\/jats:italic>\n            ) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However,\n            <jats:italic>MCSP<\/jats:italic>\n            query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current\n            <jats:italic>Forest Hop Labeling (FHL)<\/jats:italic>\n            index can answer\n            <jats:italic>MCSP<\/jats:italic>\n            efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based\n            <jats:italic>FHL<\/jats:italic>\n            index that can handle the flexible\n            <jats:italic>MCSP<\/jats:italic>\n            efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the\n            <jats:italic>FHL<\/jats:italic>\n            structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.\n          <\/jats:p>","DOI":"10.14778\/3551793.3551856","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3112-3125","source":"Crossref","is-referenced-by-count":21,"title":["FHL-cube"],"prefix":"10.14778","volume":"15","author":[{"given":"Ziyi","family":"Liu","sequence":"first","affiliation":[{"name":"The University of Queensland, Brisbane, QLD, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengxuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Iowa State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Hua","sequence":"additional","affiliation":[{"name":"Iowa State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"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. [n.d.]. 9th DIMACS Implementation Challenge - Shortest Paths. http:\/\/users.diag.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Complete version of this paper. https:\/\/www.dropbox.com\/s\/3nr2jnch7ok0l4b\/documentFull.pdf?dl=0.  [n.d.]. Complete version of this paper. https:\/\/www.dropbox.com\/s\/3nr2jnch7ok0l4b\/documentFull.pdf?dl=0."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2014.09.005"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_5_1","first-page":"256","article-title":"Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks","volume":"52","author":"Carlyle W Matthew","year":"2008","unstructured":"W Matthew Carlyle , Johannes O Royset , and R Kevin Wood . 2008 . Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks : An International Journal 52 , 4 (2008), 256 -- 270 . W Matthew Carlyle, Johannes O Royset, and R Kevin Wood. 2008. Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks: An International Journal 52, 4 (2008), 256--270.","journal-title":"An International Journal"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0274-x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ATM.1998.675192"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_13"},{"key":"e_1_2_1_10_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. 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_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871504"},{"key":"e_1_2_1_12_1","volume-title":"Computers and intractability","author":"Garey Michael R","unstructured":"Michael R Garey and David S Johnson . 1979. Computers and intractability . Vol. 174 . freeman San Francisco . Michael R Garey and David S Johnson. 1979. Computers and intractability. Vol. 174. freeman San Francisco."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the VLDB Endowment","volume":"5","author":"Godfrey Parke","year":"2005","unstructured":"Parke Godfrey , Ryan Shipley , Jarek Gryz , 2005 . Maximal vector computation in large data sets . In Proceedings of the VLDB Endowment , Vol. 5 . Citeseer, 229--240. Parke Godfrey, Ryan Shipley, Jarek Gryz, et al. 2005. Maximal vector computation in large data sets. In Proceedings of the VLDB Endowment, Vol. 5. Citeseer, 229--240."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00087"},{"key":"e_1_2_1_16_1","unstructured":"Jason Hahn. [n.d.]. New York City to Google: Reduce the number of left turns in Maps navigation directions. https:\/\/www.foxnews.com\/auto\/new-york-city-to-google-reduce-the-number-of-left-turns-in-maps-navigation-directions.  Jason Hahn. [n.d.]. New York City to Google: Reduce the number of left turns in Maps navigation directions. https:\/\/www.foxnews.com\/auto\/new-york-city-to-google-reduce-the-number-of-left-turns-in-maps-navigation-directions."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100403"},{"key":"e_1_2_1_18_1","volume-title":"Multiple criteria decision making theory and application","author":"Hansen Pierre","unstructured":"Pierre Hansen . 1980. Bicriterion path problems . In Multiple criteria decision making theory and application . Springer , 109--127. Pierre Hansen. 1980. Bicriterion path problems. In Multiple criteria decision making theory and application. Springer, 109--127."},{"key":"e_1_2_1_19_1","volume-title":"Approximation schemes for the restricted shortest path problem. Mathematics of Operations research 17, 1","author":"Hassin Refael","year":"1992","unstructured":"Refael Hassin . 1992. Approximation schemes for the restricted shortest path problem. Mathematics of Operations research 17, 1 ( 1992 ), 36--42. Refael Hassin. 1992. Approximation schemes for the restricted shortest path problem. Mathematics of Operations research 17, 1 (1992), 36--42."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140109"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90020-5"},{"key":"e_1_2_1_22_1","volume-title":"Multi-objective vehicle routing problems. European journal of operational research 189, 2","author":"Jozefowiez Nicolas","year":"2008","unstructured":"Nicolas Jozefowiez , Fr\u00e9d\u00e9ric Semet , and El-Ghazali Talbi . 2008. Multi-objective vehicle routing problems. European journal of operational research 189, 2 ( 2008 ), 293--309. Nicolas Jozefowiez, Fr\u00e9d\u00e9ric Semet, and El-Ghazali Talbi. 2008. Multi-objective vehicle routing problems. European journal of operational research 189, 2 (2008), 293--309."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2001.916277"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567688.2567691"},{"key":"e_1_2_1_25_1","first-page":"834","article-title":"Multi-constrained optimal path selection","volume":"2","author":"Korkmaz Turgay","year":"2001","unstructured":"Turgay Korkmaz and Marwan Krunz . 2001 . Multi-constrained optimal path selection . In INFOCOM , Vol. 2. 834 -- 843 . Turgay Korkmaz and Marwan Krunz. 2001. Multi-constrained optimal path selection. In INFOCOM, Vol. 2. 834--843.","journal-title":"INFOCOM"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Hans-Peter Kriegel Peer Kr\u00f6ger Peter Kunath Matthias Renz and Tim Schmidt. 2007. Proximity queries in large traffic networks. In ACM GIS. 1--8.  Hans-Peter Kriegel Peer Kr\u00f6ger Peter Kunath Matthias Renz and Tim Schmidt. 2007. Proximity queries in large traffic networks. In ACM GIS. 1--8.","DOI":"10.1145\/1341012.1341040"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447845"},{"key":"e_1_2_1_28_1","volume-title":"A comparison of exact and \u03b5-approximation algorithms for constrained routing","author":"Kuipers Fernando","unstructured":"Fernando Kuipers , Ariel Orda , Danny Raz , and Piet Van Mieghem . 2006. A comparison of exact and \u03b5-approximation algorithms for constrained routing . In NETWORKING. Springer , 197--208. Fernando Kuipers, Ariel Orda, Danny Raz, and Piet Van Mieghem. 2006. A comparison of exact and \u03b5-approximation algorithms for constrained routing. In NETWORKING. Springer, 197--208."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"key":"e_1_2_1_30_1","volume-title":"Time-Dependent Hop Labeling on Road Network. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 902--913","author":"Li Lei","year":"2019","unstructured":"Lei Li , Sibo Wang , and Xiaofang Zhou . 2019 . Time-Dependent Hop Labeling on Road Network. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 902--913 . Lei Li, Sibo Wang, and Xiaofang Zhou. 2019. Time-Dependent Hop Labeling on Road Network. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 902--913."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2981062"},{"key":"e_1_2_1_32_1","volume-title":"Fast Query Decomposition for Batch Shortest Path Processing in Road Networks. In 2020 IEEE 36th International Conference on Data Engineering (ICDE).","author":"Li Lei","year":"2020","unstructured":"Lei Li , Mengxuan Zhang , Wen Hua , and Xiaofang Zhou . 2020 . Fast Query Decomposition for Batch Shortest Path Processing in Road Networks. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). Lei Li, Mengxuan Zhang, Wen Hua, and Xiaofang Zhou. 2020. Fast Query Decomposition for Batch Shortest Path Processing in Road Networks. In 2020 IEEE 36th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0499-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18123-3_13"},{"key":"e_1_2_1_36_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 . 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_37_1","volume-title":"Multi-Constraint Shortest Path using Forest Hop Labeling. The VLDB Journal","author":"Liu Ziyi","year":"2022","unstructured":"Ziyi Liu , Lei Li , Mengxuan Zhang , Wen Hua , and Xiaofang Zhou . 2022. Multi-Constraint Shortest Path using Forest Hop Labeling. The VLDB Journal ( 2022 ). Ziyi Liu, Lei Li, Mengxuan Zhang, Wen Hua, and Xiaofang Zhou. 2022. Multi-Constraint Shortest Path using Forest Hop Labeling. The VLDB Journal (2022)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00069-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.07.008"},{"key":"e_1_2_1_40_1","unstructured":"Shengliang Lu Bingsheng He Yuchen Li and Hao Fu. 2020. Accelerating exact constrained shortest paths on GPUs. (2020).  Shengliang Lu Bingsheng He Yuchen Li and Hao Fu. 2020. Accelerating exact constrained shortest paths on GPUs. (2020)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820835"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91452-7_16"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137647"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367855"},{"key":"e_1_2_1_48_1","volume-title":"Y) 100, 4","author":"Pei Jian","year":"2005","unstructured":"Jian Pei , Wen Jin , Martin Ester , and Yufei Tao . 2005. Catching the best views of skyline: A semantic approach based on decisive subspaces. Space (X , Y) 100, 4 ( 2005 ), 1. Jian Pei, Wen Jin, Martin Ester, and Yufei Tao. 2005. Catching the best views of skyline: A semantic approach based on decisive subspaces. Space (X, Y) 100, 4 (2005), 1."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920948"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.05.109"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2017.02.002"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Sabine Storandt. 2012. Route planning for bicycles---exact constrained shortest paths made practical via contraction hierarchy. In ICAPS.  Sabine Storandt. 2012. Route planning for bicycles---exact constrained shortest paths made practical via contraction hierarchy. In ICAPS.","DOI":"10.1609\/icaps.v22i1.13495"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9096-4"},{"key":"e_1_2_1_54_1","volume-title":"On the complexity of QoS routing. Computer communications 26, 4","author":"Mieghem Piet Van","year":"2003","unstructured":"Piet Van Mieghem and Fernando A Kuipers . 2003. On the complexity of QoS routing. Computer communications 26, 4 ( 2003 ), 376--387. Piet Van Mieghem and Fernando A Kuipers. 2003. On the complexity of QoS routing. Computer communications 26, 4 (2003), 376--387."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3015274.3015277"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.37"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_59_1","volume-title":"An efficient index method for the optimal path query over multi-cost networks. World Wide Web","author":"Yang Yajun","year":"2021","unstructured":"Yajun Yang , Hang Zhang , Hong Gao , and Xin Wang . 2021. An efficient index method for the optimal path query over multi-cost networks. World Wide Web ( 2021 ), 1--23. Yajun Yang, Hang Zhang, Hong Gao, and Xin Wang. 2021. An efficient index method for the optimal path query over multi-cost networks. World Wide Web (2021), 1--23."},{"key":"e_1_2_1_60_1","volume-title":"Route Recommendations on Road Networks for Arbitrary User Preference Functions. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 602--613","author":"Yawalkar Pranali","year":"2019","unstructured":"Pranali Yawalkar and Sayan Ranu . 2019 . Route Recommendations on Road Networks for Arbitrary User Preference Functions. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 602--613 . Pranali Yawalkar and Sayan Ranu. 2019. Route Recommendations on Road Networks for Arbitrary User Preference Functions. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 602--613."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59419-0_16"},{"key":"e_1_2_1_63_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 . 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_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.14778\/3476249.3476267"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-69377-0_14"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:52:01Z","timestamp":1672224721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551856"}},"subtitle":["multi-constraint shortest path querying with flexible combination of constraints"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":67,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551856"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551856","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}