# Efficient Time-Series Clustering through Sparse Gaussian Modeling
## 5 Experimental Evaluation
### Computational Efficiency
\(T_{a}+T_{b}\) is the total CPU utilization of our method, \((T_{a}+T_{b})/T_{k}\) indicates the CPU utilization overhead due to the modeling process; \(T_{k}/T_{b}\) quantifies how much slower \(k\)-means becomes when applied to the original dataset compared against the same algorithm applied to the sparsified dataset; and \(T_{a}/N\) is the average running time of the modeling phase per time series in the particular dataset. We observe that \(k\)-means runs from 1.6 (in very small datasets) up to 230 times faster when applied to the sparsified dataset (compared against the \(k\)-means algorithm applied to the original instance, see also Figure 6). The speed-up is due to the improved running time for computing DTW from \(\Theta(T^{2})\) in the original data to \(\Theta(\log^{2}T)\) in the sparsified data. As expected, the speed-up becomes more apparent when it comes to datasets with time-series length \(T\) above a few hundred. On average, \(k\)-means runs more than 50 times faster when applied to the sparsified dataset than when applied to the original one. On the other hand, the computational overhead of Sparse Gaussian Process Regression becomes quite high, compared against the running time of the standard \(k\)-means algorithm, when Algorithm 1 is applied to datasets of small to moderate size (and with time series of small to moderate length). However, for datasets with larger sizes and \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Dataset** & \(T_{k}\) & \(T_{b}\) & \(T_{a}\) & \(\dfrac{T_{k}}{T_{b}}\) & \(\dfrac{(T_{a}+T_{b})}{T_{k}}\) & \(\dfrac{T_{a}}{N}\) \\ \hline
**SmallKitchenAppliances** & 1683.222 & 18.953 & 3321.628 & 88.8 & 2.0 & 2.768 \\
**SonyAIBRobotSurface1** & 34.634 & 15.644 & 3655.760 & 2.2 & 106.0 & 4.874 \\
**SonyAIBRobotSurface2** & 71.301 & 25.905 & 6676.567 & 2.8 & 94.0 & 10.751 \\
**Strawberry** & 1183.540 & 23.964 & 7845.866 & 49.4 & 6.6 & 8.006 \\
**SwedishLeaf** & 224.676 & 67.156 & 5367.119 & 3.3 & 24.2 & 5.460 \\
**Symbols** & 4984.632 & 43.091 & 9755.276 & 115.7 & 2.0 & 8.671 \\
**SyntheticControl** & 26.540 & 16.777 & 3758.807 & 1.6 & 142.3 & 3.685 \\
**ToeSegmentation1** & 464.657 & 8.339 & 1931.603 & 55.7 & 4.2 & 3.219 \\
**ToeSegmentation2** & 263.977 & 4.073 & 1176.577 & 64.8 & 4.5 & 4.390 \\
**Trace** & 225.796 & 4.452 & 1505.905 & 50.7 & 6.7 & 9.072 \\
**TwoLeadECG** & 115.038 & 33.520 & 7091.992 & 3.4 & 61.9 & 35.460 \\
**TwoPatterns** & 767.798 & 313.861 & 28,274.694 & 2.4 & 37.2 & 24.333 \\
**Wine** & 51.230 & 1.493 & 831.680 & 34.3 & 16.3 & 0.166 \\
**WordSynonyms** & 3179.780 & 61.514 & 3889.850 & 51.7 & 1.2 & 35.044 \\
**Worms** & 1540.641 & 9.298 & 2799.553 & 165.7 & 1.8 & 3.093 \\ \hline
**mean** & 982.337 & 37.214 & 4401.955 & 53.8 & 40.0 & 8.095 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: _Cont._  
Figure 6: CPU utilization time comparison of the \(k\)-means algorithm applied to the original datasets (blue bars) and to the sparsified data sets (orange bars). \(k\)-means on the sparsified instance can run up to 230 times faster than \(k\)-means on the original instance. longer time series, such as InsectWingbeatSound (with 2200 time series of length 256 each), RefrigerationDevices and LargeKitchenAppliances (both with 750 time series of length 720 each), the benefits of the significantly improved asymptotic computational complexity of our framework become apparent. In these datasets, the total \(T_{a}+T_{b}\) running time of our framework is practically identical to the total running time of the standard \(k\)-means. For some larger datasets, such as ShapesAll (with 1200 time series of length 512 each), the total \(T_{a}+T_{b}\) running time of our framework is half the total running time of the standard \(k\)-means.