Research And Application Of Two-dimensional Spatial Data Partitioning Algorithm Based On Differential Privacy

Spatial partitioning is an effective measure used for statistical location data characteristics.In order to solve the problem that the existing location data partitioning methods based on differential privacy do not fully consider the characteristics of spatial data distribution and noise overlay,two perspectives of partitioning structure and privacy budget allocation are studied,and the grid adaptive merging bucket algorithm based on differential privacy and the unbalanced quadratic tree partitioning algorithm based on differential privacy are proposed,and the effectiveness of the methods is verified by experimental comparison.The main research work and results include:1.A differential privacy-based grid adaptive ensemble bucketing algorithm is proposed.First,the spatial dataset is divided into two levels of grids.At the same time,adaptive bucket-fitting judgments are made based on the sum-of-squares error values within the divided regions,and regions with similar distributions are heuristically put into the same bucket,i.e.reducing the uniformity assumption error and reducing the noise error caused by a large number of blank regions.Finally,a reasonable allocation of noise is achieved by a noise allocation strategy based on Hopkins’ statistics.The experimental results on real location datasets show that the algorithm can obtain a better range querying effect and privacy preservation effect compared with other differential privacy space partitioning class-based algorithms.2.An unbalanced quadratic tree space partitioning algorithm based on differential privacy is proposed.The algorithm determines the distribution density of the current region based on the Hopkins statistics of the tree nodes and adaptively performs iterative partitioning to reduce the negative effects caused by blank regions and overpartitioning.Also,a new privacy budget allocation scheme is designed to further improve the query accuracy of the location data.The scheme performs geometric privacy budget allocation from top to bottom based on a quadratic tree structure that fits into an unbalanced quadratic tree structure to achieve reasonable privacy budget allocation results.Experimental results on real location datasets show that the algorithm achieves better range query results and privacy preservation compared to other differential privacy space partitioning-based class algorithms.3.A spatial range number query system was developed using the Python language and the Py Side2 framework.The system is divided and designed with four major modules,namely the user module,the dataset management module,the computation engine module,and the query module,and the algorithm proposed in the above research work is used for the actual range number query.Main contributions: A grid adaptive merging bucket algorithm was designed based on the values of Hopkins statistics in different grids;an unbalanced quadtree strategy was implemented using an unbalanced quadtree strategy with a geometric privacy budget allocation strategy.