# Efficient Top-\(k\) Spatial Dataset Search Processing
## 6 The Optimized Search Scheme
### The Optimized Search Algorithm  
During the above optimization strategies for the baseline search scheme, the GMBR and the pooling index are used to accelerate dataset filtering, thus speeding up the search process. Adopting the above optimization strategies, we present an optimized spatial dataset search process (KSDS+). The GMBR-based optimization strategy has a lower time overhead, but cannot fine-grained filter out spatial datasets with zero similarity to the exemplar dataset, while the pooling-based optimization strategy achieves the opposite. Thus, the steps of the KSDS+ search processing we designed are as follows:  
* _CheckGMBR_. Determine whether each dataset has GMBR overlap with the exemplar dataset according to GMBR-based optimization strategy. * _CheckPool_. Assess whether each dataset has a grid pool that overlaps with the exemplar dataset according to the pooling-based optimization strategy. * _Search_. Calculate the similarity between each dataset that satisfies the \(CheckPool\) and the exemplar dataset according to GDSS, and select the top-\(k\) datasets with the highest similarity to the exemplar dataset. Since both of our proposed optimization strategies specifically filter out datasets with a similarity score of zero, our two optimization strategies effectively improve the efficiency of spatial dataset search while ensuring accurate search. Additionally, the GMBR-based optimization strategy has better adaptability to situations where the data repository covers a large area and the datasets are relatively scattered, while the grid pooling-based optimization strategy can make up for the shortcomings of the GMBR-based optimization strategy when the datasets are relatively concentrated. Therefore, we recommend combining these two optimization schemes in practical applications to achieve better optimization results. Based on the above analysis, we can first use the GMBR-based optimization strategy to quickly filter out datasets with zero similarity, then use the pooling-based optimization strategy to filter out the remaining datasets with zero similarity and finally perform similarity calculations to complete the search. Details of the optimized spatial dataset search processing are presented in Algorithm 5. In Algorithm 5, the GMBR, the grid distribution representation and the MCG are first generated for the exemplar dataset. Then, for each dataset in the data repository, it is checked whether there is an overlap between its GMBR and the exemplar dataset. If an overlap exists, the dataset is further checked for overlap between its grid pool and the exemplar dataset. For each dataset that satisfies these conditions, a priority queue is then initialized to store the dataset along with its similarity to the exemplar spatial dataset. A new similarity-dataset pair is inserted, and the queue is updated only if the number of pairs in the priority queue is less than \(k\), or if the minimum similarity in the queue is lower than the newly calculated similarity. Finally, the spatial datasets in the queue are the requested spatial datasets. According to the search-processing procedures, the time complexity of the optimized search algorithm (KSDS+) is \(O(n+\eta(\alpha^{\prime}+\beta^{\prime})+\eta^{\prime}(\alpha+\beta+\log k))\). Here, \(\eta^{\prime}\) is the number of datasets that satisfy step \(CheckPool\), \(\alpha^{\prime}\) and \(\beta^{\prime}\) are the average numbers of grid pools in \(MCG^{\epsilon}\) of exemplar datasets and spatial datasets, respectively. The meanings of \(\alpha\), \(\beta\), \(n\), \(k\), \(\eta\) are the same as in Section 5. ``` Input: The number of requested datasets \(k\), the exemplar dataset \(S_{e}\), the spatial data repository \(\mathcal{S}\), the GMBR set \(\mathcal{E}\) and the pooling index \(\mathcal{I}^{\epsilon}=(I_{u}^{\epsilon},I_{l}^{\epsilon})\) Output: The search result \(R\).