Another approach is to transform the dataset into a smaller but representative dataset, called a core-set, and running k-means on that core-set instead which pr

Another approach is to transform the dataset into a smaller but representative dataset, called a core-set, and running k-means on that core-set instead which produces a "(1+e )-approximation for the optimal cluster centers". See http://people.csail.mit.edu/dannyf/kmeancoreset.pdf http://people.csail.mit.edu/dannyf/kmeancoreset.pdf