{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:22Z","timestamp":1775638402508,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>\n            2-hop labeling has been widely utilized to accelerate the efficiency of online shortest distance queries. Given the nature of frequent changes in real-world graphs, the efficient maintenance of 2-hop labeling index has been extensively studied recently. However, existing methods cannot efficiently process large-scale graphs due to their high time and memory costs, and most of them process large batches of updates sequentially, significantly decreasing efficiency. In this paper, we propose a novel algorithm for maintaining the 2-hop labeling index in a parallel manner, called\n            <jats:bold>M2HL<\/jats:bold>\n            , which can efficiently handle both edge insertions and deletions. Moreover, we theoretically prove that M2HL maintains both correctness and minimality for the updated 2-hop labeling index. Our experiments on ten large-scale graphs demonstrate that M2HL outperforms the state-of-the-art 2-hop labeling maintenance methods by up to four orders of magnitude in speed while maintaining correctness and minimality, as well as exhibiting strong scalability and low memory usage.\n          <\/jats:p>","DOI":"10.14778\/3734839.3734840","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:06Z","timestamp":1756483266000},"page":"2005-2017","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs"],"prefix":"10.14778","volume":"18","author":[{"given":"Yuanyuan","family":"Zeng","sequence":"first","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China"}]},{"given":"Kun","family":"Chen","sequence":"additional","affiliation":[{"name":"Ant Group, China"}]},{"given":"Yangfan","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha, Hunan, China"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.14"},{"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\u2013360.","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_4_1","volume-title":"WWW","author":"Akiba Takuya","year":"2014","unstructured":"Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2014. Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In WWW, 2014. ACM, 237\u2013248."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453934"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00054"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00977-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467873"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3425891"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544\u20133550","author":"Chen Yankai","year":"2021","unstructured":"Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. 2021. Efficient community search over large directed graphs: An augmented index-based approach. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544\u20133550."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299901"},{"key":"e_1_2_1_13_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\u2013333."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452796"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626731"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00799-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517883"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_20_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\u20131077.","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_21_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\u20131381.","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_23_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\u2013859.","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_2_1_25_1","volume-title":"Myers and Jure Leskovec","author":"Seth","year":"2014","unstructured":"Seth A. Myers and Jure Leskovec. 2014. The bursty dynamics of the Twitter information network. In WWW, 2014. ACM, 913\u2013924."},{"key":"e_1_2_1_26_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\u2013724.","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00071"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00074"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_30_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\u2013876.","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547315"},{"key":"e_1_2_1_32_1","volume-title":"CIKM","author":"Vieira Monique V.","year":"2007","unstructured":"Monique V. Vieira, Bruno M. Fonseca, Rodrigo Damazio, Paulo Braz Golgher, Davi de Castro Reis, and Berthier A. Ribeiro-Neto. 2007. Efficient search ranking in social networks. In CIKM, 2007. ACM, 563\u2013572."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00198"},{"key":"e_1_2_1_34_1","volume-title":"Raymond Chi-Wing Wong, and Cheng Long","author":"Wei Victor Junqiu","year":"2020","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, and Cheng Long. 2020. Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks. In SIGMOD, 2020. ACM, 1841\u20131856."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725261"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639277"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3139111"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675053"},{"key":"e_1_2_1_41_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_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589408"},{"key":"e_1_2_1_43_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\u2013144."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3236632"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389737"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517875"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00348"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3734839.3734840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:20Z","timestamp":1756483280000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3734839.3734840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":47,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.14778\/3734839.3734840"],"URL":"https:\/\/doi.org\/10.14778\/3734839.3734840","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}