A Differentially private hybrid decomposition algorithm based on quad-tree. Issue 109 (October 2021)

• Record Type: Journal Article
• Authors: Li, Shuyu; Geng, Yue; Li, Yingle
• Is Part Of: Computers & security. Issue 109(2021)
• Publication Date: 2021-10
• Subjects: Spatial data query -- Quad-tree -- Differential privacy -- Recursion depth -- Privacy budget; Computer security -- Periodicals; Electronic data processing departments -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.cose.2021.102384
• Languages: English
• ISSNs: 0167-4048

Abstract

Abstract: Nowadays, spatial data provides users with more convenient services because of its wide application scenarios and rich content. At the same time, the collection and release of spatial data also bring risks of privacy disclosure. In this paper, a differentially private hybrid hierarchical decomposition algorithm named DP-HDAQT is proposed for privacy preserving spatial data query. Data dependent adaptive density grid decomposition is used for coarse sparse/dense region splitting at the first layer. Then for dense regions, an improved quad-tree decomposition way is adopted for further sub-region splitting by introducing bias count to eliminate the impact of recursion depth on a query result. Geometric budget allocation strategy and Laplace noise are used during the decomposition process for privacy preservation. Experimental results demonstrate that the proposed algorithm achieves better accuracy of the count queries in the condition of preserving data privacy well.