{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:28:37Z","timestamp":1756463317805,"version":"3.40.3"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem that is work-efficient, supports batches of updates, runs in polylogarithmic depth, and uses only linear total space. The existing algorithms for the problem either use super-linear space, do not come with strong theoretical bounds, or are not parallel.<\/jats:p>\n          <jats:p>\n            On the empirical side, we provide the first implementation of the\n            <jats:italic>cluster forest algorithm<\/jats:italic>\n            , the first linear-space and polylogarithmic update time algorithm for dynamic connectivity. Experimentally, we find that our algorithm uses up to 19.7\u00d7 less space and is up to 6.2\u00d7 faster than the level-set algorithm of Holm, de Lichten-berg, and Thorup, arguably the most widely-implemented dynamic connectivity algorithm with strong theoretical guarantees.\n          <\/jats:p>","DOI":"10.14778\/3712221.3712250","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"889-901","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Towards Scalable and Practical Batch-Dynamic Connectivity"],"prefix":"10.14778","volume":"18","author":[{"given":"Quinten","family":"De Man","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Karczmarz","sequence":"additional","affiliation":[{"name":"University of Warsaw &amp; IDEAS NCBR"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"\u0141\u0105cki","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongqi","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19)","author":"Acar Umut A.","year":"2019","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19). ACM."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"N. S. Arora R. D. Blumofe and C. G. Plaxton. 2001. Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS) 34 2 (01 Apr 2001).","DOI":"10.1007\/s002240011004"},{"key":"e_1_2_1_3_1","volume-title":"abseil.io. abseil.io. Online","author":"Authors Abseil","year":"2024","unstructured":"Abseil C++ Authors. [n.d.]. abseil.io. abseil.io. Online; accessed September 2024."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_5_1","volume-title":"Practice of streaming processing of dynamic graphs: Concepts, models, and systems. arXiv preprint arXiv:1912.12740","author":"Besta Maciej","year":"2019","unstructured":"Maciej Besta, Marc Fischer, Vasiliki Kalavri, Michael Kapralov, and Torsten Hoefler. 2019. Practice of streaming processing of dynamic graphs: Concepts, models, and systems. arXiv preprint arXiv:1912.12740 (2019)."},{"key":"e_1_2_1_6_1","article-title":"Joinable Parallel Balanced Binary Trees","volume":"9","author":"Blelloch Guy","year":"2022","unstructured":"Guy Blelloch, Daniel Ferizovic, and Yihan Sun. 2022. Joinable Parallel Balanced Binary Trees. ACM Trans. Parallel Comput. 9, 2, Article 7 (apr 2022), 41 pages.","journal-title":"ACM Trans. Parallel Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th International Conference on World Wide Web","author":"Boldi P.","unstructured":"P. Boldi and S. Vigna. 2004. The webgraph framework I: compression techniques. In Proceedings of the 13th International Conference on World Wide Web (New York, NY, USA) (WWW '04). Association for Computing Machinery, New York, NY, USA, 595--602."},{"key":"e_1_2_1_10_1","volume-title":"R-MAT: A Recursive Model for Graph Mining","author":"Chakrabarti Deepayan","year":"2004","unstructured":"Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004. R-MAT: A Recursive Model for Graph Mining.. In SDM, Michael W. Berry, Umeshwar Dayal, Chandrika Kamath, and David B. Skillicorn (Eds.). SIAM, 442--446. http:\/\/dblp.uni-trier.de\/db\/conf\/sdm\/sdm2004.html#ChakrabartiZF04"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.41"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.062116"},{"key":"e_1_2_1_15_1","volume-title":"Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 393--404","author":"Dhulipala Laxman","year":"2018","unstructured":"Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 393--404."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.79"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436923"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_19_1","volume-title":"Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical","author":"Fonollosa Jordi","year":"2015","unstructured":"Jordi Fonollosa, Sadique Sheik, Ram\u00f3n Huerta, and Santiago Marco. 2015. Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical (2015)."},{"key":"e_1_2_1_20_1","volume-title":"2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 998--1007","author":"Gabert Kasimir","year":"2021","unstructured":"Kasimir Gabert, Ali Pinar, and \u00dcmit V \u00c7ataly\u00fcrek. 2021. Shared-memory scalable k-core maintenance on dynamic graphs and hypergraphs. In 2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 998--1007."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064050"},{"key":"e_1_2_1_22_1","volume-title":"Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60","author":"Gu Yan","year":"2022","unstructured":"Yan Gu, Zachary Napier, and Yihan Sun. 2022. Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555806"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_27_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 510--520","author":"Huang Shang-En","year":"2017","unstructured":"Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. 2017. Fully Dynamic Connectivity in O(Log N(Log Log N)2) Amortized Expected Time. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 510--520."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945398"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_2_1_30_1","volume-title":"Faster Worst Case Deterministic Dynamic Connectivity. In European Symposium on Algorithms (ESA).","author":"Kejlberg-Rasmussen Casper","year":"2016","unstructured":"Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. 2016. Faster Worst Case Deterministic Dynamic Connectivity. In European Symposium on Algorithms (ESA)."},{"key":"e_1_2_1_31_1","volume-title":"International Conference on the Applications of Digital Information and Web Technologies (ICADIWT). IEEE, 232--238","author":"Khan Kamran","year":"2014","unstructured":"Kamran Khan, Saif Ur Rehman, Kamran Aziz, Simon Fong, and Sababady Sarasvady. 2014. DBSCAN: Past, present and future. In International Conference on the Applications of Digital Information and Web Technologies (ICADIWT). IEEE, 232--238."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_33_1","volume-title":"Graphs over time: densification laws, shrinking diameters and possible explanations (KDD '05)","author":"Leskovec Jure","unstructured":"Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations (KDD '05). Association for Computing Machinery, New York, NY, USA, 177--187."},{"key":"e_1_2_1_34_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_2_1_36_1","unstructured":"Quinten De Man Laxman Dhulipala Adam Karczmarz Jakub \u0141\u0105cki Julian Shun and Zhongqi Wang. 2024. Towards Scalable and Practical Batch-Dynamic Connectivity. arXiv:2411.11781 [cs.DS] https:\/\/arxiv.org\/abs\/2411.11781"},{"key":"e_1_2_1_38_1","volume-title":"Online Level-wise Hierarchical Clustering. In ACM Conference on Knowledge Discovery and Data Mining (KDD). 1733--1745","author":"Monath Nicholas","year":"2023","unstructured":"Nicholas Monath, Manzil Zaheer, and Andrew McCallum. 2023. Online Level-wise Hierarchical Clustering. In ACM Conference on Knowledge Discovery and Data Mining (KDD). 1733--1745."},{"key":"e_1_2_1_39_1","volume-title":"ACM Symposium on Theory of Computing (STOC). ACM.","author":"Nanongkai Danupon","year":"2017","unstructured":"Danupon Nanongkai and Thatchaphol Saranurak. 2017. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1\/2 - \u03b5)-time. In ACM Symposium on Theory of Computing (STOC). ACM."},{"key":"e_1_2_1_40_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org . https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452828"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1033"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing. 343--350","author":"Thorup Mikkel","year":"2000","unstructured":"Mikkel Thorup. 2000. Near-optimal fully-dynamic graph connectivity. In Proceedings of the ACM Symposium on Theory of Computing. 343--350."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). 92--106","author":"Tseng Thomas","year":"2019","unstructured":"Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019. Batch-Parallel Euler Tour Trees. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). 92--106."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.126"},{"key":"e_1_2_1_48_1","volume-title":"ACM Symposium on Theory of Computing (STOC). ACM.","author":"Wulff-Nilsen Christian","year":"2017","unstructured":"Christian Wulff-Nilsen. 2017. Fully-dynamic minimum spanning forest with improved worst-case update time. In ACM Symposium on Theory of Computing (STOC). ACM."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD '17)","author":"Yin Hao","unstructured":"Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local Higher-Order Graph Clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD '17). Association for Computing Machinery, New York, NY, USA, 555--564."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:34:47Z","timestamp":1744050887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712250"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712250","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}