{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:26:20Z","timestamp":1786638380398,"version":"build-2736575974"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>Shortest path distance retrieval is a core component in many important applications. For a decade, hub labeling (HL) techniques have been considered as a practical solution with fast query response time (e.g., 1--3 orders of magnitude faster), competitive indexing time, and slightly larger storage overhead (e.g., several times larger). These techniques enhance query throughput up to hundred thousands queries per second, which is particularly helpful in large user environment. Despite the importance of HL techniques, we are not aware of any comprehensive experimental study on HL techniques. Thus it is difficult for a practitioner to adopt HL techniques for her applications.<\/jats:p>\n          <jats:p>To address the above issues, we provide a comprehensive experimental study on the state-of-the-art HL technique with analysis of their efficiency, effectiveness and applicability. From insightful summary of different HL techniques, we further develop a simple yet effective HL techniques called Significant path based Hub Pushing (SHP) which greatly improves indexing time of previous techniques while retains good query performance. We also complement extensive comparisons between HL techniques and other shortest path solutions to demonstrate robustness and efficiency of HL techniques.<\/jats:p>","DOI":"10.1145\/3186728.3164141","type":"journal-article","created":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T10:54:54Z","timestamp":1574247294000},"page":"445-457","source":"Crossref","is-referenced-by-count":78,"title":["An experimental study on hub labeling based shortest path algorithms"],"prefix":"10.14778","volume":"11","author":[{"given":"Ye","family":"Li","sequence":"first","affiliation":[{"name":"University of Macau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leong Hou","family":"U","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ngai Meng","family":"Kou","sequence":"additional","affiliation":[{"name":"University of Macau"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/degroup.cis.umac.mo\/sspexp.  http:\/\/degroup.cis.umac.mo\/sspexp."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790174.2790188"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_2_1_8_1","first-page":"62","volume-title":"MFCS","author":"Babenko M.","year":"2015","unstructured":"M. Babenko , A. V. Goldberg , H. Kaplan , R. Savchenko , and M. Weller . On the complexity of hub labeling . In MFCS , pages 62 -- 74 , 2015 . M. Babenko, A. V. Goldberg, H. Kaplan, R. Savchenko, and M. Weller. On the complexity of hub labeling. In MFCS, pages 62--74, 2015."},{"key":"e_1_2_1_9_1","volume-title":"Route planning in transportation networks. arXiv preprint arXiv:1504.05140","author":"Bast H.","year":"2015","unstructured":"H. Bast , D. Delling , A. Goldberg , M. M\u00fcller-Hannemann , T. Pajor , P. Sanders , D. Wagner , and R. F. Werneck . Route planning in transportation networks. arXiv preprint arXiv:1504.05140 , 2015 . H. Bast, D. Delling, A. Goldberg, M. M\u00fcller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. arXiv preprint arXiv:1504.05140, 2015."},{"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\/1498698.1537599"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_16_1","first-page":"2","article-title":"Robust exact distance queries on massive networks. Microsoft Research, USA","author":"Delling D.","year":"2014","unstructured":"D. Delling , A. V. Goldberg , T. Pajor , and R. F. Werneck . Robust exact distance queries on massive networks. Microsoft Research, USA , Tech. Rep , 2 , 2014 . D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Robust exact distance queries on massive networks. Microsoft Research, USA, Tech. Rep, 2, 2014.","journal-title":"Tech. Rep"},{"key":"e_1_2_1_17_1","volume-title":"Transportation Science","author":"Delling D.","year":"2015","unstructured":"D. Delling , A. V. Goldberg , T. Pajor , and R. F. Werneck . Customizable route planning in road networks . Transportation Science , 2015 . D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning in road networks. Transportation Science, 2015."},{"key":"e_1_2_1_18_1","first-page":"18","volume-title":"SEA","author":"Delling D.","year":"2013","unstructured":"D. Delling , A. V. Goldberg , and R. F. Werneck . Hub label compression . In SEA , pages 18 -- 29 . 2013 . D. Delling, A. V. Goldberg, and R. F. Werneck. Hub label compression. In SEA, pages 18--29. 2013."},{"key":"e_1_2_1_19_1","volume-title":"9th dimacs implementation challenge-shortest paths","author":"Demetrescu C.","year":"2006","unstructured":"C. Demetrescu , A. Goldberg , and D. Johnson . 9th dimacs implementation challenge-shortest paths . American Mathematical Society , 2006 . C. Demetrescu, A. Goldberg, and D. Johnson. 9th dimacs implementation challenge-shortest paths. American Mathematical Society, 2006."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070455"},{"key":"e_1_2_1_25_1","first-page":"93","volume-title":"The Shortest Path Problem","author":"Goldberg A. V.","year":"2006","unstructured":"A. V. Goldberg , H. Kaplan , and R. F. Werneck . Reach for a*: Shortest path algorithms with preprocessing . In The Shortest Path Problem , pages 93 -- 140 , 2006 . A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for a*: Shortest path algorithms with preprocessing. In The Shortest Path Problem, pages 93--140, 2006."},{"key":"e_1_2_1_26_1","first-page":"100","article-title":"A new approach to shortest path algorithms optimized for road networks","volume":"4","author":"Gutman R. J.","year":"2004","unstructured":"R. J. Gutman . Reach-based routing : A new approach to shortest path algorithms optimized for road networks . ALENEX\/ANALC , 4 : 100 -- 111 , 2004 . R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. ALENEX\/ANALC, 4:100--111, 2004.","journal-title":"ALENEX\/ANALC"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_31_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_33_1","first-page":"145","volume-title":"EDBT","author":"Qin Y.","year":"2015","unstructured":"Y. Qin , Q. Z. Sheng , and W. E. Zhang . Sief: Efficiently answering distance queries for failure prone graphs . In EDBT , pages 145 -- 156 , 2015 . Y. Qin, Q. Z. Sheng, and W. E. Zhang. Sief: Efficiently answering distance queries for failure prone graphs. In EDBT, pages 145--156, 2015."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_71"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321520"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_2_1_40_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\/10.1145\/3186728.3164141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186728.3164141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:31Z","timestamp":1750273651000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186728.3164141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1145\/3186728.3164141"],"URL":"https:\/\/doi.org\/10.1145\/3186728.3164141","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}