{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:14Z","timestamp":1779174794798,"version":"3.51.4"},"reference-count":44,"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>The shortest-path query, which returns the shortest path between two vertices, is a basic operation on complex networks and has numerous applications. To handle shortest-path queries, one option is to use traversal-based methods (e.g., breadth-first search); another option is to use extension-based methods, i.e., extending existing methods that use indexes to handle shortest-distance queries to support shortest-path queries. These two types of methods make different trade-offs in query time and space cost, but comprehensive studies of their performance on real-world graphs are lacking. Moreover, extension-based methods usually use extra attributes to extend the indexes, resulting in high space costs. To address these issues, we thoroughly compare the two types of methods mentioned above. We also propose a new extension-based approach, Monotonic Landmark Labeling (MLL), to reduce the required space cost while still guaranteeing query time. We compare the performance of different methods on ten large real-world graphs with up to 5.5 billion edges. The experimental results reveal the characteristics of various methods, allowing practitioners to select the appropriate method for a specific application.<\/jats:p>","DOI":"10.14778\/3551793.3551820","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"2640-2652","source":"Crossref","is-referenced-by-count":21,"title":["Shortest-path queries on complex networks"],"prefix":"10.14778","volume":"15","author":[{"given":"Junhua","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wentao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[{"name":"Nanjing University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.77"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"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","volume-title":"Complex networks: Structure and dynamics. Physics reports 424, 4--5","author":"Boccaletti Stefano","year":"2006","unstructured":"Stefano Boccaletti , Vito Latora , Yamir Moreno , Martin Chavez , and D-U Hwang . 2006. Complex networks: Structure and dynamics. Physics reports 424, 4--5 ( 2006 ), 175--308. Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D-U Hwang. 2006. Complex networks: Structure and dynamics. Physics reports 424, 4--5 (2006), 175--308."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0274-x"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_13_1","volume-title":"Characterization of complex networks: A survey of measurements. Advances in physics 56, 1","author":"Costa L","year":"2007","unstructured":"L da F Costa , Francisco A Rodrigues , Gonzalo Travieso , and Paulino Ribeiro Villas Boas . 2007. Characterization of complex networks: A survey of measurements. Advances in physics 56, 1 ( 2007 ), 167--242. L da F Costa, Francisco A Rodrigues, Gonzalo Travieso, and Paulino Ribeiro Villas Boas. 2007. Characterization of complex networks: A survey of measurements. Advances in physics 56, 1 (2007), 167--242."},{"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.14778\/2095686.2095694"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_17_1","volume-title":"SODA","volume":"5","author":"Goldberg Andrew V","year":"2005","unstructured":"Andrew V Goldberg and Chris Harrelson . 2005 . Computing the shortest path: A search meets graph theory .. In SODA , Vol. 5 . Citeseer, 156--165. Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory.. In SODA, Vol. 5. Citeseer, 156--165."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.12.013"},{"key":"e_1_2_1_21_1","volume-title":"Raymond Chi-Wing Wong, and Yanyan Xu.","author":"Jiang Minhao","year":"2014","unstructured":"Minhao Jiang , Ada Wai-Chee Fu , Raymond Chi-Wing Wong, and Yanyan Xu. 2014 . Hop doubling label indexing for point-to-point distance querying on scale-free networks. arXiv preprint arXiv:1403.0779 (2014). Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, and Yanyan Xu. 2014. Hop doubling label indexing for point-to-point distance querying on scale-free networks. arXiv preprint arXiv:1403.0779 (2014)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321768"},{"key":"e_1_2_1_23_1","volume-title":"A fast algorithm for Steiner trees. Acta informatica 15, 2","author":"Kou Lawrence","year":"1981","unstructured":"Lawrence Kou , George Markowsky , and Leonard Berman . 1981. A fast algorithm for Steiner trees. Acta informatica 15, 2 ( 1981 ), 141--145. Lawrence Kou, George Markowsky, and Leonard Berman. 1981. A fast algorithm for Steiner trees. Acta informatica 15, 2 (1981), 141--145."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732978"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_30_1","volume-title":"Evolution and structure of the Internet: A statistical physics approach","author":"Pastor-Satorras Romualdo","unstructured":"Romualdo Pastor-Satorras and Alessandro Vespignani . 2007. Evolution and structure of the Internet: A statistical physics approach . Cambridge University Press . Romualdo Pastor-Satorras and Alessandro Vespignani. 2007. Evolution and structure of the Internet: A statistical physics approach. Cambridge University Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti116"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1181967.1324391"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.172"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164135.3164139"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380110"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452826"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_41_1","volume-title":"Andy Diwen Zhu, and Shuigeng Zhou","author":"Wu Lingkun","year":"2012","unstructured":"Lingkun Wu , Xiaokui Xiao , Dingxiong Deng , Gao Cong , Andy Diwen Zhu, and Shuigeng Zhou . 2012 . Shortest path and distance queries on road networks: An experimental evaluation. arXiv preprint arXiv:1201.6564 (2012). Lingkun Wu, Xiaokui Xiao, Dingxiong Deng, Gao Cong, Andy Diwen Zhu, and Shuigeng Zhou. 2012. Shortest path and distance queries on road networks: An experimental evaluation. arXiv preprint arXiv:1201.6564 (2012)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSB.2005.9"},{"key":"e_1_2_1_43_1","unstructured":"Junhua Zhang Wentao Li Long Yuan Lu Qin Ying Zhang and Lijun Chang. 2022. Technical Report. https:\/\/www.dropbox.com\/sh\/gv96k90xz02fopd\/AACYG6d6FftmNiWzzT1JflKya?dl=0  Junhua Zhang Wentao Li Long Yuan Lu Qin Ying Zhang and Lijun Chang. 2022. Technical Report. https:\/\/www.dropbox.com\/sh\/gv96k90xz02fopd\/AACYG6d6FftmNiWzzT1JflKya?dl=0"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389737"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:33:56Z","timestamp":1672223636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551820"}},"subtitle":["experiments, analyses, and improvement"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":44,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551820"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551820","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}