{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:44:49Z","timestamp":1787017489990,"version":"build-2736575974"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62176026"],"award-info":[{"award-number":["62176026"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Beijing Natural Science Foundation","award":["M22009"],"award-info":[{"award-number":["M22009"]}]},{"name":"BUPT innovation and entrepreneurship support program","award":["2023-YC-T008"],"award-info":[{"award-number":["2023-YC-T008"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>\n                    Landmark-based 3-hop cover labeling is a category of approaches for shortest distance\/path queries on large-scale complex networks. It pre-computes an index offline to accelerate the online distance\/path query. Most real-world graphs undergo rapid changes in topology, which makes index maintenance on dynamic graphs necessary. So far, the majority of index maintenance methods can handle only one edge update (either an addition or deletion) each time. To keep up with frequently changing graphs, we research the\n                    <jats:italic>\n                      <jats:bold>ful<\/jats:bold>\n                    <\/jats:italic>\n                    ly\n                    <jats:italic>\n                      <jats:bold>b<\/jats:bold>\n                    <\/jats:italic>\n                    atch\n                    <jats:italic>\n                      <jats:bold>m<\/jats:bold>\n                    <\/jats:italic>\n                    aintenance problem for the 3-hop cover labeling, and proposed the method called\n                    <jats:italic>FulBM<\/jats:italic>\n                    . FulBM is composed of two algorithms: InsBM and DelBM, which are designed to handle batch edge insertions and deletions, respectively. This separation is motivated by the insight that batch maintenance for edge insertions are much more time-efficient and the fact that most edge updates in the real world are incremental. Both InsBM and DelBM are equipped with well-designed pruning strategies to minimize the number of vertex accesses. We have conducted comprehensive experiments on both synthetic and real-world graphs to verify the efficiency of FulBM and its variants for weighted graphs. The results show that our methods achieve 5.5\u00d7 to 228\u00d7 speedup compared with the state-of-the-art method.\n                  <\/jats:p>","DOI":"10.1145\/3650035","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T08:01:32Z","timestamp":1710489692000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["FulBM: Fast Fully Batch Maintenance for Landmark-based 3-hop Cover Labeling"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3007-0554","authenticated-orcid":false,"given":"Wentai","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2087-586X","authenticated-orcid":false,"given":"HaiHong","family":"E","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2727-0361","authenticated-orcid":false,"given":"Haoran","family":"Luo","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7967-1373","authenticated-orcid":false,"given":"Mingzhi","family":"Sun","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323196"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9154"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972894.10"},{"key":"e_1_3_1_8_2","first-page":"1","article-title":"Fully dynamic 2-hop cover labeling","volume":"24","author":"D\u2019Angelo Gianlorenzo","year":"2019","unstructured":"Gianlorenzo D\u2019Angelo, Mattia D\u2019emidio, and Daniele Frigioni. 2019. Fully dynamic 2-hop cover labeling. J. Experim. Algor. 24 (2019), 1\u201336.","journal-title":"J. Experim. Algor."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Edsger Wybe Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1 (1959) 269\u2013271).-","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13080191"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517883"},{"key":"e_1_3_1_13_2","article-title":"A highly scalable labelling approach for exact distance queries in complex networks","author":"Farhan Muhammad","year":"2018","unstructured":"Muhammad Farhan, Qing Wang, Yu Lin, and Brendan Mckay. 2018. A highly scalable labelling approach for exact distance queries in complex networks. arXiv preprint arXiv:1812.02363 (2018).","journal-title":"arXiv preprint arXiv:1812.02363"},{"key":"e_1_3_1_14_2","doi-asserted-by":"crossref","unstructured":"Muhammad Farhan Qing Wang Yu Lin and Brendan McKay. 2022. Fast fully dynamic labelling for distance queries. The VLDB Journal 31 3 (2022) 483\u2013506.","DOI":"10.1007\/s00778-021-00707-z"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_3_1_17_2","volume-title":"Exploring Network Structure, Dynamics, and Function Using NetworkX","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter Swart, and Daniel S. Chult. 2008. Exploring Network Structure, Dynamics, and Function Using NetworkX. Technical Report. Los Alamos National Lab, Los Alamos, NM."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983731"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401945"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"key":"e_1_3_1_23_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554824"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"issue":"1","key":"e_1_3_1_26_2","first-page":"300","article-title":"Fastest path query answering using time-dependent hop-labeling in road network","volume":"34","author":"Li Lei","year":"2020","unstructured":"Lei Li, Sibo Wang, and Xiaofang Zhou. 2020. Fastest path query answering using time-dependent hop-labeling in road network. IEEE Trans. Knowl. Data Eng. 34, 1 (2020), 300\u2013313.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00107"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568043"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0421-1"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452826"},{"key":"e_1_3_1_35_2","article-title":"Shortest path and distance queries on road networks: An experimental evaluation","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).","journal-title":"arXiv preprint arXiv:1201.6564"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339491"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00036"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3010005"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"e_1_3_1_40_2","doi-asserted-by":"crossref","unstructured":"Mengxuan Zhang Lei Li Goce Trajcevski Andreas Zufle and Xiaofang Zhou. 2023. Parallel hub labelingmaintenance with high efficiency in dynamic small-world networks. IEEE Transactions on Knowledge& Data Engineering 35 11 (2023) 11751\u201311768.","DOI":"10.1109\/TKDE.2023.3236632"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476267"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389737"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3650035","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3650035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:03:43Z","timestamp":1750277023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3650035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3650035"],"URL":"https:\/\/doi.org\/10.1145\/3650035","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2023-06-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}