Building quadtrees for spatial data under local differential privacy

Abstract

Spatial decompositions are commonly used in the privacy literature for various purposes such as range query answering, spatial indexing, count-of-counts histograms, data summarization, and visualization. Among spatial decomposition techniques, quadtrees are a popular and well-known method. In this paper, we study the problem of building quadtrees for spatial data under the emerging notion of Local Differential Privacy (LDP). We first propose a baseline solution inspired from a state-of-the-art method from the centralized DP literature and adapt it to LDP. Motivated by the observation that the baseline solution causes large noise accumulation due to its iterative strategy, we then propose a novel solution which utilizes a single data collection step from users, propagates density estimates to all nodes, and finally performs structural corrections to the quadtree. We experimentally evaluate the baseline solution and the proposed solution using four real-world location datasets and three utility metrics. Results show that our proposed solution consistently outperforms the baseline solution, and furthermore, the resulting quadtrees provide high accuracy in practical tasks such as spatial query answering under conventional privacy levels.