# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/by/creativecommons.org/licenses/by/creativecommons](https://creativecommons.org/licenses/by/creativecommons.org/licenses/by/creativecommons)]([https://creativecommons.org/licenses/by/creativecommons.org/licenses/by/creativecommons](https://creativecommons.org/licenses/by/creativecommons.org/licenses/by/creativecommons)).  
distance from a query point \(q\) to each facility \(f\) in \(F\). An additional \(O(|F|\cdot\log|F|)\) time is required to retrieve the \(k\) facilities farthest from \(q\). However, this simple solution cannot be used in practical applications because \(k\)FN queries should be regularly evaluated to refresh the query results while \(q\) moves continuously. Therefore, this study proposes a moving farthest search algorithm called MOFA that enables the efficient evaluation of M\(k\)FN queries in road networks. MOFA computes the valid segments for the query segment in which the query point \(q\) moves such that it does not repeatedly retrieve candidate facilities whenever \(q\) moves. To this end, MOFA quickly retrieves the candidate facilities for the query segment and computes the valid segments using the candidate facilities. Each query location in the valid segment has the same \(k\) facilities farthest from the query location.  
Figure 2 presents an example of an M\(k\)FN query, where \(q\) moves along query segment \(\overline{q_{s}q_{e}}\). First, the moving query point \(q\) submits a query segment \(\overline{q_{s}q_{e}}\) to the location-based service (LBS) server, instead of the current \(q\) location. Next, the LBS server returns a set of valid segments for \(\overline{q_{s}q_{e}}\), where each valid segment has the same \(k\) facilities farthest from each query location in the valid segment. This study assumes that query points (e.g., vehicles and pedestrians) move, while facilities (e.g., garbage incinerators and chemical plants) are stationary. To the best of our knowledge, this is the first attempt to study the efficient processing of M\(k\)FN queries in road networks.  
The main contributions of this study are summarized below.  
Figure 1: Example of M\(k\)FN queries in a road network.  
Figure 2: Interaction between the moving query point \(q\) and location-based service (LBS) server while \(q\) moves along \(\overline{q_{s}q_{e}}\).  
* This study proposes MOFA to compute valid segments for the query segment in which a query point moves.
* MOFA retrieves candidate facilities once and has a stable query processing time that is independent of the query frequency.
* An extensive empirical evaluation is performed using real-world road networks to demonstrate the superiority of MOFA compared to a conventional solution.  
The remainder of this paper is organized as follows. Section 2 reviews the related research. Section 3 describes the M\(\&\)FN query problem and notation used in this study. Section 4 describes the clustering of facilities and calculation of distances between facility clusters and a border point. Section 5 presents MOFA for M\(\&\)FN query processing in road networks, and Section 6 evaluates an example of M\(\&\)FN query using MOFA. Section 7 presents the empirical results obtained using MOFA and conventional algorithms with different setups, and Section 8 summarizes our conclusions.