# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
## 5 MOFA Algorithm for M\(k\)FN Query Processing in Road Networks  
Algorithm 1 presents the MOFA algorithm, which has three steps. The first step groups facilities into facility clusters using the clustering method described in Section 4.1; therefore, a set \(F\) of facilities changes to a set \(\overline{F}\) of facility clusters. The second step retrieves the candidate facilities for a query segment \(\overline{q_{s}q_{e}}\), which are retrieved from border points \(q_{s}\) and \(q_{e}\). To this end, the \(find\_candidates\) function is called from \(q_{s}\) (\(q_{e}\)), whose result is stored to \(\Sigma(q_{s})\) (\(\Sigma(q_{e})\)). In the third step, the valid segments for \(\overline{q_{s}q_{e}}\) are computed using the candidate facilities in \(\Sigma(q_{s})\cup\Sigma(q_{e})\). Note that \(\Phi(\overline{q_{s}q_{e}})\) includes valid segments for \(\overline{q_{s}q_{e}}\) and the \(k\) facilities farthest from them. ```
0:\(k\): number of FNs requested for \(q\), \(\overline{q_{s}q_{e}}\); query segment, \(F\): set of facilities
0:\(\Phi(\overline{q_{s}q_{e}})\): query result for \(\overline{q_{s}q_{e}}\), i.e., \(\Phi(\overline{q_{s}q_{e}})=\) (\(\{q\),\(\Phi(q)\}\))\(|q\overline{q_{s}q_{e}}\))
1:\(f\) / Step 1: Facilities are grouped into facility clusters, which is explained in Section 4.1. 2:\(\overline{F}\) + \(cluster\_facilities(F)\) // Step 2: Candidate facilities for \(\overline{q_{s}q_{e}}\) are retrieved by border points, which is detailed in Algorithm 2. 3:\(\Sigma(q_{s})\gets find\_candidates(k,q_{s},len(\overline{q_{s}q_{e}}), \overline{F})\) // Candidate facilities for \(\overline{q_{s}q_{e}}\) are retrieved by \(q_{s}\). 4:\(\Sigma(q_{e})\gets find\_candidates(k,q_{e},len(\overline{q_{s}q_{e}}), \overline{F})\) // Candidate facilities for \(\overline{q_{s}q_{e}}\) are retrieved by \(q_{e}\). 5:\(\overline{Q}(q_{e})\gets compute\_valid\_segments(k,\overline{q_{s}q_{e}},\Sigma(q_{s})\cup\Sigma(q_{e}))\) return\(\Phi(\overline{q_{s}q_{e}})\) // \(\Phi(\overline{q_{s}q_{e}})\) is a set of valid segments, each of which has a set of \(k\) facilities for the valid segment. ```  
**Algorithm 1** MOFA\((k,\overline{q_{s}q_{e}},F)\). Algorithm 2 fetches a set of candidate facilities for the query segment \(\overline{q_{s}q_{e}}\). The set of candidate facilities for \(\overline{q_{s}q_{e}}\), \(\Sigma(q_{b})\), is initially set to the empty set (Line 1). The candidate distance is initially set to \(d_{\mathit{camd}}(q_{b})=0\) and used to determine whether or not \(f\) is a candidate facility for \(\overline{q_{s}q_{e}}\). The largest distance from \(q_{b}\) to each facility cluster in \(\overline{F}\) is computed and elaborated in Section 4.2. We then arrange the facility clusters in a descending order based on their largest distance to \(q_{b}\). The arranged facility clusters are investigated one by one. The remaining facility clusters to be examined do not need to be accessed if \(d_{\mathit{max}}(q_{b},\overline{F_{C}})<d_{\mathit{camd}}(q_{b})\), that is, the largest distance from \(q_{b}\) to the next facility cluster \(\overline{F_{C}}\) is smaller than the candidate distance. This is because the remaining facilities cannot be candidate facilities for \(\overline{q_{s}q_{e}}\). Otherwise (i.e., \(d_{\mathit{max}}(q_{b},\overline{F_{C}})\geq d_{\mathit{camd}}(q_{b})\)), each facility \(f\) in \(\overline{F_{C}}\) must be investigated to determine whether or not \(f\) is a candidate facility for \(\overline{q_{s}q_{e}}\). For this, \(d(q_{b},f)\) should be computed. If \(q_{b}\) is enclosed by \(\overline{F_{C}}\), the distance from \(q_{b}\) to \(f\) is calculated using a graph traversal algorithm such as the A* search algorithm [27]; otherwise (i.e., unless \(q_{b}\) is enclosed by \(\overline{F_{C}}\)), the distance is evaluated as \(d(q_{b},f)\leftarrow\)_min_\(\{d(q_{b},f_{b})+d(f_{b},f)|f_{b}\in B(\overline{F_{C}})\}\) because a border point \(f_{b}\) of \(\overline{F_{C}}\) must be in the path from \(q_{b}\) to \(f\), i.e., \(q_{b}\to f_{b}\to f\).