Abstract: Grid-based differentially private spatial decomposition has attracted considerable research attention in recent years. The trade-off among the size of spatial data, data skew, and Laplace noise directly constrains the accuracy of decomposition. Most state-of-the-art methods based on grid cannot efficiently accommodate the three constraints. To address the above questions, this paper proposes a three-layer adaptive grid, called STAG, to decompose the spatial data with differential privacy. STAG employs Bernoulli random sampling method to retrieve the samples as decomposition data in the second level. According to the different query granularities in the second level, some cells whose counts are smaller than the given threshold will be filtered by exponential mechanism and high-pass filter techniques. For the cells whose counts are over the threshold, STAG uses Down-Split method to decompose them into fine-grained cells in the third level. For the filtered cells, STAG utilizes Up-Merge method to group them into coarse-grained cells with optimal grouping skill in the first level. STAG method is compared with the existing methods such as UG, AG, Kd-Stand, and Kd-Hybrid on the large-scale real datasets. The experimental results show that the STAG outperforms its competitors, achieves the accurate decomposition and results of range query.

Key words: differential privacy, adaptive grid, private spatial decomposition, Bernoulli random sampling, constrained inference