# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
## 4 Clustering Facilities and Computing Distances
### Clustering Facilities into Facility Clusters  
Figure 3 presents an example MKFN query \(q\), where \(k=2\) and \(F=\{f_{1},f_{2},\cdots,f_{6}\}\). This example is used to elaborate the solution process. The example MKFN query requires that the moving query point \(q\) constantly retrieves the two facilities farthest from itself. The vertex list in which query point \(q\) moves is referred to as the query segment for \(q\). In this example, \(\overline{v_{1}v_{2}}\) is the query segment for \(q\) (Figure 3). For ease of identification, the query segment is shown in bold.  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**References** & **Space Domain** & **Query Type** \\ \hline
[3; 4; 5; 6; 7; 8] & Euclidean space & Reverse FN query \\
[1; 4; 10; 11; 12; 14] & Euclidean space & FN query \\
[2] & Euclidean space & Aggregate FN query \\
[5; 7] & Road network & Reverse FN query \\
[6] & Road network & Aggregate FN query \\
[20] & Road network & FN join query \\
[21] & Road network & Multiple FN query \\ This study & Road network & Moving FN query \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison between our problem scenario and those of previous studies.  
Figure 4 illustrates the segmentation of a road network. In this figure, the intersection vertices corresponding to road intersections are marked using dashed circles. The example road network contains six intersection vertices \(v_{1}\), \(v_{2}\), \(v_{3}\), \(v_{4}\), \(v_{5}\), and \(f_{5}\). The degrees are represented by numbers in parentheses. In this study, a road network is split into vertex lists using intersection vertices. Therefore, facility segments adjacent to an intersection vertex are grouped into a facility cluster, as illustrated in Figure 5.  
Figure 5 illustrates the clustering method for grouping facilities into facility clusters. The clustering method first groups facilities in a vertex list into a facility segment. Adjacent facility segments are then grouped into a facility cluster. First, the facilities \(f_{1}\), \(f_{2}\), and \(f_{3}\) in a vertex list \(\overline{v_{3}f_{2}v_{5}}\) are connected to form a facility segment \(\overline{f_{1}f_{2}f_{3}}\). Similarly, the facilities \(f_{4}\) and \(f_{5}\) in the vertex list \(\overline{f_{5}v_{4}}\) are connected to form a facility segment \(\overline{f_{4}f_{5}}\). Therefore, there are three facility segments \(\overline{f_{1}f_{2}f_{3}}\), \(\overline{f_{4}f_{5}}\), and \(f_{6}\) (Figure 5a). Next, the two facility segments \(\overline{f_{4}f_{5}}\) and \(f_{6}\) are connected using the intersection vertex \(f_{5}\) to form a facility cluster \(\{\overline{f_{4}f_{5}},\overline{f_{5}f_{6}}\}\). Therefore, a set of facilities \(F=\{f_{1},f_{2},\cdots,f_{6}\}\) changes into a set of facility clusters \(\overline{F}=\{\{\overline{f_{1}f_{2}f_{3}}\},\{\overline{f_{4}f_{5}}, \overline{f_{5}f_{6}}\}\}\). In the proposed method, facility segments constitute a facility cluster, which is represented by a set of facility segments.  
Figure 4: Segmentation of an example road network using road intersections.  
Figure 3: Example of an MkFN query \(q\) in a road network.