# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
## 7 Empirical Evaluation
### Empirical Results  
Figure 14 compares the proposed MOFA and conventional algorithm on the SJ road network. Each chart presents the M\(k\)FN execution time and number of \(k\)FN queries required to answer the M\(k\)FN query. The numbers in parentheses in Figures 14-16 refer to the number of \(k\)FN queries required by MOFA and the conventional algorithm for answering the M\(k\)FN query. MOFA requires only two \(k\)FN queries to be evaluated to compute the valid segments for the query segment. However, the conventional algorithm requires \(k\)FN queries to be regularly evaluated to refresh the query results as the query point moves. In other words, the conventional algorithm evaluates a number of \(k\)FN queries linearly proportional to the query frequency, whereas MOFA evaluates only two \(k\)FN queries, regardless of the query frequency, as the query point moves within a query segment. Figure 14a presents the query execution times of MOFA and the conventional algorithm when the number of facilities varies from 1000 to 5000 (i.e., \(10^{3}\leq|F|\leq 5\times 10^{3}\)). In all cases of \(|F|\), MOFA \begin{table}
\begin{tabular}{l l} \hline \hline
**Parameter** & **Range** \\ \hline Number of query points (\(|Q|\)) & 10 \\ Number of facilities (\(|F|\)) & 1, 2, 3, 4, 5 (\(\times 10^{3}\)) \\ Number of FNs required (\(k\)) & 1, 2, 4, 8, 16 \\ Query frequency in the query segment (\(Q_{F}\)) & 2, 4, 8, 10, 20 \\ Distribution of facilities & Gaussian distribution \\ Number of centroids for the facilities in \(F\) (\(|C|\)) & 1, 3, 5, 7, 10 \\ Standard deviation for the normal distribution (\(\sigma\)) & \(10^{-2}\) \\ Road network & SJ, NA, SF \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Empirical settings. \begin{table}
\begin{tabular}{l l l l l} \hline \hline
**Road Network** & **Description** & **Vertices** & **Edges** & **Vertex lists** \\ \hline SJ & City streets in San Joaquin, California & 18,263 & 23,874 & 20,040 \\ NA & Highways in North America & 175,813 & 179,179 & 12,416 \\ SF & City streets in San Francisco, California & 174,956 & 223,001 & 192,276 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Real road networks. outperforms the conventional algorithm. For this empirical study, 10 query points were considered with each query point evaluating eight \(k\)FN queries while moving along its query segment. Therefore, the MOFA and conventional algorithms evaluated 20 and 80 \(k\)FN queries, respectively. Figure 13(b) presents the query execution times when the number of FNs required varies from 1 to 16 (i.e., \(1\leq k\leq 16\)). For all cases of \(k\), MOFA is approximately four times faster than the conventional algorithm. The query execution times of MOFA and the conventional algorithms are stable, regardless of \(k\). This is because \(k\)FN query evaluation sorts facility clusters based on their distances to the query point and processes the sorted facility clusters. Figure 13(c) presents the query execution times when the query frequency varies from 2 to 20 (i.e., \(2\leq Q_{F}\leq 20\)). The query execution time of MOFA is stable and independent of the query frequency, whereas that of the conventional algorithm increases with the query frequency. Figure 13(d) presents the query execution times when the number of centroids for the facilities in \(F\) varies from 1 to 10 (i.e., \(1\leq|C|\leq 10\)). The \(k\)FN query execution time tends to increase with the \(|C|\) value. This is because the facilities become more widely distributed as the \(|C|\) value increases, resulting in an increase in query execution time. Figure 15 compares the performance of MOFA and the conventional algorithm on the NA road network. The empirical results obtained using the NA road network exhibit performance patterns similar to those obtained using the SJ road network. Figure 14(a) presents the query execution times for \(10^{3}\leq|F|\leq 5\times 10^{3}\). MOFA is four times faster than the conventional algorithm. Figure 14(b) presents the query execution times for \(1\leq k\leq 16\).