# Personalized Privacy Protection Based on Space Grid in Mobile Crowdsensing
## 4 Personalized Privacy Protection
### Personalized Private Space Decomposition Framework Design
#### 4.1.3 Spatial Grid Division Strategy  
When constructing a spatial index, it is necessary to organize each index into a grid containing a limited number of user nodes or a grid covering a small area, with each leaf node forming part of the subsequent tree structure. Drawing from index categories in the database, various forms of tree structure decomposition exist during spatial division:  
No data decomposition required. The tree structure after division is precisely defined, and the division's outcome relies solely on the definition of the tree structure. For instance, the quadtree is established by recursively dividing each node's region into four subregions of equal area [36]. Data decomposition required. This decomposition relies on the internal data of the node. For example, Hilbert R-tree: R-tree is a spatial decomposition formed by nested rectangles that may overlap. Hybrid tree. The definition of a hybrid tree is that the establishment of some level nodes needs data support and the division of the remaining level nodes does not need data support. The construction process of a hybrid tree needs to be designed in combination with a specific framework. When providing differential privacy protection for nodes in space, some researchers have adopted the above tree structure [34; 37]. It is common to use recursive partitioning to establish quadtree and k-d tree. Although effective in maintaining differential privacy protection, applying one-dimensional hierarchical methods to two-dimensional datasets often results in deeper trees. When dealing with massive data, the construction of spatial indexes can extend to more than ten levels, with grid divisions often operating at a scale level. Dynamic spatial meshing strategy AG: Reference [35] proposed an adaptive grid (AG) method. This method aims to divide areas with concentrated worker data into more subareas and areas with sparse worker data into fewer subareas. In other words, AG addresses the drawback of the unified grid (UG) by calculating the sizes of second-level grid cells at different levels based on the data of the upper-level node. The PSD algorithm in AG is introduced as follows: Firstly, we establish the root node of the mesh. Subsequently, we partition the root node into a grid of fixed size \(m_{1}\times m_{1}\). To introduce variability into the number of users in each grid cell, we add noise to the number of users in each grid cell by using Formula (5). The author of Reference [30] proposed the calculation formula for determining the granularity of the first-level grid node in AG, which is presented in Equation (7):  
\[m_{1}=\max\{10,\left[\frac{1}{4}\sqrt{\frac{N\times\varepsilon}{c}}\,\right]\} \tag{7}\]  
where \(N\) represents the number of data points on the workers' location grid. The authors of Reference [38] presented a substantial number of data. According to the experimental results, it was demonstrated that setting \(c=10\) yields improved division results. Subsequently, AG retrieves the count of workers in the first-level grids. With the number of these grids being \(m_{1}\times m_{1}\), we calculate the size of the second-level grid according to the number of query results. Each coarse-grained region is then adaptively subdivided into \(m_{2}\times m_{2}\) finer-grained areas. The calculation formula of \(m_{2}\) is as follows:  
\[m_{2}=\left[\sqrt{\frac{N^{\prime}\times\varepsilon\times(1-\alpha)}{c_{2}}}\,\right] \tag{8}\]  
To increase the granularity \(m_{2}\) and reduce the overhead, the author of Reference [35] incorporated an additional parameter \(c_{2}\) into the heuristic algorithm, setting it to \(c_{2}=\sqrt{2}\). During the initialization phase, the particle size is set to \(m_{2}\times m_{2}\), and noise is added to the number of fine-grained grid cells using Formula (5). Subsequently, the perturbed count of the corresponding fine-grained mesh is published alongside the structure of AG. Based on Formula (1), the counting query algorithm of the AG model satisfies the requirements of \(\varepsilon\)-differential privacy.