Can anyone tell me the factors that affect the memory requirements of $k$-means clustering with a bit of explanation?
Algorithms like Lloyds can be implemented with $k\cdot(2\cdot d + 1)$ floating point values memory use only. MacQueens k-means algorithm should only need $k\cdot(d + 1)$ memory.
However, as most users will want to know which point belongs to which cluster, almost every implementation you'll find will use $O(n+k\cdot d)$ memory.
In other words, the memory use by k-means is essentially the output data size.
I recently came across a note of a scipy implementation of the k-means algorithm in scipy.cluster.vq.py
Notes ----- This could be faster when number of codebooks is small, but it becomes a real memory hog when codebook is large. It requires N by M by O storage where N=number of obs, M = number of features, and O = number of codes.