# Efficient Top-\(k\) Spatial Dataset Search Processing
## 6 The Optimized Search Scheme
### The Optimized Search Algorithm
The search efficiency of five schemes is evaluated, where KSDS is the baseline search scheme, KSDS+ is the optimized search scheme and KSDS-GMBR and KSDS-Pooling are the addition of GMBR-based and Pooling-based optimization strategies to the baseline scheme, respectively. Figures 10-14 illustrate the search time cost of KSDS, KSDS+ and EMD as the parameters \(\sigma\), \(k\), \(n\), \(u\) vary. The variation in the search time cost with \(\sigma\) is shown in Figure 10, from which it can be concluded that the difference \(\sigma\) has almost no effect on search efficiency. This is because \(\sigma\) only affects the result of similarity calculation between datasets, but not the efficiency of similarity calculation, and thus does not affect the spatial dataset search efficiency. The variation in the search time cost with \(k\) is shown in Figure 11, from which it can be concluded that the search time cost is almost the same at different \(k\). This is because \(k\) is only used in the sorting phase to select the top-\(k\) similarity datasets. However, the time overhead of the sorting phase is only a very small fraction of the time overhead of the total search. Therefore, the different \(k\) has little effect on the spatial dataset search efficiency. The variation in the search time cost with \(n\) is shown in Figure 12, from which it can be concluded that as the number of datasets \(n\) increases, the search time cost increases. This is because increasing \(n\) incurs more similarity calculations, which reduces the search time cost. Figure 11: Time cost versus \(k\). Figure 10: Time cost versus \(\sigma\). The variation in the search time cost with \(u\) is shown in Figure 13, from which it can be concluded that as the grid threshold \(u\) increases, the search time overhead increases. This is because an increase in \(u\) divides the spatial space into more grids, requiring more grids to be involved in similarity calculation. This increases the time cost of similarity calculation and, therefore, decreases the search efficiency. The relationship between search time cost and \(\epsilon\) is illustrated in Figure 14. It can be observed that the search efficiency of KSDS and KSDS-GMBR remains unchanged as \(\epsilon\) varies. This is because \(\epsilon\) only influences KSDS-Pooling and KSDS+, thereby affecting their search efficiency. As \(\epsilon\) changes, the search efficiency of KSDS-Pooling and KSDS+ exhibits a decreasing trend followed by an increase. From the results, we identify the optimal values of \(\epsilon\) that minimize the search time overhead for the two data repositories, Public and Identifiable, which are \(\epsilon=4\) and \(\epsilon=7\), respectively. From Figures 10-14, it can be observed that under the default parameters, KSDS+ consistently achieves the highest search efficiency. KSDS-GMBR and KSDS-Pooling exhibit different optimization capabilities, with their effectiveness varying across different datasets. Figure 14: Time cost versus \(\epsilon\). Figure 5:0 Time cost versus \(n\). Figure 5:1 Time cost versus \(u\). Specifically, KSDS-GMBR demonstrates superior optimization performance when datasets in the data warehouse are spatially distant from each other. Meanwhile, KSDS-Pooling enhances search efficiency when datasets are spatially close to each other and contain sparse internal data points. Therefore, the combined use of these two approaches is a good choice to enhance search performance. ### Space Cost Evaluation

This subsection evaluates the pooling index space cost for performing spatial dataset searches. We mainly consider the space cost changes induced by the pooling index when the pooling threshold changes and select the appropriate pooling threshold in conjunction with the evaluation of the search efficiency in Figure 5:2

The relationship between the space cost of the index is depicted in Figure 5:3 As \(\epsilon\) increases, the index space cost also increases because a finer grid partition creates more index entries, consuming more storage.