{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:20Z","timestamp":1775638400261,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:p>Distance labeling approaches are widely adopted to speed up the shortest-distance query performance. Due to the explosive growth of data graphs, a single machine can hardly satisfy the requirements of both computational power and memory capacity, which causes an urgent need for efficient distributed methods. As the graph is distributed across different machines, it is inevitable to frequently exchange messages among different machines when deploying the existing centralized distance labeling methods on the distributed environment, thereby producing serious communication costs and weakening the scalability. To alleviate this problem, we design a distributed hop-based index<jats:bold>DH-Index<\/jats:bold>, which is designed based on a newly proposed boundary graph structure and restricts the index-based hop number of each connected vertex pair within 4 hops. In addition, we propose a hierarchical algorithm to accelerate the index construction and reduce the communication cost. Furthermore, a bidirectional searching strategy is proposed to efficiently resolve the query tasks based on DH-Index. The comprehensive experimental results on eight real-world graphs demonstrate that DH-Index achieves up to 65.5\u00d7 and 3 orders of magnitude speedup than the existing methods in indexing time and query performance respectively, and exhibits superior capabilities on memory space, communication cost, and scalability.<\/jats:p>","DOI":"10.14778\/3675034.3675053","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:11Z","timestamp":1722982751000},"page":"2641-2653","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Distributed Shortest Distance Labeling on Large-Scale Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Yuanyuan","family":"Zeng","sequence":"first","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"SEA","volume":"241","author":"Abraham Ittai","year":"2011","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato Fonseca F. Werneck. 2011. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. In SEA, 2011 (Lecture Notes in Computer Science, Vol. 6630). Springer, 230--241."},{"key":"e_1_2_1_2_1","volume-title":"ESA","volume":"35","author":"Abraham Ittai","year":"2012","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato Fonseca F. Werneck. 2012. Hierarchical Hub Labelings for Shortest Paths. In ESA, 2012 (Lecture Notes in Computer Science, Vol. 7501). Springer, 24--35."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Takuya Akiba Yoichi Iwata and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. ACM 349--360.","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467873"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_7_1","first-page":"148","article-title":"An Optimality Theorem for a Bi-Directional Heuristic Search","volume":"20","author":"de Champeaux Dennis","year":"1977","unstructured":"Dennis de Champeaux and Lenie Sint. 1977. An Optimality Theorem for a Bi-Directional Heuristic Search Algorithm. Comput. J. 20, 2 (1977), 148--150.","journal-title":"Algorithm. Comput. J."},{"key":"e_1_2_1_8_1","volume-title":"Werneck","author":"Delling Daniel","year":"2014","unstructured":"Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2014. Robust Distance Queries on Massive Networks. In ESA (Lecture Notes in Computer Science, Vol. 8737). Springer, 321--333."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_11_1","volume-title":"WEA","volume":"333","author":"Geisberger Robert","year":"2008","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In WEA, 2008 (Lecture Notes in Computer Science, Vol. 5038). Springer, 319--333."},{"key":"e_1_2_1_12_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In SODA, 2005. SIAM, 156--165."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489499"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"181601","DOI":"10.1007\/s11704-022-2368-y","article-title":"Answering reachability queries with ordered label constraints over labeled graphs","volume":"18","author":"He Daoliang","year":"2024","unstructured":"Daoliang He, Pingpeng Yuan, and Hai Jin. 2024. Answering reachability queries with ordered label constraints over labeled graphs. Frontiers Comput. Sci. 18, 1 (2024), 181601.","journal-title":"Frontiers Comput. Sci."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2019. Scaling Distance Labeling on Small-World Networks. In SIGMOD. ACM 1060--1077.","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Wentao Li Miao Qiao Lu Qin Ying Zhang Lijun Chang and Xuemin Lin. 2020. Scaling Up Distance Labeling on Graphs with Core-Periphery Properties. In SIGMOD. ACM 1367--1381.","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Chenhao Ma Yixiang Fang Reynold Cheng Laks V. S. Lakshmanan and Xiaolin Han. 2022. A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery. In SIGMOD. ACM 845--859.","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Dian Ouyang Lu Qin Lijun Chang Xuemin Lin Ying Zhang and Qing Zhu. 2018. When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks. In SIGMOD. ACM 709--724.","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_2_1_24_1","volume-title":"ICDE","author":"Peng Peng","year":"2022","unstructured":"Peng Peng, M. Tamer \u00d6zsu, Lei Zou, Cen Yan, and Chengjun Liu. 2022. MPC: Minimum Property-Cut RDF Graph Partitioning. In ICDE, 2022. IEEE, 192--204."},{"key":"e_1_2_1_25_1","volume-title":"ICDE","author":"Peng You","year":"2023","unstructured":"You Peng, Zhuo Ma, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xiaoshuang Chen. 2023. Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs. In ICDE, 2023. IEEE, 856--868."},{"key":"e_1_2_1_26_1","volume-title":"ICDE","author":"Peng You","year":"2023","unstructured":"You Peng, Jeffrey Xu Yu, and Sibo Wang. 2023. PSPC: Efficient Parallel Shortest Path Counting on Large-Scale Graphs. In ICDE, 2023. IEEE, 896--908."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Michalis Potamias Francesco Bonchi Carlos Castillo and Aristides Gionis. 2009. Fast shortest path distance estimation in large networks. In CIKM. ACM 867--876.","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547315"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Polina Rozenshtein Aris Anagnostopoulos Aristides Gionis and Nikolaj Tatti. 2014. Event detection in activity networks. In SIGKDD. ACM 1176--1185.","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_2_1_31_1","volume-title":"12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings (Lecture Notes in Computer Science","volume":"175","author":"Sanders Peter","year":"2013","unstructured":"Peter Sanders and Christian Schulz. 2013. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7933). Springer, 164--175."},{"key":"e_1_2_1_32_1","volume-title":"ICDE","author":"Wen Dong","year":"2020","unstructured":"Dong Wen, Yilun Huang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2020. Efficiently Answering Span-Reachability Queries in Large Temporal Graphs. In ICDE, 2020. IEEE, 1153--1164."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0338-6"},{"key":"e_1_2_1_34_1","volume-title":"ICDE","author":"Xu Yehong","year":"2023","unstructured":"Yehong Xu, Lei Li, Mengxuan Zhang, Zizhuo Xu, and Xiaofang Zhou. 2023. Global Routing Optimization In Road Networks. In ICDE, 2023. IEEE, 2524--2537."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_36_1","volume-title":"ICDE","author":"Yang Lei","year":"2021","unstructured":"Lei Yang and Lei Zou. 2021. Noah: Neural-optimized A* Search Algorithm for Graph Edit Distance Computation. In ICDE, 2021. IEEE, 576--587."},{"key":"e_1_2_1_37_1","first-page":"3","volume-title":"Proc. ACM Manag. Data 2","author":"Zeng Yuanyuan","year":"2024","unstructured":"Yuanyuan Zeng, Yixiang Fang, Chenhao Ma, Xu Zhou, and Kenli Li. 2024. Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs. Proc. ACM Manag. Data 2, 3 (2024), 22:1--22:25."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3139111"},{"key":"e_1_2_1_39_1","volume-title":"Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs","author":"Zeng Yuanyuan","unstructured":"Yuanyuan Zeng, Wangdong Yang, Xu Zhou, Guoqin Xiao, Yunjun Gao, and Kenli Li. 2022. Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs. In ICDE. IEEE."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551820"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494148"},{"key":"e_1_2_1_42_1","volume-title":"Efficient 2-Hop Labeling Maintenance in Dynamic Small-World Networks","author":"Zhang Mengxuan","unstructured":"Mengxuan Zhang, Lei Li, Wen Hua, and Xiaofang Zhou. 2021. Efficient 2-Hop Labeling Maintenance in Dynamic Small-World Networks. In ICDE. IEEE, 133--144."},{"key":"e_1_2_1_43_1","volume-title":"SIGMOD","author":"Zhang Yikai","year":"2020","unstructured":"Yikai Zhang and Jeffrey Xu Yu. 2020. Hub Labeling for Shortest Path Counting. In SIGMOD, 2020. ACM, 1813--1828."},{"key":"e_1_2_1_44_1","volume-title":"ICDE","author":"Zheng Bolong","year":"2023","unstructured":"Bolong Zheng, Yong Ma, Jingyi Wan, Yongyong Gao, Kai Huang, Xiaofang Zhou, and Christian S. Jensen. 2023. Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks. In ICDE, 2023. IEEE, 1678--1690."},{"key":"e_1_2_1_45_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\/3675034.3675053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T07:41:24Z","timestamp":1732606884000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3675034.3675053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10.14778\/3675034.3675053"],"URL":"https:\/\/doi.org\/10.14778\/3675034.3675053","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}