{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:58:12Z","timestamp":1756573092921,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000995","name":"Australian National University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000995","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many real-world applications operate on dynamic graphs to perform important tasks. In this article, we study batch-dynamic algorithms that are capable of updating distance labelling efficiently in order to reflect the effects of rapid changes on such graphs. To explore the full pruning potentials, we first characterize the minimal set of vertices being affected by batch updates. Then, we reveal patterns of interactions among different updates (edge insertions and edge deletions) and leverage them to design pruning rules for reducing update search space. These interesting findings lead us to developing a new batch-dynamic method, called BatchHL<jats:inline-formula><jats:alternatives><jats:tex-math>$$^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow\/>\n                    <mml:mo>+<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which can dynamize labelling for distance queries much more efficiently than existing work. We provide formal proofs for the correctness and minimality of BatchHL<jats:inline-formula><jats:alternatives><jats:tex-math>$$^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow\/>\n                    <mml:mo>+<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which are non-trivial and require a delicate analysis of patterns of interactions. Empirically, we have evaluated the performance of BatchHL<jats:inline-formula><jats:alternatives><jats:tex-math>$$^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow\/>\n                    <mml:mo>+<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on 15 real-world networks. The results show that BatchHL<jats:inline-formula><jats:alternatives><jats:tex-math>$$^+$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow\/>\n                    <mml:mo>+<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> significantly outperforms the state-of-the-art methods with up to 3 orders of magnitude faster in reflecting updates of rapidly changing graphs for distance queries.<\/jats:p>","DOI":"10.1007\/s00778-023-00799-9","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T17:01:46Z","timestamp":1686157306000},"page":"101-129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["BatchHL$$^{+}$$: batch dynamic labelling for distance queries on large-scale networks"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1239-2107","authenticated-orcid":false,"given":"Muhammad","family":"Farhan","sequence":"first","affiliation":[]},{"given":"Henning","family":"Koehler","sequence":"additional","affiliation":[]},{"given":"Qing","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"799_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Proceedings of the 20th Annual European Conference on Algorithms, ESA\u201912, pp. 24\u201335. Springer-Verlag, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_4","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"799_CR2","doi-asserted-by":"publisher","unstructured":"Acar, U.A., Anderson, D., Blelloch, G.E., Dhulipala, L.: Parallel batch-dynamic graph connectivity. In: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201919, pp. 381\u2013392. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3323165.3323196","DOI":"10.1145\/3323165.3323196"},{"key":"799_CR3","doi-asserted-by":"crossref","unstructured":"Acar, U.A., Anderson, D., Blelloch, G.E., Dhulipala, L., Westrick, S.: Parallel batch-dynamic trees via change propagation. In: ESA (2020)","DOI":"10.1145\/3323165.3323196"},{"key":"799_CR4","doi-asserted-by":"publisher","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201913, pp. 349\u2013360. Association for Computing Machinery, New York, NY, USA (2013). https:\/\/doi.org\/10.1145\/2463676.2465315","DOI":"10.1145\/2463676.2465315"},{"key":"799_CR5","doi-asserted-by":"publisher","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In: Proceedings of the 23rd International Conference on World Wide Web, WWW \u201914, pp. 237\u2013248. Association for Computing Machinery, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2566486.2568007","DOI":"10.1145\/2566486.2568007"},{"key":"799_CR6","doi-asserted-by":"publisher","unstructured":"Akiba, T., Sommer, C., Kawarabayashi, K.i.: Shortest-path queries for complex networks: Exploiting low tree-width outside the core. In: Proceedings of the 15th International Conference on Extending Database Technology, EDBT \u201912, pp. 144\u2013155. Association for Computing Machinery, New York, NY, USA (2012). https:\/\/doi.org\/10.1145\/2247596.2247614","DOI":"10.1145\/2247596.2247614"},{"key":"799_CR7","doi-asserted-by":"publisher","unstructured":"Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group formation in large social networks: Membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 44\u201354 (2006). https:\/\/doi.org\/10.1145\/1150402.1150412","DOI":"10.1145\/1150402.1150412"},{"issue":"4\u20135","key":"799_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.physrep.2005.10.009","volume":"424","author":"S Boccaletti","year":"2006","unstructured":"Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.U.: Complex networks: structure and dynamics. Phys. Rep. 424(4\u20135), 175\u2013308 (2006). https:\/\/doi.org\/10.1016\/j.physrep.2005.10.009","journal-title":"Phys. Rep."},{"key":"799_CR9","doi-asserted-by":"publisher","unstructured":"Boldi, P., Vigna, S.: The webgraph framework I: compression techniques. In: Proceedings of the 13th International Conference on World Wide Web, WWW, pp. 595\u2013602 (2004). https:\/\/doi.org\/10.1145\/988672.988752","DOI":"10.1145\/988672.988752"},{"issue":"6","key":"799_CR10","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/s00778-012-0274-x","volume":"21","author":"L Chang","year":"2012","unstructured":"Chang, L., Yu, J.X., Qin, L., Cheng, H., Qiao, M.: The exact distance to destination in undirected world. VLDB J. 21(6), 869\u2013888 (2012). https:\/\/doi.org\/10.1007\/s00778-012-0274-x","journal-title":"VLDB J."},{"key":"799_CR11","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201902, pp. 937\u2013946. Society for Industrial and Applied Mathematics, USA (2002)"},{"key":"799_CR12","doi-asserted-by":"publisher","DOI":"10.1145\/3299901","author":"G D\u2019angelo","year":"2019","unstructured":"D\u2019angelo, G., D\u2019emidio, M., Frigioni, D.: Fully dynamic 2-hop cover labeling. J. Exp. Algorithmics (2019). https:\/\/doi.org\/10.1145\/3299901","journal-title":"J. Exp. Algorithmics"},{"key":"799_CR13","doi-asserted-by":"publisher","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Robust distance queries on massive networks. In: European Symposium on Algorithms, pp. 321\u2013333. Berlin (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_27","DOI":"10.1007\/978-3-662-44777-2_27"},{"key":"799_CR14","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Durfee, D., Kulkarni, J., Peng, R., Sawlani, S., Sun, X.: Parallel batch-dynamic graphs: Algorithms and lower bounds. In: SODA, pp. 1300\u20131319 (2020)","DOI":"10.1137\/1.9781611975994.79"},{"key":"799_CR15","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Liu, Q.C., Shun, J., Yu, S.: Parallel batch-dynamic k-clique counting. In: Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 129\u2013143 (2021)","DOI":"10.1137\/1.9781611976489.10"},{"key":"799_CR16","unstructured":"Farhan, M., Wang, Q.: Efficient maintenance of distance labelling for incremental updates in large dynamic graphs. In: 24th International Conference on Extending Database Technology EDBT (2021)"},{"key":"799_CR17","doi-asserted-by":"publisher","unstructured":"Farhan, M., Wang, Q.: Efficient maintenance of highway cover labelling for distance queries on large dynamic graphs. World Wide Web, pp. 1\u201326 (2023). https:\/\/doi.org\/10.1007\/s11280-023-01146-2","DOI":"10.1007\/s11280-023-01146-2"},{"key":"799_CR18","doi-asserted-by":"publisher","unstructured":"Farhan, M., Wang, Q., Koehler, H.: Batchhl: Answering distance queries on batch-dynamic networks at scale. SIGMOD \u201922, pp. 2020\u20132033. Association for Computing Machinery, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3514221.3517883","DOI":"10.1145\/3514221.3517883"},{"key":"799_CR19","unstructured":"Farhan, M., Wang, Q., Lin, Y., Mckay, B.: A highly scalable labelling approach for exact distance queries in complex networks. In: EDBT (2018)"},{"key":"799_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00707-z","author":"M Farhan","year":"2021","unstructured":"Farhan, M., Wang, Q., Lin, Y., McKay, B.: Fast fully dynamic labelling for distance queries. VLDB J. (2021). https:\/\/doi.org\/10.1007\/s00778-021-00707-z","journal-title":"VLDB J."},{"key":"799_CR21","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: SODA, vol.\u00a05, pp. 745\u2013754. Citeseer (2005)"},{"issue":"6","key":"799_CR22","doi-asserted-by":"publisher","first-page":"457","DOI":"10.14778\/2536336.2536346","volume":"6","author":"AWC Fu","year":"2013","unstructured":"Fu, A.W.C., Wu, H., Cheng, J., Wong, R.C.W.: Is-label: an independent-set based labeling scheme for point-to-point distance querying. Proc. VLDB Endow 6(6), 457\u2013468 (2013). https:\/\/doi.org\/10.14778\/2536336.2536346","journal-title":"Proc. VLDB Endow"},{"key":"799_CR23","doi-asserted-by":"publisher","unstructured":"Hayashi, T., Akiba, T., Kawarabayashi, K.I.: Fully dynamic shortest-path distance query acceleration on massive networks. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, CIKM \u201916, pp. 1533\u20131542. Association for Computing Machinery, New York (2016). https:\/\/doi.org\/10.1145\/2983323.2983731","DOI":"10.1145\/2983323.2983731"},{"key":"799_CR24","doi-asserted-by":"publisher","unstructured":"Jin, R., Ruan, N., Xiang, Y., Lee, V.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201912, pp. 445\u2013456. Association for Computing Machinery, New York (2012). https:\/\/doi.org\/10.1145\/2213836.2213887","DOI":"10.1145\/2213836.2213887"},{"key":"799_CR25","doi-asserted-by":"publisher","unstructured":"Kunegis, J.: Konect: The Koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, WWW, pp. 1343\u20131350 (2013). https:\/\/doi.org\/10.1145\/2487788.2488173","DOI":"10.1145\/2487788.2488173"},{"key":"799_CR26","doi-asserted-by":"publisher","DOI":"10.1145\/2898361","author":"J Leskovec","year":"2016","unstructured":"Leskovec, J., Sosi\u010d, R.: Snap: a general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (2016). https:\/\/doi.org\/10.1145\/2898361","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"799_CR27","doi-asserted-by":"publisher","unstructured":"Li, W., Qiao, M., Qin, L., Zhang, Y., Chang, L., Lin, X.: Scaling distance labeling on small-world networks. In: Proceedings of the 2019 International Conference on Management of Data, SIGMOD \u201919, pp. 1060\u20131077. Association for Computing Machinery, New York (2019). https:\/\/doi.org\/10.1145\/3299869.3319877","DOI":"10.1145\/3299869.3319877"},{"issue":"4","key":"799_CR28","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/3186728.3164141","volume":"11","author":"Y Li","year":"2017","unstructured":"Li, Y., U, L.H., Yiu, M.L., Kou, N.M.: An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow. 11(4), 445\u2013457 (2017). https:\/\/doi.org\/10.1145\/3186728.3164141","journal-title":"Proc. VLDB Endow."},{"key":"799_CR29","doi-asserted-by":"publisher","unstructured":"Liu, Q.C., Shi, J., Yu, S., Dhulipala, L., Shun, J.: Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. In: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201922, pp. 191\u2013204. Association for Computing Machinery, New York (2022). https:\/\/doi.org\/10.1145\/3490148.3538569","DOI":"10.1145\/3490148.3538569"},{"issue":"1","key":"799_CR30","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/2627692.2627694","journal-title":"SIGMOD Rec."},{"issue":"5","key":"799_CR31","doi-asserted-by":"publisher","first-page":"602","DOI":"10.14778\/3377369.3377371","volume":"13","author":"D Ouyang","year":"2020","unstructured":"Ouyang, D., Yuan, L., Qin, L., Chang, L., Zhang, Y., Lin, X.: Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proc. VLDB Endow. 13(5), 602\u2013615 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"799_CR32","doi-asserted-by":"publisher","unstructured":"Pacaci, A., Bonifati, A., \u00d6zsu, M.T.: Regular path query evaluation on streaming graphs. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201920, pp. 1415\u20131430. Association for Computing Machinery, New York (2020). https:\/\/doi.org\/10.1145\/3318464.3389733","DOI":"10.1145\/3318464.3389733"},{"key":"799_CR33","first-page":"127","volume":"6","author":"I Pohl","year":"1971","unstructured":"Pohl, I.: Bi-derectional search. Mach. Intell. 6, 127\u2013140 (1971)","journal-title":"Mach. Intell."},{"key":"799_CR34","doi-asserted-by":"publisher","unstructured":"Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM \u201909, pp. 867\u2013876. Association for Computing Machinery, New York (2009). https:\/\/doi.org\/10.1145\/1645953.1646063","DOI":"10.1145\/1645953.1646063"},{"issue":"5","key":"799_CR35","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/s11280-016-0421-1","volume":"20","author":"Y Qin","year":"2017","unstructured":"Qin, Y., Sheng, Q.Z., Falkner, N.J., Yao, L., Parkinson, S.: Efficient computation of distance labeling for decremental updates in large dynamic graphs. World Wide Web 20(5), 915\u2013937 (2017). https:\/\/doi.org\/10.1007\/s11280-016-0421-1","journal-title":"World Wide Web"},{"key":"799_CR36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"RE Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (1983). https:\/\/doi.org\/10.1137\/1.9781611970265"},{"key":"799_CR37","doi-asserted-by":"publisher","unstructured":"Ukkonen, A., Castillo, C., Donato, D., Gionis, A.: Searching the wikipedia with contextual information. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM, pp. 1351\u20131352 (2008). https:\/\/doi.org\/10.1145\/1458082.1458274","DOI":"10.1145\/1458082.1458274"},{"key":"799_CR38","doi-asserted-by":"publisher","unstructured":"Vieira, M.V., Fonseca, B.M., Damazio, R., Golgher, P.B., Reis, D.d.C., Ribeiro-Neto, B.: Efficient search ranking in social networks. In: Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management, CIKM, pp. 563\u2013572 (2007). https:\/\/doi.org\/10.1145\/1321440.1321520","DOI":"10.1145\/1321440.1321520"},{"key":"799_CR39","doi-asserted-by":"publisher","unstructured":"Wang, Y., Wang, Q., Koehler, H., Lin, Y.: Query-by-sketch: Scaling shortest path graph queries on very large networks. In: Proceedings of the 2021 International Conference on Management of Data, SIGMOD \u201921, pp. 1946\u20131958. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3448016.3452826","DOI":"10.1145\/3448016.3452826"},{"key":"799_CR40","doi-asserted-by":"publisher","unstructured":"Wei, F.: Tedi: Efficient shortest path query answering on graphs. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201910, pp. 99\u2013110. Association for Computing Machinery, New York (2010). https:\/\/doi.org\/10.1145\/1807167.1807181","DOI":"10.1145\/1807167.1807181"},{"key":"799_CR41","doi-asserted-by":"publisher","unstructured":"Yu, M., Qin, L., Zhang, Y., Zhang, W., Lin, X.: Dptl+: Efficient parallel triangle listing on batch-dynamic graphs. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1332\u20131343 (2021). https:\/\/doi.org\/10.1109\/ICDE51399.2021.00119","DOI":"10.1109\/ICDE51399.2021.00119"},{"key":"799_CR42","doi-asserted-by":"publisher","unstructured":"Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient 2-hop labeling maintenance in dynamic small-world networks. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 133\u2013144 (2021). https:\/\/doi.org\/10.1109\/ICDE51399.2021.00019","DOI":"10.1109\/ICDE51399.2021.00019"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00799-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00799-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00799-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T19:06:20Z","timestamp":1705604780000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00799-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["799"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00799-9","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"18 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}