(initialization, distance function, termination criterion, etc.) can be modified. This is evidenced by hundreds of publications over the last fifty years that extend k-means in various ways. Third, it has a time complexity that is linear in $N$, $D$, and $K$ (in general, $D \ll N$ and $K \ll N$). For this reason, it can be used to initialize more expensive clustering algorithms such as expectation maximization [@Bradley98], DBSCAN [@Dash01], and spectral clustering [@Chen11]. Furthermore, numerous sequential [@Kanungo02; @Hamerly10] and parallel [@Chen10] acceleration techniques are available in the literature. Fourth, it has a storage complexity that is linear in $N$, $D$, and $K$. In addition, there exist disk-based variants that do not require all points to be stored in memory [@Ordonez04]. Fifth, it is guaranteed to converge [@Selim84] at a quadratic rate [@Bottou95]. Finally, it is invariant to data ordering, i.e., random shufflings of the data points.

On the other hand, k-means has several significant disadvantages. First, it requires the number of clusters, $K$, to be specified in advance. The value of this parameter can be determined automatically by means of various internal/relative cluster validity measures [@Vendramin10]. Second, it can only detect compact, hyperspherical clusters that are well separated. This 