Differential Privacy Space Decomposition Algorithm Based on Hierarchical Model
Haiping Huang, Chaorun Sun, Zhenqi Shi, Wei Zhang, Jiyun Cang, Fu Xiao · IEEE Transactions on Mobile Computing · 2025
Choosing an appropriate division method is crucial for partitioning two-dimensional spatial data under the constraints of differential privacy. The current mainstream partitioning methods include grid-based partitioning and hierarchical partitioning. In order to optimize query accuracy while satisfying differential privacy conditions, it remains challenge to achieve the sum minimization of noise error and uniformity assumption error. To address this issue, we propose the HOLG (Hierarchical Optimization of Logical Grids) algorithm, employing a ”divide-merge-divide” approach. It begins with fine-grained grid partitioning of the data domain, followed by heuristic merging of grids with similar data distributions. After determining the scale of the query domain, the merged regions are further subdivided into smaller regions with similar query probabilities, constructing a hierarchical structure to reduce uniformity assumption errors. Additionally, we design a novel noise injection method and introduce consistency constraints to further minimize noise errors. To reduce the time complexity of the HOLG partitioning method, Huffman trees is employed to optimize the processing of the hierarchical tree set generated by HOLG, ensuring query utility while effectively reducing the query response time for the partitioning algorithm. Experimental results on large-scale spatial datasets demonstrate that HOLG outperforms similar algorithms in query accuracy. Furthermore, when combined with the Huffman tree optimization, it effectively reduces query response time.