## 3 New Algorithms
### Parallel Implementation of the Proposed K-Means Initialization Algorithms  
[PERSON] et al. [6] implemented K-means\(\|\) with the MapReduce programming model. It can also be implemented by the Single Program Multiple Data (SPMD) programming model with message passing. Then all the steps of the parallelized Algorithms 1-3 are executed inside an SPMD block. Next, a parallel implementation of K-means\(\|\) as depicted in Algorithm 1 is briefly described, by using Matlab Parallel Computing Toolbox (PCT), SPMD blocks, and message passing functions (see [42] for a detailed description about PCT). First, data \(\mathbf{X}\) is split into \(Q\) subsets of approximately equal size and then the subsets are distributed to \(Q\) workers. Step 1 picks a random point from a random worker and broadcasts this point to all other workers. In Step 2, each worker calculates distances and SSE for its local data. Next, points are aggregated by calling \(gplus\)-function, after which the aggregation distributes this sum to other workers. In Steps 4 and 5, each worker samples points from its local data, the next points are aggregated to \(\mathbf{C}^{\prime}\) by calling \(gop\)-function, and then \(\mathbf{C}^{\prime}\) is broadcasted to all workers. Again, distances and SSE are calculated similarly as in Step 2. Each worker in Step 6 assigns weights based on its local data, after which the weights are aggregated with \(gop\)-function. Finally, Step 7 is computed sequentially.  
As with the parallel K-means\(\|\) implementation, a parallel implementation of Algorithm 2 with SMPD and message passing is described next. First, each subset \(\mathbf{X}_{i}\) from \(S\) subsets is split into \(J\) approximately equal size subsets and then these subsets are distributed to \(J\times S\) workers, e.g., subset \(\mathbf{X}_{i}\) is distributed to workers \((i-1)J+1,...,(i-1)J+J\). In Steps 1-3, each subset of workers runs steps for subset \(\mathbf{X}_{i}\) in parallel similarly as described in the previous paragraph. For parallel Lloyd's iterations, a similar strategy as proposed in [8] can be used in Step 2. Steps 1-3 require calling modified \(gop\)-function and \(gplus\)-function for the subset of workers; these functions were modified to support this requirement. Finally, prototypes corresponding to the smallest local SSE from the subset \(i^{\prime}\) allocated workers \((i^{\prime}-1)J+1,...,(i^{\prime}-1)J+J\) are returned as the initialization.  
The parallel SRPK-means\(\|\) in Algorithm 3 can be implemented in a highly similar fashion to the parallel SK-means\(\|\). More precisely, in Step 1, each worker \((i-1)J+1\)where \(i\in\{1,2,...,S\}\), generates the random matrix \(\mathbf{R}_{i}\) and broadcasts it to workers \((i-1)J+1,...,(i-1)J+J\). In Step 2, each worker computes random projected data for its local data. Steps 3-4 are otherwise computed similarly to the parallel SK-means\(\parallel\) Steps 1 and 2, except these steps are executed for the projected subsets. In Step 5, the prototypes are computed in the original space in parallel. Finally, Steps 6 and 7 are the same as Steps 3 and 4 in Algorithm 2. The parallel implementations of the proposed methods and K-means\(\parallel\) are available in ([[https://github.com/jookriha/Scalable-K-means](https://github.com/jookriha/Scalable-K-means)]([https://github.com/jookriha/Scalable-K-means](https://github.com/jookriha/Scalable-K-means))).