data sets, each of the IMs require less than a few milliseconds of CPU time. On the other hand, on large and/or high-dimensional data sets efficiency differences become more prominent. It should be noted that each of the values reported in this table corresponds to a single k-means ‘run’. In practice, a random method is typically executed $R$ times, e.g., in this study $R=100$, and the output of the run that gives the least final SSE is taken as the result. Therefore, the total computational cost of a random method is often significantly higher than that of a deterministic method. For example, on the ISOLET data set, which has the greatest $N \times D \times K$ value among all the data sets, `K` took on the average $3,397$ milliseconds, whereas `OP` took $12,460$ milliseconds. The latter method, however, required about $27$ times less CPU time than the former one since the former was executed a total of $100$ times.

Relative Performance Analysis
-----------------------------

We also determined the number of data sets (out of 24) on which `OV` and `OP` respectively performed $\{$worse than/same as/better than$\}$ `V` and `P`. Tables \[tab\_rel\_var\] and \[tab\_rel\_pca\] present the results for `OV` and `OP`, respectively. 