Sublinear Algorithms for Hierarchical Clustering. (arXiv:2206.07633v1 [cs.DS])

Web: http://arxiv.org/abs/2206.07633

Hierarchical clustering over graphs is a fundamental task in data mining and
machine learning with applications in domains such as phylogenetics, social
network analysis, and information retrieval. Specifically, we consider the
recently popularized objective function for hierarchical clustering due to
Dasgupta. Previous algorithms for (approximately) minimizing this objective
function require linear time/space complexity. In many applications the
underlying graph can be massive in size making it computationally challenging
to process the graph even using a linear time/space algorithm. As a …

algorithms arxiv clustering hierarchical