# Memory requirements of $k$-means clustering

Can anyone tell me the factors that affect the memory requirements of $k$-means clustering with a bit of explanation?

• $k$-means is NP-hard, so there is a lot of heuristics which significantly differ, also in resource consumption; are you interested in some specific algorithm? – user88 Jun 5 '11 at 20:57
• Are you referring to Lloyd's algorithm? If so, I believe the memory requirements for a standard implementation would be O(log k * n) because you would have to store a list of (point,cluster) pairs for the update step. Because k is usually small, my guess is you could usually get away with storing just a short for each point, but I haven't looked at any specific implementations. – rm999 Jun 6 '11 at 0:08
• You only really need intermediate storage of size $k$, if you're willing to store the data on disk and scan it in each pass. Of course, this is very slow, and so there are tradeoffs involved. What specifically were you looking for. – Suresh Venkatasubramanian Jun 7 '11 at 4:21

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.