Grid-based decompositions for spatial data under local differential privacy

Abstract

Local differential privacy (LDP) has recently emerged as a popular privacy standard. With the growing popularity of LDP, recent works have applied LDP to spatial data, and grid-based decompositions have been a common building block in 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. (2022). To advance the state-of-the-art in adaptive grids, this paper proposes 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, 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.