# Personalized Privacy Protection Based on Space Grid in Mobile Crowdsensing
## 2 Related Work
### Private Space Decomposition  
In database management, there exists a specialized storage structure known as an index, which enables the rapid retrieval of required data. For instance, in a student information database, the index allows for the swift retrieval of specific student information. Common index storage is generally implemented using B-tree or B+tree, facilitating the quick location of specified data through dichotomy. However, these conventional indexes are designed solely for one-dimensional data. When dealing with data represented on two-dimensional coordinates, spatial indexes are employed in database management. Data storage commonly utilizes quadtree [33], R-tree, k-d tree and the geohash algorithm to convert two-dimensional data into one-dimensional data, enabling the use of B-tree indexes for efficient spatial data point searches.  
Building upon the definition of query function in differential privacy, [PERSON] et al. proposed the concept of \"private space decomposition (PSD)\" in Reference [34]. PSD is a concept applied in the field of data management. It refers to dividing the data space into smaller subspaces with the introduction of differential privacy protection measures in spatial data structures to achieve the goal of data privacy protection. Under the premise of privacy protection, introducing noise at different levels of the data space can safeguard data privacy while maintaining data structure effectiveness and retrievability. Private space decomposition technology is used in applications involving personal and private data to balance the requirements of data availability and privacy protection.  
When using PSD for privacy protection in spatial indexing, it is common to utilize the spatial index tree structure and divide the geographical area into subintervals, which serve as the next-level nodes of the tree structure. Leaf nodes contain two-dimensional coordinates, while the parent node stores the summarized data information of child nodes adhering to differential privacy, essentially representing the index information. To ensure the objective of data privacy protection, noise is introduced to the spatial nodes during index establishment, ultimately leading to query results aligned with the distribution of differential privacy.  
In addition to the tree hierarchy, the index for spatial data also has a plane structure, such as a grid structure. [PERSON] et al. [30] proposed the concept of a multilevel grid index and compared it with the traditional tree index. Their findings indicate that the multilevel grid offers better performance in terms of differential privacy protection than the traditional hierarchy. They further introduced the unified grid granularity method [30]. Building upon the idea of unifying the grid granularity partition, Reference [35] presented an adaptive grid (AG) method characterized by robustness and simplicity. This method calculates the size of the second grid based on the results of the first grid query. In comparison to the PSD, the AG method also demonstrates robustness and simplicity. While the dynamic grid utilizes some data in the second calculation of grid granularity, its impact on privacy protection is not significant. This paper inherits the adaptive grid (AG) method and makes improvements based on personalized user needs. When adding noise to the grid by using the Laplace mechanism, the personalized user needs are considered.