# The Efficient Processing of Moving \(k\)-Farthest Neighbor Queries in Road Networks +
## 2 Related Works  
Many studies have been conducted on the efficient processing of spatial queries based on the FN search [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12]. **Reverse FN (RFN) query**[3; 4; 5; 7; 8; 9; 13]. Given a set of facilities \(F\) and a query point \(q\), an RFN query retrieves the facilities in \(F\) that have \(q\) as their farthest neighbor. Recently, RFN queries have attracted increasing attention based on their applicability. Several studies have been conducted to efficiently evaluate RFN queries in Euclidean spaces [3; 4; 8; 9; 13] and road networks [5; 7]. **Approximate FN query**[1; 10; 11; 14]. Given an approximation ratio \(c\) (\(c>1\)) and success probability \(\delta\), a \(c\)-approximate FN query retrieves the \(c\)-approximate farthest neighbors with a confidence of at least \(\delta\). Approximate FN search algorithms are considered acceptable in high-dimensional spaces because it is typically not feasible to return the exact farthest neighbors in a large set of points. [PERSON] et al. [10; 14] developed a reverse-query-aware locality-sensitive hashing scheme for high-dimensional \(c\)-approximate FN searches over external memory. They also proposed a heuristic variant that applied data-dependent object selection to reduce the number of data objects. [PERSON] et al. [11] proposed a \(c\)-approximate FN algorithm called reverse incremental locality-sensitive hashing for high-dimensional data that employs a continuous search strategy for each projection dimension. **Aggregate FN query**[2; 6]. Given a set of query points \(Q\) and an aggregate function (e.g., min, max, and sum), the aggregate FN query retrieves a facility \(f\) from a set of facilities \(F\) such that the aggregate distance from \(f\) to all query points in \(Q\) is maximized. [PERSON] et al. [2] studied the aggregate FN query in Euclidean space and proposed the smallest-bounding and best-first algorithms. [PERSON] et al. [6] presented effective solutions to aggregate FN queries in road networks. **Moving spatial query**[15; 16; 17; 18]. Various types of moving spatial queries have been studied extensively, including \(k\)NN [15; 16; 17] and range [18] queries. [PERSON] et al. [17] developed an incremental safe region-based technique known as the \(V^{*}\)-diagram to process moving \(k\)NN queries in Euclidean space and in undirected spatial networks. [PERSON] et al. [18] proposed an algorithm for computing the boundaries, which are referred to as safe exits, of the safe regions of moving-range queries in road networks. The associated studies considered different problem scenarios from those in our study, and their solutions were found to be inappropriate for our problem scenarios. Spatial access methods based on Euclidean distance cannot process M\(\&\)FN queries in road networks because network distance evaluation is much more expensive than Euclidean distance evaluation. Solutions for the M\(\&\)NN search [15; 16; 17] are not applicable to M\(\&\)FN query settings because M\(\&\)FN queries focus on the farthest neighbors, rather than the nearest neighbors. This is an extended version of a preliminary conference report presented at the KSCI Summer Conference 2021 [19]. The preliminary conference report [19] describesthe key concepts of MOFA without empirical evidence. Therefore, in this study, MOFA was thoroughly analyzed and an empirical evaluation was performed. This study also differs from our previous studies [20; 21] in several aspects. [PERSON] [20] considered \(k\)FN join queries in a spatial network. The \(k\)FN join query focuses on evaluating a snapshot of the \(k\)FN query for each query point in \(Q\). [PERSON] and [PERSON] [21] presented the group processing of multiple \(k\)FN (GMP) algorithms to efficiently process multiple \(k\)FN queries in road networks. The GMP algorithm exploits shared computation techniques to rapidly process snapshot \(k\)FN queries for multiple query points with distinct query conditions.