K-means is a very effective clustering algorithm that has wide applications. However, without good initialization of centroids, it might lead to sub-optimal solution. K-means ++ is a good initialization algorithm designed to work well with K-means. However, since both algorithms are rather sequential, together, they are quite time-consuming. Our project focuses on designing a parallel version of the algorithm to make it faster without compromising accuracy.