A Comprehensive Survey of Clustering Algorithms (2015)

Table of Contents

Low complexity algorithms #

Algorithm	Type	Complexity	Scalability	Large-scale data	High-dimensional data	Shape
k-means	Partition	$O(knt)$	Middle	Yes	No	Convex
BIRCH	Hierarchy	$O(n)$	High	Yes	No	Convex
CURE	Hierarchy	$O(s^2s)$	High	Yes	Yes	Arbitrary
FCM	Fuzzy theory	$O(n)$	Middle	No	No	Convex
CLICK	Graph theory	$O(k*f(v, e))$	High	Yes	No	Arbitrary
STING	Grid	$O(n)$	High	Yes	Yes	Arbitrary
CLIQUE	Grid	$O(n+k^2)$	High	No	Yes	Convex
WaveCluster	Grid	$O(n)$	High	Yes	No	Arbitrary
FC	Fractal theory	$O(n)$	High	Yes	Yes	Arbitrary
STREAM	Stream data	$O(kn)$	Middle	Yes	No	Arbitrary

Xu, D., Tian, Y. A Comprehensive Survey of Clustering Algorithms. Ann. Data. Sci. 2, 165–193 (2015). https://doi.org/10.1007/s40745-015-0040-1