## 3 Preliminaries
### NN and RNN Query  
Before introducing nearest neighbor (NN) and reverse nearest neighbors (RNN), it is essential to first understand Euclidean distance. Euclidean distance [24] is a metric that can be used to calculate nodes of different dimensions in order to measure the length between nodes. Based on [25], the Euclidean distance \(dist(a,b)\), with the two-dimensional points \(a=(x_{1},y_{1})\) and \(b=(x_{2},y_{2})\), could be determined as follows:  
\[dist(a,b)=\sqrt{(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}} \tag{1}\]Generally speaking, nearest neighbor (NN) [8; 26] query has garnered widespread attention in the spatial database research community. For example, when point A is closer to point B than other points, we say that point A is the nearest neighbor of point B. Conversely, we also refer to point B as one of the reverse nearest neighbors (RNN) of point A. In other words, an RNN query identifies a set of points for which the query point serves as their nearest neighbor, i.e., it calculates the Euclidean distance between the query point and other points. The RNN query was first proposed in [16]. There are two variants of RNN queries [9]: a monochromatic version and a bichromatic version. Given a facility \(\mathcal{F}\), that is, a location of the \(\mathcal{F}\), the bichromatic RNN query finds the set of objects that has \(\mathcal{F}\) as the nearest neighbor. Please note that we typically assume, in optimal location query scenarios, that each object prefers the nearest facility.  
**Definition 1** (RNN query).: _Given a set of facility locations \(\mathcal{F}=\{f_{1},f_{2},\ldots,f_{\mathrm{s}}\}\), the purpose of the RNN query is to find RNNQ(\(\mathcal{F}\))=\(\{num_{j}=|\{l_{i}|l_{i}\text{ is RNN of }f_{j}\}|,\,1\leq j\leq s,\,\text{where }l_{i}\) represents the location of customer \(x_{i}\) and \(|\cdot|\) denotes the cardinality of a set. In other words, it aims to determine the cardinality of the reverse nearest neighbors (RNNs) for each facility \(f_{j}\)._  
For a RNN query, the query result \(Q=RNNQ(\mathcal{F})\) is an \(s\)-vector (ordered set) of RNN cardinalities, where the largest element in the vector of size \(s\) corresponds to the facility that is the optimal facility location; in other words, the facility that attracts the maximum number of customers.  
However, when the vector of two facilities share the same cardinality (e.g., \(num_{j_{1}}=num_{j_{2}}\), \(1\leq j_{1}\
eq j_{2}\leq s\)), the tie has to be broken. Generally, the customers prefer the facility closer to them because they can utilize it more easily. Thus, we employ the accumulated distance from all customers \(l_{i}\) to the locations \(f_{j}\) in its facility set \(\mathcal{F}\), denoted as \(D_{j}=\sum_{l_{i}\in n}d(l_{i},f_{j})\), as the tie breaker. The \(n\) is the number of customers. The smaller the \(D_{j}\) is, the better the \(f_{j}\)'s optimality is.  
**Definition 2** (AVG query).: _Given a set of facility locations \(\mathcal{F}=\{f_{1},f_{2},\ldots,f_{\mathrm{s}}\}\), the AVGQ query intends to find the following:_  
\[AVGQ(\mathcal{F})=\frac{\sum_{l_{i}\in n}d(l_{i},f_{j})}{n} \tag{2}\]  
_where \(f_{i}\) is the NN of \(l_{i}\), and \(d(l_{i},f_{i})\) means the Euclidean distance between \(l_{i}\) and \(f_{i}\). In other words, it aims to compute the average distance between all customers and their nearest facilities._  
**Definition 3** (MAX query).: _Given a set of facility locations \(\mathcal{F}=\{f_{1},f_{2},\ldots,f_{\mathrm{s}}\}\), the MAXQ query aims to identify MAXQ(\(\mathcal{F})=max(d(l_{i},f_{i}))\), where \(f_{i}\) is the NN of \(l_{i}\). In other words, it aims to find the maximum distance between a customer and their nearest facilities._