Differential Private Spatial Decomposition and Location Publishing Based on Unbalanced Quadtree Partition Algorithm

Abstract

Centralized publishing of big location data provides great convenience for various location-based interactive queries and services. Privacy protection of users' location information is an indispensable issue in the security of big data applications. Partition publishing is an effective way to release statistical information of two-dimensional big location data. By combining with the differential privacy model, it can provide more accurate range counting query service on the premise of ensuring location privacy. In order to further improve the availability of location data subsequent to centralized publishing, this paper analyzes the primary noise sources of partition publishing and discusses the constraints among publishing errors, the spatial partition structure, and privacy budget allocation. An unbalanced quadtree partition algorithm based on regional uniformity is proposed. Accordingly, the gradient privacy budget allocation scheme and adjustment method are designed to ensure the effectiveness of the differential privacy model. Experimental comparison of the real-world datasets proves the advantages of the proposed algorithm in improving the querying accuracy of the published data.

Keywords

• Privacy preserving data publishing
• location privacy
• private spatial decomposition
• differential privacy
• unbalanced quadtree partition
• gradient budget allocation