{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:00:38Z","timestamp":1770278438222,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DARPA","award":["HR0011-18-3-0007"],"award-info":[{"award-number":["HR0011-18-3-0007"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1845763,CCF-2103483"],"award-info":[{"award-number":["CCF-1845763,CCF-2103483"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["E-SC0018947"],"award-info":[{"award-number":["E-SC0018947"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538584","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"233-245","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering"],"prefix":"10.1145","author":[{"given":"Tom","family":"Tseng","sequence":"first","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323196"},{"key":"e_1_3_2_1_3_1","volume-title":"28th Annual European Symposium on Algorithms","volume":"173","author":"Acar Umut A.","year":"2020","unstructured":"Umut A. Acar , Daniel Anderson , Guy E. Blelloch , Laxman Dhulipala , and Sam Westrick . 2020 . Parallel Batch-Dynamic Trees via Change Propagation . In 28th Annual European Symposium on Algorithms , Vol. 173 . 2:1--2:23. Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms, Vol. 173. 2:1--2:23."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms","volume":"531","author":"Acar Umit A","year":"2004","unstructured":"Umit A Acar , Guy E Blelloch , Robert Harper , Jorge L Vittes , and Shan Leung Maverick Woo . 2004 . Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence . In Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms , Vol. 531 . 540. Umit A Acar, Guy E Blelloch, Robert Harper, Jorge L Vittes, and Shan Leung Maverick Woo. 2004. Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence. In Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, Vol. 531. 540."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Stephen Alstrup Jacob Holm Kristian de Lichtenberg and Mikkel Thorup. 1997. Minimizing Diameters of Dynamic Trees. In International Colloquium on Automata Languages and Programming. 270--280.  Stephen Alstrup Jacob Holm Kristian de Lichtenberg and Mikkel Thorup. 1997. Minimizing Diameters of Dynamic Trees. In International Colloquium on Automata Languages and Programming. 270--280.","DOI":"10.1007\/3-540-63165-8_184"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400241"},{"key":"e_1_3_2_1_7_1","volume-title":"Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni.","author":"Bateni MohammadHossein","year":"2017","unstructured":"MohammadHossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , Mohammad- Taghi Hajiaghayi , Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. 2017 . Affinity Clustering : Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems . 6864--6874. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, Mohammad- Taghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems. 6864--6874."},{"key":"e_1_3_2_1_8_1","volume-title":"Construction d'une classification ascendante hi\u00e9rarchique par la recherche en cha\u00eene des voisins r\u00e9ciproques. Cahiers de l'analyse des donn\u00e9es 7, 2","author":"Benz\u00e9cri J.-P.","year":"1982","unstructured":"J.-P. Benz\u00e9cri . 1982. Construction d'une classification ascendante hi\u00e9rarchique par la recherche en cha\u00eene des voisins r\u00e9ciproques. Cahiers de l'analyse des donn\u00e9es 7, 2 ( 1982 ), 209--218. J.-P. Benz\u00e9cri. 1982. Construction d'une classification ascendante hi\u00e9rarchique par la recherche en cha\u00eene des voisins r\u00e9ciproques. Cahiers de l'analyse des donn\u00e9es 7, 2 (1982), 209--218."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_3_2_1_11_1","volume-title":"The Complexity of Satisfiability of Small Depth Circuits. In International Workshop on Parameterized and Exact Computation. Springer, 75--85","author":"Calabro Chris","year":"2009","unstructured":"Chris Calabro , Russell Impagliazzo , and Ramamohan Paturi . 2009 . The Complexity of Satisfiability of Small Depth Circuits. In International Workshop on Parameterized and Exact Computation. Springer, 75--85 . Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. 2009. The Complexity of Satisfiability of Small Depth Circuits. In International Workshop on Parameterized and Exact Computation. Springer, 75--85."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970343912X"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321386"},{"key":"e_1_3_2_1_15_1","unstructured":"Sajal K Das and Paolo Ferragina. 1995. Parallel Dynamic Algorithms for Minimum Spanning Trees. (1995).  Sajal K Das and Paolo Ferragina. 1995. Parallel Dynamic Algorithms for Minimum Spanning Trees. (1995)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897527"},{"key":"e_1_3_2_1_17_1","volume-title":"Lecture Notes on Skip Lists. https:\/\/courses.csail.mit.edu\/6.046\/spring04\/handouts\/skiplists.pdf. [Online","author":"Demaine Erik","year":"2022","unstructured":"Erik Demaine . 2004. Lecture Notes on Skip Lists. https:\/\/courses.csail.mit.edu\/6.046\/spring04\/handouts\/skiplists.pdf. [Online ; accessed 08- January - 2022 ]. Erik Demaine. 2004. Lecture Notes on Skip Lists. https:\/\/courses.csail.mit.edu\/6.046\/spring04\/handouts\/skiplists.pdf. [Online; accessed 08-January-2022]."},{"key":"e_1_3_2_1_18_1","volume-title":"Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time. In International Conference on Machine Learning. 2676--2686","author":"Dhulipala Laxman","year":"2021","unstructured":"Laxman Dhulipala , David Eisenstat , Vahab Mirrokni , and Jessica Shi . 2021 . Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time. In International Conference on Machine Learning. 2676--2686 . Laxman Dhulipala, David Eisenstat, Vahab Mirrokni, and Jessica Shi. 2021. Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time. In International Conference on Machine Learning. 2676--2686."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58184-7_143"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010032"},{"key":"e_1_3_2_1_22_1","volume-title":"On a class of (2) problems in computational geometry. Computational geometry 5, 3","author":"Gajentaan Anka","year":"1995","unstructured":"Anka Gajentaan and Mark H Overmars . 1995. On a class of (2) problems in computational geometry. Computational geometry 5, 3 ( 1995 ), 165--185. Anka Gajentaan and Mark H Overmars. 1995. On a class of (2) problems in computational geometry. Computational geometry 5, 3 (1995), 165--185."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346439"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. 24--34","author":"Gu Yan","unstructured":"Yan Gu , Julian Shun , Yihan Sun , and Guy E. Blelloch . 2015. A Top-Down Parallel Semisort . In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. 24--34 . Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A Top-Down Parallel Semisort. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. 24--34."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9157-2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_62"},{"key":"e_1_3_2_1_31_1","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1 Joseph","unstructured":"Joseph J\u00e1J\u00e1 . 1992. An Introduction to Parallel Algorithms . Addison-Wesley . Joseph J\u00e1J\u00e1. 1992. An Introduction to Parallel Algorithms. Addison-Wesley."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098079"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210403"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-46150-8_5"},{"key":"e_1_3_2_1_36_1","volume-title":"Online hierarchical clustering approximations. arXiv preprint arXiv:1909.09667","author":"Menon Aditya Krishna","year":"2019","unstructured":"Aditya Krishna Menon , Anand Rajagopalan , Baris Sumengen , Gui Citovsky , Qin Cao , and Sanjiv Kumar . 2019. Online hierarchical clustering approximations. arXiv preprint arXiv:1909.09667 ( 2019 ). Aditya Krishna Menon, Anand Rajagopalan, Baris Sumengen, Gui Citovsky, Qin Cao, and Sanjiv Kumar. 2019. Online hierarchical clustering approximations. arXiv preprint arXiv:1909.09667 (2019)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330929"},{"key":"e_1_3_2_1_39_1","volume-title":"Wang","author":"Moseley Benjamin","year":"2017","unstructured":"Benjamin Moseley and Joshua R . Wang . 2017 . Approximation Bounds for Hierarchical Clustering: Average Linkage , Bisecting K-means, and Local Search. In Advances in Neural Information Processing Systems . 3094--3103. Benjamin Moseley and Joshua R. Wang. 2017. Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search. In Advances in Neural Information Processing Systems. 3094--3103."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228509"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700371065"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1993.262898"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the Meeting on Algorithm Engineering and Experiments. 92--106","author":"Tseng Thomas","unstructured":"Thomas Tseng , Laxman Dhulipala , and Guy E. Blelloch . 2019. Batch-Parallel Euler Tour Trees . In Proceedings of the Meeting on Algorithm Engineering and Experiments. 92--106 . Thomas Tseng, Laxman Dhulipala, and Guy E. Blelloch. 2019. Batch-Parallel Euler Tour Trees. In Proceedings of the Meeting on Algorithm Engineering and Experiments. 92--106."},{"key":"e_1_3_2_1_49_1","volume-title":"Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. arXiv preprint arXiv:2205.04956","author":"Tseng Tom","year":"2022","unstructured":"Tom Tseng , Laxman Dhulipala , and Julian Shun . 2022. Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. arXiv preprint arXiv:2205.04956 ( 2022 ). Tom Tseng, Laxman Dhulipala, and Julian Shun. 2022. Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. arXiv preprint arXiv:2205.04956 (2022)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321601"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Philadelphia PA USA","acronym":"SPAA '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538584","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":49,"alternative-id":["10.1145\/3490148.3538584","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538584","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}