Answering spatial density queries under local differential privacy

Abstract

Spatial density queries are fundamental in many geospatial data analysis and crowdsourcing tasks. However, answering spatial density queries may violate users’privacy by exposing their locations to an untrusted data collector. In this paper, we propose a solution for answering spatial density queries under Local Differential Privacy (LDP), a state-of-the-art privacy protection standard. Our solution consists of four main steps: partitioning, finding sensitivity, user-side noisy response computation, and server-side estimation. For the first step, we propose and analyze three basic partitioning strategies, and based on our analysis, we design an improved strategy called Advanced Partitioning. For the second step, we adapt graph-based modeling of query sets from the centralized DP literature. Advanced Partitioning also leverages and extends this technique by formulating the partitioning problem using vertex coloring. For the third and fourth steps, in addition to adapting two popular LDP protocols (GRR, RAPPOR), we propose a novel extension for the OUE protocol. Our new protocol (OBE) is not only applicable to our problem but can also be used in other LDP problems with bitvector encodings. Finally, we perform an extensive experimental evaluation of different partitioning strategies and protocols using multiple real-world datasets. Results show that Advanced Partitioning and OBE yield the lowest error, demonstrating the superiority of our proposed methods. IEEE