# Three Rapid Methods for Averaging GPS Segments
## 4 Experiments
### Results  
The effect of the threshold is shown in Figure 12. The results show that we can achieve good results even with the linear model. For example, RapSeg-A reaches 62.0% even without the curvy model. We set the threshold to 0.986 based on the training, as the performance seems to peek at that point. RapSeg-C reaches the best performance of 62.2%. If the threshold was increased further, the maximum performance of 62.3% could have been reached. Most of the performance is achieved already by the linear model, which indicates unbalance of the line and curve shapes in the dataset. The effect of outlier removal is shown in Table 2. It clearly improves the performance with the training data, and the smoothed variant is always better than the full outlier removal as such. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Step** & **Solution** & **Complexity** \\ \hline \multirow{3}{*}{Linear Segment} & Endpoints & Table look-up & O(\(k\)) \\  & K-means & Clustering & O(\(k\))\({}^{1}\) \\  & Median points & Table look-up + average & O(\(k\)) \\ \hline \multirow{3}{*}{Curve Segment} & RapSeg-A: Median & Selection & O(\(k\)) \\  & RapSeg-B: Medoid & Hausdorff & O(\(n^{2}\cdot k^{2}\)) \\ \cline{1-1}  & RapSeg-C: Divide-and-Conquer & Calculate M & O(T\(\cdot k\)) \\ \hline \hline \end{tabular}  
\({}^{1}\) Assuming 10 iterations of k-means with 2 clusters: 2\(\cdot\)10 \(k\) = 20\(k\) = O(\(k\)).  
\end{table} 
Table 1: The time complexity of the proposed methods. Figure 12: Effect of the threshold: the higher the value, the more often the curvy model is used. However, the results do not generalize to the test data, and the best results are reached by RapSeg-A and RapSeg-C without any outlier removal step at all. We, therefore, drop the outlier removal from the final method completely. Comparison of the RapSeg method (without the outlier removal) is compared against existing techniques in Table 3. All variants outperform the existing methods on accuracy, processing time and the number of points. In other words, RapSeg does not only provide more accurate approximation of the segment but it also saves processing time. The closest competitor in terms of accuracy is the method by [PERSON] [17]. The performance of the different curve models is compared in Table 4. We can see that RapSeg-A has the best performance of length and processing time, while RapSeg-C has the best performance on accuracy and the number of points. The reason for the oversample of the other variants is the use of median/medoid, which use the original points as such without any attempt to reduce their amount. Their main difference between the variants is their processing time; RapSeg-B takes 5 times longer than RapSeg-A (0.59s vs. 3.39s), whereas RapSeg-C is almost as efficient (0.56s vs. 0.67s). From the visual examples in Figure 13, we can see that all methods provide satisfactory results whereas RapSeg-A appears to be more robust on noise. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Method** & **HC-SIM** & **Length** & **Points** & **Time** \\ \hline RapSeg-A & 53.05\% & **99\%** & **194\%** & **0.59 s** \\ RapSeg-B & 53.26\% & **89\%** & 167\% & 3.39 s \\ RapSeg-C & **55.53\%** & **95\%** & 120\% & 0.67 s \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of the proposed methods on curve model, as evaluated by HC-SIM accuracy. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Outlier Removal** & **RapSeg-A** & **RapSeg-B** & **RapSeg-C** \\ \hline \multirow{3}{*}{Train} & — & 67.4\% & 68.3\% & 67.9\% \\  & Smoothed & 69.4\% & 70.2\% & 69.5\% \\  & Full & 69.0\% & 69.7\% & 69.3\% \\ \hline \multirow{3}{*}{Test} & — & 62.0\% & 61.9\% & 62.2\% \\  & Smoothed & 61.8\% & 61.9\% & 62.0\% \\  & Full & 61.3\% & 61.4\% & 61.5\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Effect of outlier removal on the three variants, evaluated by hierarchical cell-based similarity measure (HC-SIM) accuracy.