## 4 Empirical Evaluation of Proposed Algorithms
### Experiments with Reference Datasets
#### 4.1.4 Results for Scalability  
We conducted scalability tests for TIN and SVH to show how running time varies as a function of #processing elements (Matlab workers) and to demonstrate the benefits of using SRPK-means\(\parallel\) for a very high-dimensional dataset (SVH) when \(K\) is increased. \begin{table}
\begin{tabular}{l c c c c c c c c c c c c c} \hline \hline  & **HAR** & **ISO** & **LET** & **CFE** & **MMN** & **BIR** & **BSM** & **FCT** & **SVH** & **RCV** & **USC** & **KDD** & **MSM** & **TIN** & **OXR** \\ \hline K-means++ & 255 & 31.5 & **29** & 62 & 86 & 94 & 36 & 14 & - & - & - & - & - \\  & \(\pm\)11.1 & \(\pm\)8.7 & \(\pm\)22.1 & \(\pm\)15.8 & \(\pm\)30.3 & \(\pm\)22.7 & \(\pm\)11.9 & \(\pm\)11.1 & - & - & - & - & - & - \\ \hline K-means\(\parallel\) & 28.5 & 33.5 & 68.5 & 59 & 86 & 97 & 35 & 95 & 32.5 & 20 & 81 & 82 & 31 & 37.5 & 27.5 \\  & 41.0 & 4.11.0 & 4.22.8 & \(\pm\)15.6 & 4.30.5 & 42.2 & 41.2 & 4.10.3 & 42.5 & 42.3 & 48.5 & 42.5 & 41.1 & 43.8 & 42.3 \\ \hline SK-means\(\parallel\) & 28.5 & 25.8\(\pm\)0.42 & **63.9\(\pm\)0.43** & 52.7 & 28 & **86.5** & 25.8\(\pm\)0.52 & **14.9\(\pm\)0.42** & **28.5\(\pm\)0.52** & **19** & **86** & **72** & **24** & **24** & **24** & **23** & **24** & **22** & **24** \\ \hline  & 49.4 & 49.2 & 42.02 & 41.46 & 4.307 & 42.8 & 41.35 & 45.5 & 43.7 & 41.4 & 41.9 & 42.2 & 41.3 & 41.7 & 41.7 \\ \hline SRPK-means\(\parallel\) \(F\) = 5 & 35 & 72 & 60 & 87 & - & 35 & 64 & 58 & 20 & 93.5 & 96.5 & 38.0 & 40 & 25.5 \\  & 49.5 & 49.5 & 42.28 & 41.61 & \(\pm\)37.2 & - & 412.1 & 4.2 & 2.11 & 4.13 & 41.4 & 25.2 & 41.5 & 42.5 & 41.6 \\ \hline  & **39.5** & 30 & 76.5 & 55.5 & 72.5 & - & 30.5 & 5.4\(\pm\)0.4 & 32 & 20 & 83.5 & 78 & 31.5 & **38.5** & **28** \\  & 41.05 & 41.0 & 42.11 & \(\pm\)32.3 & - & \(\pm\)13.03 & - & \(\pm\)11.4 & +5 & +2.2 & +1.3 & +19.8 & +24.2 & +1.7 & +3 & +1.8 \\ \hline  & 20.6* & 30 & - & 53.5 & 80 & - & 26.5*,4.4 & 34.4 & 30 & **17.9** & **27** & **69** & 30 & 39 & 27.5 \\  & 49.0 & 48.7 & - & 41.38 & 43.29 & - & 410.6 & 4.8 & 4.21 & 41.2 & 41.7 & 41.2 & 41.89 & +1.2 & +2.6 & +2.1 \\ \hline  & **39.5** & 28.4 & - & **50.** & **66** & - & **24.4** & 4.9\(\pm\)0.42 & **27.4** & **17.9** & **69** & 70 & 28.5*,4.6 & 35.5 & 28.5 \\  & 49.4 & 49.1 & - & 47.3 & 42.77 & - & 411.8 & 45.3 & 42.9 & 40.9 & 42.74 & 25.4 & 42.0 & 44.5 & 42.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The number of iterations needed for convergence. The statistically significant differences according to the Kruskal-Wallis test are indicated with \(**\) after the dataset acronym. Symbols +, \(*\), \(\ddagger\), and \(\dagger_{P}\) indicate that the method has statistically significantly faster convergence in a pairwise comparison with respect to K-means++ (K++), K-means\(\parallel\) (K\(\parallel\)), SK-means\(\parallel\) (SK\(\parallel\)), and SRPK-means\(\parallel\) (SRPK\(\parallel\)) for \(P=P^{\prime}\), respectively. Median values are on a gray background. Corresponding median absolute deviation values are below the median values. The best performances are highlighted in bold. \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline  & **KDD** & **USC** & **OXB** & **TIN** & **MSM** & **RCV** & **SVH** \\ \hline K-means\(\parallel\) & **5.0 \(\pm\) 0.1** & **3.0 \(\pm\) 0.3** & 26.0 \(\pm\) 1.8 & 52.1 \(\pm\) 1.3 & 98.5\(\pm\)2.9 & 14.1 \(\pm\) 1.8 & 13.7 \(\pm\) 0.8 \\ SK-means\(\parallel\) & & 8.7 \(\pm\) 0.2 & 5.0 \(\pm\) 0.2 & 39.1 \(\pm\) 0.5 & 65.8 \(\pm\) 0.9 & 145.5 \(\pm\) 0.6 & 20.6 \(\pm\) 0.7 & 17.3 \(\pm\) 0.2 \\ SRPK-means\(\parallel\) & \(p=5\) & 7.9 \(\pm\) 0.1 & 3.9 \(\pm\) 0.1 & **23.7 \(\pm\) 0.3** & **24.9 \(\pm\) 0.4** & **32.2 \(\pm\) 0.3** & **4.8 \(\pm\) 0.1** & 3.4 \(\pm\) 0.2 \\ SRPK-means\(\parallel\) & \(p=40\) & 10.2 \(\pm\) 0.2 & 5.6 \(\pm\) 0.3 & 27.4 \(\pm\) 0.6 & 28.5 \(\pm\) 1.3 & 37.9 \(\pm\) 0.6 & 5.6 \(\pm\) 0.5 & **3.3 \(\pm\) 0.2** \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Running time for the initialization in seconds. The best performances are highlighted in bold.