# Estimating Road Segments Using Kernelized Averaging of GPS Trajectories
## 4 Experimentation
On the training data, a simple grid search led to selecting \(\gamma=2\) and \(T=100\), which allowed reaching a HC-SIM score of 67.39%. Figure 6: HC-SIM (in %) of the iTEKA centroid estimate relative to the ground truth trajectory when \(\
u\) varies for \(T=50\), \(T=100\), \(200\) and \(300\). Figures 6 and 7 show that over-sampling has an important impact on the HC-SIM measure of the estimated centroids. As stated above, the HC-SIM measure is not strongly correlated to the RMSE measure. The correlation between RMSE and HC-SIM measures when varying \(\gamma\) parameter for soft-DTW or \(\
u\) for iTEKA is, respectively, \(-61\%\) and \(+67\%\). This shows the difficulty of this challenge, since the ground truth provided on the training data does not directly help to train the models. Hence, selecting the minimum RMSE value would not lead to the best HC-SIM measure. Table 1 synthesizes the results obtained by the eight tested methods. It turns out that centroid based methods are much more accurate than the medoid ones. The averaging scheme is thus quite important. One can notice that, on this benchmark characterized by small and simple trajectories, the Euclidean averaging performed quite well, reaching a 67.15% HC-SIM when outlier removal was considered. This is better than soft-DTW that obtained 66.93%. The best method on this benchmark is iTEKA that reached 67.63% HC-SIM with outlier removal. However, with the absence of an analytical knowledge of the HC-SIM measure that is used, we cannot provide confidence intervals or state whether these results are significant or not. The final results of the challenge ([[http://cs.uef.fi/sipu/segments/results.html](http://cs.uef.fi/sipu/segments/results.html)]([http://cs.uef.fi/sipu/segments/results.html](http://cs.uef.fi/sipu/segments/results.html))), as provided by the organizers, are given in Table 2. When no post-processing was used, iTEKA method ranks first (Method A), but, as shown in the last two columns of the table, the method is slow and induces a spurious number of points in the averaged trajectory that is provided. When reducing the number of points of the centroid trajectory, using the down-sampling post-processing, the HC-SIM quality measure dropped, as shown for Method E that corresponds to the processing pipeline presented in Figure 1 when iTEKA was used. The slight differences in the results apparent in Tables 1 and 2 are \begin{table}
\begin{tabular}{l c c} \hline \hline
**Method** & **Without Outlier Removal** & **With Proposed Outlier Removal** \\ \hline Euclidean Medoid [25] & 60.90 & 60.49 \\ DTW Medoid [26] & 63.16 & 63.16 \\ \(\mathcal{K}_{\text{rdtw}}\) Medoid [23] & 61.20 & 61.20 \\ soft-DTW Medoid [9] & 61.29 & 61.29 \\ \hline Euclidean Centroid [27] & 67.28 & 67.54 \\ DBA Centroid [28] & 66.40 & 66.40 \\ soft-DTW Centroid [9] & 67.47 & 67.39 \\ iTEKA Centroid [13] & **68.21** & **68.28** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Best HC-SIM (in %) obtained with or without outlier removal for the eight tested methods. The best obtained HC-SIM value are indicated in bold cases. Figure 7: HC-SIM (in %) of the soft-DTW centroid estimate relative to the ground truth trajectory when \(\gamma\) varies for \(T=\) 50, 100, 200 and 300.  
probably due to a slight change in the HC-SIM measure that produces differences in the selection of the meta parameters for the submitted results. Finally, Figure 8 presents the elapsed time in a logarithmic scale when \(T\) increases (the length of the re-sampled trajectories) for the centroids approaches. The Euclidean centroid method is clearly the most efficient one, as expected, followed by the iTEKA method that is significantly faster than the soft-DTW centroid one. The least efficient method is clearly DBA. Indeed, although all the tested algorithms were run on the same architecture and operating system, the observed differences of processing efficiency may be due, at least partly, to difference in the implementation choices.