# Efficient Top-\(k\) Spatial Dataset Search Processing
## 6 The Optimized Search Scheme
### Grid Pooling-Based Optimization Strategy  
The GMBR-based optimization strategy can quickly filter out far-apart datasets that do not overlap with the exemplar dataset. However, there are still datasets that, despite having an overlap area with the exemplar dataset, yield a similarity score of 0. This occursbecause GMBR only takes into account the proximity of the dataset as a whole, and does not take into account the proximity of the dataset in a finer-grained grid. For example, as shown in Figure 3, In cases where the similarity between two datasets is zero, which is unlikely to represent a final search result, the GMBR strategy alone proves inadequate for efficient filtering. This stems from GMBR's aggregate-based perspective, which hinders swift exclusion of such datasets. To achieve finer-grained filtering, we propose a pooling-based optimization strategy as follows. **Definition 6** (\(\epsilon\)-Grid Pooling). : _Given a two-dimensional spatial space \(G\) which is equally divided into \(2^{u}\times 2^{u}\) grids, and a grid pooling threshold \(\epsilon\)\((1\leq\epsilon\leq u-1)\), the \(\epsilon\)-grid pooling performs grid pooling on \(G\) to equally generate \(2^{u-\epsilon}\times 2^{u-\epsilon}\) grid pools, i.e.,_  
\[G=\Big{\{}g_{x,y}^{\epsilon}|x,y\in\{1,2,\cdots,2^{u-\epsilon}\}\Big{\}}. \tag{11}\]  
According to Definition 6, we have the following observations:  
* Each grid pool \(g_{x,y}^{\epsilon}\in G\) contains \(2^{\epsilon}\times 2^{\epsilon}\) grids. * The grid pool \(g_{x,y}^{\epsilon}\) that contains grid \(g_{c,j}\) can be quickly located using the equation: \((x,y)=(\lfloor\frac{\epsilon}{\mathcal{S}}\rfloor,\lfloor\frac{j}{\mathcal{S} }\rfloor)\). **Definition 7** (\(\epsilon\)-minimum Covered Grid Pool Collection). : _Given a spatial dataset \(S_{i}\in\mathcal{S}\) and corresponding \(\text{MCG}\ M_{i}\), the minimum covered grid pool collection (\(\text{MCG}^{\epsilon}\)) of \(S_{i}\) after \(\epsilon\)-grid pooling, denoted as \(M_{i}^{\epsilon}\), is the minimum set of gird pools that can cover all grids in \(\text{MCG}_{i}\ M_{i}\),_  
\[M_{i}^{\epsilon}=\{g_{x,y}^{\epsilon}|g_{x,y}^{\epsilon}\in G\wedge\exists g_{ c,j}\in M_{i}\to g_{c,j}\leq g_{x,y}^{\epsilon}\}, \tag{12}\]  
_where \(g_{c,j}\leq g_{x,y}^{\epsilon}\) means that grid \(g_{c,j}\) is in the grid pool \(g_{x,y}^{\epsilon}\). The \(\text{MCG}^{\epsilon}\) set corresponding to spatial data repository \(\mathcal{S}\) is denoted as \(\mathcal{M}^{\epsilon}\)._  
**Definition 8** (\(\epsilon\)-pooling Index). : _Given a spatial data repository \(\mathcal{S}\) and the corresponding grid distribution representation set \(\mathcal{D}\), the \(\epsilon\)-pooling index \(\mathcal{I}^{\epsilon}=(I_{u}^{\epsilon},I_{l}^{\epsilon})\) is a two-layer index._  
* _The upper layer_ \(I_{u}^{\epsilon}\) _is a set of pair_ \((i,P_{i})\)_, where_ \(i\) _is the identifier of dataset_ \(S_{i}\in\mathcal{S}\) _and_ \(P_{i}\) _is the set of grid pools in_ \(\text{MCG}^{\epsilon}\ M_{i}^{\epsilon}\) _of_ \(S_{i}\)_._
* _The lower layer_ \(I_{l}^{\epsilon}\) _is a set of pairs_ \((i,D_{i})\)_, where_ \(i\) _is the identifier of dataset_ \(S_{i}\in\mathcal{S}\) _and_ \(D_{i}\) _is the set of triples in the grid distribution representation of_ \(S_{i}\) _defined in Definition_ 3_._  
Figure 3: An example of spatial datasets with zero similarity. We give an example of the \(\epsilon\)-pooling index, as shown in Figure 4. Figure 4 shows two spatial datasets under the \(4\times 4\) space grid partitioning, Figure 4 shows the pooling results for the \(\epsilon=2\) case and Figure 4 shows the generated two-layer pooling index. The details of building the \(\epsilon\)-pooling index are outlined in Algorithm 3. The spatial data repository and the grid pooling threshold are taken as input, and the corresponding grid distribution representation and \(\text{MCG}^{\epsilon}\) are generated. Then, the pairs in both the upper layer and lower layer in the index are acquired, and finally, the \(\epsilon\)-pooling index is generated.