Grid-Based Decompositions for Spatial Data under Local Differential Privacy

Local differential privacy (LDP) has recently emerged as a popular privacy standard. With the growing popularity of LDP, several recent works have applied LDP to spatial data, and grid-based decompositions have been a common building block in the collection and analysis of spatial data under DP and LDP. In this paper, we study three grid-based decomposition methods for spatial data under LDP: Uniform Grid (UG), PrivAG, and AAG. UG is a static approach that consists of equal-sized cells. To enable data-dependent decomposition, PrivAG was proposed by Yang et al. as the most recent adaptive grid method. To advance the state-of-the-art in adaptive grids, in this paper we propose the Advanced Adaptive Grid (AAG) method. For each grid cell, following the intuition that the cell's intra-cell density distribution will be affected by its neighbors, AAG performs uneven cell divisions depending on the neighboring cells' densities. We experimentally compare UG, PrivAG, and AAG using three real-world location datasets, varying privacy budgets, and query sizes. Results show that AAG provides higher utility than PrivAG, demonstrating the superiority of our proposed approach. Furthermore, UG's performance is heavily dependent on the choice of grid size. When the grid size is chosen optimally in UG, AAG still beats UG for small queries, but UG beats AAG for large (coarse-grained) queries.