Quadtree-Based Adaptive Spatial Decomposition for Range Queries Under Local Differential Privacy

Abstract

Nowadays, researchers have shown significant interest in geographic location-based spatial data analysis due to its wide range of application scenarios. However, the accuracy of the grid-based quadtree range query (GT-R) algorithm, which utilizes the uniform grid method to divide the data space, is compromised by the excessive noise introduced in the divided area. In addition, the private adaptive grid (PrivAG) algorithm does not adopt any index structure, which leads to inefficient query. To address above issues, this paper presents the Quadtree-based Adaptive Spatial Decomposition (ASDQT) algorithm. ASDQT leverages reservoir sampling technology under local differential privacy (LDP) to extract spatial data as the segmentation object. By setting a reasonable threshold, ASDQT dynamically constructs the tree structure, enabling coarse-grained division of sparse regions and fine-grained division of dense regions. Extensive experiments conducted on two real-world datasets demonstrate the efficacy of ASDQT in handling large-scale spatial datasets with different distributions. The results indicate that ASDQT outperforms existing methods in terms of both accuracy and running efficiency.