# Efficient Top-\(k\) Spatial Dataset Search Processing
## 6 The Optimized Search Scheme
### The Optimized Search Algorithm
1 Initialize \(R=\varnothing\) and \(\mathcal{Q}=\varnothing\), where \(\mathcal{Q}\) is a priority queue for storing similarity and dataset pairs ordered by the similarities;
2 Generate the GMBR \(E_{e}\), the grid distribution representation \(D_{e}\) and the \(\text{MCG}^{\epsilon}\)\(M_{e}^{\epsilon}\) for \(S_{e}\);
3 foreach\(S_{i}\in\mathcal{S}\)do
4 Get the corresponding \(E_{i}\), \(P_{i}\) and \(D_{i}\) from \(\mathcal{E}\), \(I_{u}^{\epsilon}\) and \(I_{l}^{\epsilon}\), respectively;
5 if\(CheckG\)\(\text{\emph{MBR}}(E_{i},E_{e})\)then
6 if\(CheckPool(P_{i},M_{e}^{\epsilon})\)then
7 Calculate the similarity\(sim_{i}=Sim(\mathcal{S}_{e},\mathcal{S}_{i})\);
8 if\(|\mathcal{Q}|<k\)then
9 Add the pair \((sim_{i},S_{i})\) into \(\mathcal{Q}\);
10 else
11 Get the pair \((sim_{j},S_{j})\) from \(\mathcal{Q}\) where \(sim_{j}\) is the minimum;
12 if\(sim_{i}>sim_{j}\)then
13 Remove \((sim_{j},S_{j})\) from \(\mathcal{Q}\);
14 Add \((sim_{i},S_{i})\) into \(\mathcal{Q}\);
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
310
320
334
34
35
36
37
38
39
40
411
42
43
445
46
47
48
490
50
510
520
531
540
541
552
562
573
584
591
60
610
620
632
642
643
654
655
666
67
688
692
70
7100
7101
7102
711
720
735
746
757
76
778
799
800
9100
9211
935
947
958
96
979
980
990
1001
1011
1011
1111
1111
112
112
113
114
115
116
117
117
118
1191
120
1214
1221
1231
124
125

## 7 Performance Evaluation

In this section, we first introduce the experimental settings. Then, we perform a comprehensive evaluation of the proposed search schemes KSDS and KSDS+, comparing them with the EMD-based search scheme [10]. The evaluation contains search effectiveness evaluation, search efficiency evaluation and space cost evaluation. ### Settings

Datasets. The proposed schemes are evaluated on two real-world spatial data repositories, Public and Identifiable, which are collected from OpenStreetMap [10]. The details of the spatial data repositories are introduced in Table 1.

* Implementation. The tested search schemes are implemented in the hardware environment with an Intel i7-8550U CPU, 128 GB memory and 1 TB hard disk and in the software environment with a 64-bit Windows 10 operating system and the Python 3.1 development kit. * Exemplar Datasets. For each search processing, we randomly select a dataset from a spatial data repository as the exemplar dataset and take the average result of 100 searches as the final search result. * Data preprocessing. As the data owner, we generate GMBR and MCGe for each spatial dataset in the repository to construct GMBRs and grid pooling indexes. These indexes efficiently organize and manage the datasets, enhancing search and retrieval processes within the spatial data repository. * Parameter settings. The parameters include \(\sigma\), \(k\), \(n\), \(u\) and \(\epsilon\), of which \(\epsilon\) is assigned 14 parameter values and the remaining parameters are assigned 5 experimental values. The parameter settings of our evaluations are presented in Table 2 and the underlined parameter values are the default parameter values. ### Search Effectiveness Evaluation

This subsection evaluates the effectiveness of algorithms KSDS, KSDS+ and EMD for performing spatial dataset searches, with MSE as a metric to evaluate the effectiveness of search results. To calculate the MSE, we first perform \(k\)-means clustering on the points in the exemplar dataset to determine the cluster centers. Subsequently, we compute the average distance from each point in the search results to its nearest cluster center. The MSE quantifies the average distance between the location points of the search results and those of the \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Data Repository** & **Storage (GB)** & **Number of Datasets** & **Number of Points** \\ \hline Public & 29.43 & 546,193 & 13,747,735 \\ Identifiable & 19.64 & 235,483 & 13,043,935 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Details of spatial data repositories.