# Efficient Top-\(k\) Spatial Dataset Search Processing
## 6 The Optimized Search Scheme
### GMBR-Based Optimization Strategy  
The closer spatial datasets tend to cover more areas of rectangle overlap. For an exemplar dataset and a spatial dataset, if their minimum covering rectangles do not overlap, then the similarity between them is zero and the spatial dataset is not likely to be the finalsearch result. We use rectangles to enclose all grids in the MCG of a spatial dataset and propose an optimization search strategy.  
**Definition 5** (Grid-based Minimum Bounding Rectangle, GMBR).: _Given a spatial dataset \(S_{i}\in\mathcal{S}\) and its corresponding MCG \(M_{i}\), the GMBR of \(S_{i}\) is a rectangle just covering all grids in \(M_{i}\). Assuming that the bottom-left and upper-right grids in the rectangle are \(g_{x,y}\) and \(g_{u,v}\), respectively, the GMBR can be represented as a coordinate pair,_  
\[E_{i}=\{(x,y),(u,v)\}. \tag{9}\]  
_The GMBR set corresponding to the spatial data repository \(\mathcal{S}\) is denoted as \(\mathcal{E}=\{E_{i}|S_{i}\in S\}\)._  
**Lemma 1**.: _Assuming that \(S_{i}\) and \(S_{j}\) are two spatial datasets, and \(E_{i}\) and \(E_{j}\) are the corresponding GMBRs, respectively, when \(E_{i}\) and \(E_{j}\) have no overlap GMBR area, the similarity between \(S_{i}\) and \(S_{j}\) is 0, i.e.,_  
\[Sim(S_{i},S_{j})=0. \tag{10}\]  
Proof.: According to Definition 5, if \(E_{i}\) has no overlap GMBR area with \(E_{j}\), then for any grids \(g_{x,y}\in E_{i}\), we have \(g_{x,y}\
otin E_{j}\). Thus, according to the similarity calculation in Definition 4, \(T\) is an empty set and thus \(DSim\) and \(QSim\) are both 0, leading to \(Sim(S_{i},S_{j})=0\). Thus, Lemma 1 is proved.  
According to Lemma 1, for any spatial dataset \(S_{i}\), if it has no overlapping area with the GMBR of the exemplar dataset \(S_{e}\), the similarity between them is zero. During the dataset search processing, such datasets contribute nothing to the search result and can be filtered out directly without any similarity calculation. Thus, the GMBR-based optimization strategy can be used to filter out spatial datasets with zero similarity to the exemplar dataset. The details of the overlap check processing are outlined in Algorithm 2.  
```
Input: The GMBR of the dataset \(S_{i}\) and the exemplar dataset \(S_{e}\), \(E_{i}\) and \(E_{e}\), respectively. Output:\(true/false\), representing whether \(E_{i}\) overlaps with \(E_{e}\).
1 Get the bottom-left and upper-right coordinates \(\{(x_{i},y_{i}),(u_{i},v_{i})\}\) of \(E_{i}\);
2 Get the bottom-left and upper-right coordinates \(\{(x_{e},y_{e})\) and \((u_{e},v_{e})\}\) of \(E_{e}\);
3 if\(x_{i}>u_{e}\lor y_{i}>v_{e}\lor u_{i}<x_{e}\lor v_{i}<y_{e}\)then
4 return\(false\)
5 else
6 return\(true\)
```  
**Algorithm 2**_CheckGMBR(\(E_{i}\), \(E_{e}\))_  
In Algorithm 2, the GMBRs of the spatial dataset in the data repository and the exemplar dataset are inputted and their bottom-left and upper-right coordinates are used to check if there is overlapping GMBR area. If there is, the output is \(true\), otherwise \(false\), thereby reducing the number of similarity calculations and improving search efficiency. By checking whether the GMBRs overlap, we can quickly filter out datasets that are unlikely to be search results, thereby reducing the number of similarity calculations and improving search efficiency.