  K-means plays a vital role in data mining and is the simplest and most widely
used algorithm under the Euclidean Minimum Sum-of-Squares Clustering (MSSC)
model. However, its performance drastically drops when applied to vast amounts
of data. Therefore, it is crucial to improve K-means by scaling it to big data
using as few of the following computational resources as possible: data, time,
and algorithmic ingredients. We propose a new parallel scheme of using K-means
and K-means++ algorithms for big data clustering that satisfies the properties
of a ``true big data'' algorithm and outperforms the classical and recent
state-of-the-art MSSC approaches in terms of solution quality and runtime. The
new approach naturally implements global search by decomposing the MSSC problem
without using additional metaheuristics. This work shows that data
decomposition is the basic approach to solve the big data clustering problem.
The empirical success of the new algorithm allowed us to challenge the common
belief that more data is required to obtain a good clustering solution.
Moreover, the present work questions the established trend that more
sophisticated hybrid approaches and algorithms are required to obtain a better
clustering solution.
