Optimizing K-means is still an active area of research for purpose of clustering. Recent developments in Cloud Co mputing have resulted in emergence of Big Data Analytics. There is a fresh need of simp le, fast yet accurate algorithm for clustering huge amount of data. This paper proposes optimization of K-means through reduction of the points which are considered for re- clustering in each iteration. The work is generalizat ion of earlier work by Poteras et al who proposed this idea. The suggested scheme has an improved average runtime. The cost per iteration reduces as number of iterations grow which makes the proposal very scalable. Index Terms—Clustering, k-means, Optimizat ion of k- means, Distance metrics, Poteras et al"s Scheme.