6533b824fe1ef96bd127fef7
RESEARCH PRODUCT
A Greedy Algorithm for Hierarchical Complete Linkage Clustering
Anna Katharina HildebrandtErnst AlthausAndreas Hildebrandtsubject
CombinatoricsCURE data clustering algorithmSUBCLUNearest-neighbor chain algorithmCorrelation clusteringSingle-linkage clusteringHierarchical clustering of networksGreedy algorithmComplete-linkage clusteringMathematicsdescription
We are interested in the greedy method to compute an hierarchical complete linkage clustering. There are two known methods for this problem, one having a running time of \({\mathcal O}(n^3)\) with a space requirement of \({\mathcal O}(n)\) and one having a running time of \({\mathcal O}(n^2 \log n)\) with a space requirement of Θ(n 2), where n is the number of points to be clustered. Both methods are not capable to handle large point sets. In this paper, we give an algorithm with a space requirement of \({\mathcal O}(n)\) which is able to cluster one million points in a day on current commodity hardware.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-01-01 |