## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
\begin{table}
\begin{tabular}{c c} \hline \hline
**Synthetic Uniform Data**[34] \\
**Description: Synthetic Data with a Uniform Distribution** \\ \hline Number of data points & 100,000 \\ Number of columns & 6 \\ Data domain & 0–512 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: The data used for the performance evaluation. \begin{table}
\begin{tabular}{c c} \hline \hline
**Proposed k-Means Clustering** & **SkMC\({}_{\text{I}}\)[25]** \\
**Algorithm (SkMC\({}_{\text{A}}\))** & \\ \hline Proposed Parallel k-Means Clustering & \\ Algorithm (PSkMC\({}_{\text{A}}\)) & PSkMC\({}_{\text{I}}\) (Parallel processing version of SkMC\({}_{\text{I}}\)[25]) \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Targets for the performance comparison of the proposed k-means clustering algorithm. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Values** & **Default** \\ \hline \# of data points (n) & 2k, 4k, 6k, 8k, 10k & 10k \\ k & 5, 10, 15, 20 & 10 \\ \# of data dimensions (m) & 2 & 2 \\ Encryption key size (K) & 512 & 512 \\ Bit length & 22 & 22 \\ Threshold & 10 & - \\ \# of Threads & 2, 4, 6, 8, 10 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Parameters considered in the performance evaluation of the k-means clustering algorithms. the encryption operation protocols, \(\text{SkMC}_{\text{A}}\) demonstrates approximately 10.8 times better performance than \(\text{SkMC}_{\text{I}}\). Figure 8 depicts the performance of \(\text{SkMC}_{\text{A}}\) and \(\text{SkMC}_{\text{I}}\) with varying values of k when n = 10k, m = 2, and K = 512. For the case where k = 20, \(\text{SkMC}_{\text{A}}\) takes approximately 18,791 s, while \(\text{SkMC}_{\text{I}}\) requires around 236,502 s. The significant performance improvement is attributed to the proposed k-means clustering algorithm, which rapidly performs encryption protocols through decimal-based arithmetic operations. In contrast, \(\text{SkMC}_{\text{I}}\) uses iterative encryption protocols based on binary arithmetic. \(\text{SkMC}_{\text{A}}\) demonstrates approximately 12.3 times better performance than \(\text{SkMC}_{\text{I}}\). Figure 9 illustrates the performance of \(\text{PSkMC}_{\text{A}}\) and \(\text{PSkMC}_{\text{I}}\) with varying numbers of threads when n = 10k, k = 10, m = 2, and K = 512. When the number of threads is 2, \(\text{PSkMC}_{\text{A}}\) takes approximately 4918 s, while \(\text{PSkMC}_{\text{I}}\) requires around 40,345 s. When the number of threads is 10, \(\text{PSkMC}_{\text{A}}\) takes about 1287 s, and \(\text{PSkMC}_{\text{I}}\) takes around 16,446 s. Overall, \(\text{PSkMC}_{\text{A}}\) demonstrates approximately 13.5 times better performance than \(\text{PSkMC}_{\text{I}}\). Figure 8: Performance evaluation of k-means clustering algorithms with a changing k value. Figure 7: Performance evaluation of k-means clustering algorithms with a changing data size (n). As shown in Figure 9, the proposed parallel k-means clustering algorithm demonstrates a linear decrease in processing time as the number of threads increases from 2 to 10. In other words, there is no performance degradation as the number of threads increases. This indicates that the proposed parallel k-means clustering algorithm exhibits scalability, where the performance can scale effectively with the number of threads. Figure 10 illustrates the memory usage of the proposed k-means clustering algorithm and the existing algorithm. When n = 10,000, k = 10, and K = 512, the existing k-means clustering algorithm uses approximately 1000 kilobytes, while the proposed algorithm uses around 1150 kilobytes. Figure 10 shows that the proposed algorithm requires approximately an additional 15% memory usage compared with the existing algorithm. The reason for this is that the proposed algorithm consumes more memory due to the preprocessing step involved in sampling the data. However, the 150 kilobytes in total of memory overhead compared with the existing algorithm is quite small in terms of memory utilization.