# Efficient Top-\(k\) Spatial Dataset Search Processing
## 4 Grid Distribution-Based Spatial Dataset Similarity Measurement  
We assume that the two-dimensional spatial space is equally divided into \(2^{u}\times 2^{u}\) grids and the grid set is \(G=\{g_{x,y}|x,y\in\{1,2,\cdots,2^{u}\}\}\), where \(g_{x,y}\) is the grid at the \(x\)-th row and \(y\)-th column after space division. **Definition 2** (Minimum Covered Grid Collection, MCG). : _Given a spatial dataset \(S_{i}\in\mathcal{S}\), the minimum covered grid collection (MCG) of \(S_{i}\), denoted as \(M_{i}\), is the minimum set of girds that can cover all location points of \(S_{i}\),_  
\[M_{i}=\{g_{x,y}|g_{x,y}\in G\wedge\exists p_{i,c}\in S_{i}\to p_{i,c}\leq g_{x,y }\}, \tag{2}\]  
_where \(p_{i,c}\leq g_{x,y}\) means that the location point \(p_{i,c}\) is in the grid \(g_{x,y}\). The MCG set corresponding to spatial data repository \(\mathcal{S}\) is denoted as \(\mathcal{M}\)._  
**Definition 3** (Grid Distribution Representation of Spatial Dataset). : _Given a spatial dataset \(S_{i}\in\mathcal{S}\), the grid distribution of \(S_{i}\) is a set of triples, denoted as_  
\[D_{i}=\{T_{i,1},T_{i,2},\cdots,T_{i,|M_{i}|}\}, \tag{3}\]  
_where \(T_{i,j}\in D_{i}\) is a triple \((g,r,N)\), and \(T_{i,j}\).\(r\) and \(T_{i,j}\).\(N\) are the location density and the location quantity of the grid \(T_{i,j}\).\(g\), respectively. The calculation of \(T_{i,j}\).\(r\) is presented as follows,_  
\[T_{i,j}.r=\frac{T_{i,j}.N}{|S_{i}|}, \tag{4}\]  
_where \(|S_{i}|\) is the number of location points of \(S_{i}\). The grid distribution representation set corresponding to the spatial data repository \(\mathcal{S}\) is denoted as \(\mathcal{D}=\{D_{i}|S_{i}\in\mathcal{S}\}\)._  
According to Definitions 2 and 3, the minimum covered grid collection of a spatial dataset is the set of non-empty grids that have at least one location point of the spatial dataset, and only those non-empty grids are taken into the grid density distribution computation. We give an example to demonstrate the above definitions shown in Figure 2. A spatial space is divided into \(4\times 4\) grids, i.e., \(G=\{g_{x,y}|x,y\in\{1,2,3,4\}\}\). There are two spatial datasets \(S_{i}\) and \(S_{j}\) distributed in \(G\), and the corresponding grid density distributionsand \(D_{j}\) can be obtained by calculating the density and quantity of grids in the minimum covered grid collections \(M_{i}\) and \(M_{j}\), respectively. Because the area of each grid is relatively small, points within the same grid are close to each other. For different datasets, if they have points that fall within the same grid, they have a certain degree of similarity in that grid. The similarity between two spatial datasets needs to consider both the closeness of their density distributions of spatial points and the closeness in the number of spatial points they contain. We can measure the similarity of their density distributions using the density of the overlapping grids between two datasets, and measure the similarity of the number of points using the number of overlapping grids. A similarity regulator can be introduced to regulate the weights of two types of similarity, resulting in the following definition of similarity calculation. **Definition 4** (Grid Distribution-based Spatial Dataset Similarity, GDSS).