Sublinear Algorithms for Estimating Single-Linkage Clustering Costs

Pan Peng, Christian Sohler, Yi Xu

Single-linkage clustering is a fundamental method for data analysis. Algorithmically, one can compute a single-linkage $k$-clustering (a partition into $k$ clusters) by computing a…