{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:46Z","timestamp":1777954606671,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100006374","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2403235 and CNS- 2317194"],"award-info":[{"award-number":["CCF-2403235 and CNS- 2317194"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743315","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"397-412","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1321-9590","authenticated-orcid":false,"given":"Quinten","family":"De Man","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0685-064X","authenticated-orcid":false,"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6573-9445","authenticated-orcid":false,"given":"Kishen N.","family":"Gowda","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM.","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 ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM."},{"key":"e_1_3_2_1_2_1","volume-title":"European Symposium on Algorithms (ESA).","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 European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_3_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Acar Umut A.","year":"2004","unstructured":"Umut 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 ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX\/ANALCO).","author":"Acar Umut A.","unstructured":"Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. 2005. An Experimental Analysis of Change Propagation in Dynamic Trees. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX\/ANALCO)."},{"key":"e_1_3_2_1_5_1","unstructured":"Daniel Anderson. 2023. Parallel Batch-Dynamic Algorithms Dynamic Trees Graphs and Self-Adjusting Computation. Ph.D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_1_6_1","volume-title":"Blelloch","author":"Anderson Daniel","year":"2023","unstructured":"Daniel Anderson and Guy E. Blelloch. 2023. Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span. arXiv:2306.08786 [cs.DS]"},{"key":"e_1_3_2_1_7_1","volume-title":"Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Anderson Daniel","unstructured":"Daniel Anderson and Guy E. Blelloch. 2024. Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_8_1","unstructured":"Dalya Baron. 2019. Machine Learning in Astronomy: a practical overview. arXiv:1904.07248 [astro-ph.IM]"},{"key":"e_1_3_2_1_9_1","volume-title":"Intl. Colloq. on Automata, Languages and Programming (ICALP).","author":"Bateni MohammadHossein","year":"2024","unstructured":"MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub Lacki. 2024. It's Hard to HAC Average Linkage!. In Intl. Colloq. on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_10_1","volume-title":"Latin American Symposium on Theoretical Informatics (LATIN).","author":"Michael","unstructured":"Michael A. Bender and Martin Farach-Colton. 2000. The LCA problem revisited. In Latin American Symposium on Theoretical Informatics (LATIN)."},{"key":"e_1_3_2_1_11_1","volume-title":"Amortized Rigidness in Dynamic Cartesian Trees. In Symposium on Theoretical Aspects of Computer Science (STACS).","author":"Bialynicka-Birula Iwona","year":"2006","unstructured":"Iwona Bialynicka-Birula and Roberto Grossi. 2006. Amortized Rigidness in Dynamic Cartesian Trees. In Symposium on Theoretical Aspects of Computer Science (STACS)."},{"key":"e_1_3_2_1_12_1","volume-title":"Optimal Parallel Algorithms in the Binary-Forking Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal Parallel Algorithms in the Binary-Forking Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_13_1","volume-title":"Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD) 10, 1","author":"Campello Ricardo JGB","year":"2015","unstructured":"Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, and J\u00f6rg Sander. 2015. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD) 10, 1 (2015)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB) 18","author":"Man Quinten De","year":"2024","unstructured":"Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub \u0141\u0105cki, Julian Shun, and Zhongqi Wang. 2024. Towards Scalable and Practical Batch-Dynamic Connectivity. Proceedings of the VLDB Endowment (PVLDB) 18, 3 (2024)."},{"key":"e_1_3_2_1_16_1","volume-title":"On Cartesian Trees and Range Minimum Queries. Algorithmica 68, 3","author":"Demaine Erik D.","year":"2014","unstructured":"Erik D. Demaine, Gad M. Landau, and Oren Weimann. 2014. On Cartesian Trees and Range Minimum Queries. Algorithmica 68, 3 (2014)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_1_19_1","volume-title":"Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Dhulipala Laxman","year":"2024","unstructured":"Laxman Dhulipala, Xiaojun Dong, Kishen N. Gowda, and Yan Gu. 2024. Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_20_1","volume-title":"Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020. Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_21_1","volume-title":"International Conference on Machine Learning (ICML). PMLR.","author":"Dhulipala Laxman","year":"2021","unstructured":"Laxman Dhulipala, David Eisenstat, Jakub \u0141\u0105cki, Vahab Mirrokni, and Jessica Shi. 2021. Hierarchical agglomerative graph clustering in nearly-linear time. In International Conference on Machine Learning (ICML). PMLR."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Laxman Dhulipala David Eisenstat Jakub \u0141\u0105cki Vahab Mirrokni and Jessica Shi. 2022. Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth. In Neural Information Processing Systems (NeurIPS).","DOI":"10.52202\/068431-1666"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617341"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0074180900129043"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Molly Gasperini Andrew J Hill Jos\u00e9 L McFaline-Figueroa Beth Martin Seungsoo Kim Melissa D Zhang Dana Jackson Anh Leith Jacob Schreiber William S Noble et al. 2019. A genome-wide framework for mapping gene regulation via cellular genetic screens. Cell 176 1 (2019).","DOI":"10.1016\/j.cell.2019.02.027"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2829724"},{"key":"e_1_3_2_1_29_1","series-title":"Series C (Applied Statistics) 18, 1","volume-title":"Minimum Spanning Trees and Single Linkage Cluster Analysis. Journal of the Royal Statistical Society","author":"Gower J. C.","year":"1969","unstructured":"J. C. Gower and G. J. S. Ross. 1969. Minimum Spanning Trees and Single Linkage Cluster Analysis. Journal of the Royal Statistical Society. Series C (Applied Statistics) 18, 1 (1969)."},{"key":"e_1_3_2_1_30_1","volume-title":"Efficient tree construction for multiscale image representation and processing. Journal of Real-Time Image Processing 16","author":"Havel Ji\u0159\u00ed","year":"2019","unstructured":"Ji\u0159\u00ed Havel, Fran\u00e7ois Merciol, and S\u00e9bastien Lef\u00e8vre. 2019. Efficient tree construction for multiscale image representation and processing. Journal of Real-Time Image Processing 16 (2019)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1037\/0893-3200.19.1.121"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_1_34_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 Longman Publishing Co., Inc., USA."},{"key":"e_1_3_2_1_35_1","volume-title":"Interactive Tree Of Life (iTOL): an online tool for phylogenetic tree display and annotation. Bioinformatics 23, 1","author":"Letunic Ivica","year":"2007","unstructured":"Ivica Letunic and Peer Bork. 2007. Interactive Tree Of Life (iTOL): an online tool for phylogenetic tree display and annotation. Bioinformatics 23, 1 (2007)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709712"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.43"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599455"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-43412-9_42"},{"key":"e_1_3_2_1_42_1","volume-title":"The alpha-tree algorithm. JRC Scientific and Policy Report","author":"Ouzounis Georgios K","year":"2012","unstructured":"Georgios K Ouzounis and Pierre Soille. 2012. The alpha-tree algorithm. JRC Scientific and Policy Report (2012)."},{"key":"e_1_3_2_1_43_1","volume-title":"ACM Symposium on Theory of Computing (STOC).","author":"Patra\u015fcu Mihai","unstructured":"Mihai Patra\u015fcu and Erik D. Demaine. 2004. Lower bounds for dynamic connectivity. In ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_44_1","volume-title":"PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU. In International Conference on Parallel Processing (ICPP).","author":"Sao Piyush","year":"2024","unstructured":"Piyush Sao, Andrey Prokopenko, and Damien Lebrun-Grandie. 2024. PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU. In International Conference on Parallel Processing (ICPP)."},{"key":"e_1_3_2_1_45_1","article-title":"A Simple Parallel Cartesian Tree Algorithm and Its Application to Parallel Suffix Tree Construction","volume":"1","author":"Shun Julian","year":"2014","unstructured":"Julian Shun and Guy E. Blelloch. 2014. A Simple Parallel Cartesian Tree Algorithm and Its Application to Parallel Suffix Tree Construction. ACM Transactions on Parallel Computing (TOPC) 1, 1 (2014).","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_3_2_1_46_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.1137\/1.9781611975499.8"},{"key":"e_1_3_2_1_48_1","volume-title":"Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","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. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_49_1","volume-title":"A unifying look at data structures. Commun. ACM 23, 4","author":"Vuillemin Jean","year":"1980","unstructured":"Jean Vuillemin. 1980. A unifying look at data structures. Commun. ACM 23, 4 (1980)."},{"key":"e_1_3_2_1_50_1","volume-title":"Theoretically-Efficient and Practical Parallel DBSCAN. In ACM SIGMOD International Conference on Management of Data (SIGMOD).","author":"Wang Yiqiu","year":"2020","unstructured":"Yiqiu Wang, Yan Gu, and Julian Shun. 2020. Theoretically-Efficient and Practical Parallel DBSCAN. In ACM SIGMOD International Conference on Management of Data (SIGMOD)."},{"key":"e_1_3_2_1_51_1","volume-title":"Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering. In ACM SIGMOD International Conference on Management of Data (SIGMOD).","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering. In ACM SIGMOD International Conference on Management of Data (SIGMOD)."},{"key":"e_1_3_2_1_52_1","unstructured":"Yiqiu Wang Shangdi Yu Yan Gu and Julian Shun. 2021. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. arXiv:2010.02379 [cs.DS]"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"},{"key":"e_1_3_2_1_54_1","article-title":"Should Tables Be Sorted","volume":"28","author":"Chi-Chih Yao Andrew","year":"1981","unstructured":"Andrew Chi-Chih Yao. 1981. Should Tables Be Sorted? J. ACM 28, 3 (1981).","journal-title":"J. ACM"},{"key":"e_1_3_2_1_55_1","unstructured":"Lo\u00efc Yengo Sailaja Vedantam Eirini Marouli Julia Sidorenko Eric Bartell Saori Sakaue Marielisa Graff Anders U Eliasen Yunxuan Jiang Sridharan Raghavan et al. 2022. A saturated map of common genetic variants associated with human height. Nature 610 7933 (2022)."},{"key":"e_1_3_2_1_56_1","unstructured":"Rahul Yesantharao Yiqiu Wang Laxman Dhulipala and Julian Shun. 2021. Parallel Batch-Dynamic kd-Trees. arXiv:2112.06188 [cs.DS]"},{"key":"e_1_3_2_1_57_1","volume-title":"Hierarchical cluster analysis: comparison of three linkage measures and application to psychological data. The quantitative methods for psychology 11, 1","author":"Yim Odilia","year":"2015","unstructured":"Odilia Yim and Kylee T Ramdeen. 2015. Hierarchical cluster analysis: comparison of three linkage measures and application to psychological data. The quantitative methods for psychology 11, 1 (2015)."},{"key":"e_1_3_2_1_58_1","unstructured":"Shangdi Yu Laxman Dhulipala Jakub \u0141\u0105cki and Nikos Parotsidis. 2025. Dyn-HAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering. arXiv:2501.07745 [cs.DS]"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489509"}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:20Z","timestamp":1777922360000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":59,"alternative-id":["10.1145\/3694906.3743315","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743315","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}