## 4 Empirical Evaluation of Proposed Algorithms
### Experiments with Reference Datasets
#### 4.1.1 Experimental Setup
The parallel algorithms were implemented with Matlab Parallel Computing Toolbox with the SPMD blocks and message passing functions as discussed in Section 3.3. The parallel experiments were run in a computer cluster using Sandy Bridge nodes with 16 cores and 256 GB memory. A parallel pool of 32 workers was used in the experiments; therefore, 4 workers were allocated for each subset. In the parallel experiments, each worker had a \(\frac{1}{4}\) random disjoint partition of the subset on the local workspace. For all datasets we used the following settings: (i) for K-means\(\|\): \(l=2K\) and \(r=5\); (ii) for SK-means\(\|\) and SRPK-means\(\|\): \(T_{init}=5\) and \(S=8\); (iii) and for SRPK-means\(\|\): \(P\in\{5,10,20,40\}\) and \(R\) with \(r_{ij}=\pm 1\). Please note that occurrence of an empty cluster for SRPK-means\(\|\) is possible in rare cases when all \(S\) subsets produce an empty cluster. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **\#Observations (N)** & **\#Features (M)** & **\#Clusters (K)** \\ \hline HAR & 7352 & 561 & 6 \\ ISO & 7797 & 617 & 26 \\ LET & 20,000 & 16 & 26 \\ GFE & 27,936 & 300 & 36 \\ MNI & 70,000 & 784 & 10 \\ BIR & 100,000 & 2 & 100 \\ BSM & 583,250 & 77 & 50 * \\ FCT & 581,012 & 54 & 7 \\ SVH & 630,420 & 3072 & 100 * \\ RCV & 781,265 & 1000 & 350 \\ USC & 2,458,285 & 68 & 100 * \\ KDD & 4,898,431 & 41 & 100 * \\ M8M & 8,100,000 & 784 & 265 \\ TIN & 15,860,403 & 384 & 100 * \\ OXB & 16,334,970 & 128 & 100 * \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Characteristics of datasets. The number of clusters \(K\) was chosen according to the known number of classes or fixed by hand. The latter choice is indicated with symbol *. (For instance, empty clusters appeared seven times in all the experiments with the synthetic datasets as reported in Section 4.2). In these cases, we repeated the whole clustering initialization from the start. After initialization, the [PERSON]'s algorithm was executed until the number of new assignments between the consecutive iterations was below or equal to the threshold. For the five largest datasets (SVH, RCV, OXB, M8M and TIN) we set this threshold to 1% of \(N\) and otherwise to zero. In the parallel experiments, runs were repeated 10 times for each setting. In the serial experiments, runs were repeated 100 times for each setting. Values for the number of clusters, \(K\), are given in the last column of Table 1. Since the MNIST8M dataset is constructed artificially from the original MNIST dataset, we set \(K\) for MNIST8M based on the optimal value for MNIST used by [PERSON] et al. [47]. Otherwise, the selection is either based on the known number of classes or fixed arbitrarily (indicated with * in Table 1). The quality of the clustering results between the methods was compared by using SSE. The SSE values were computed with formula (1) for the whole data. Finally, statistical comparison between the methods was performed with the nonparametric Kruskal-Wallis test [48; 49], since in most cases the clustering errors were not normally distributed. The significance level was set to 0.05.