Private spatial data aggregation in the local setting

By Rui Chen, Haoran Li, A. K. Qin, Shiva Prasad Kasiviswanathan, Hongxia Jin. 2016

177 citations recorded by the source corpus.

With the deep penetration of the Internet and mobile devices, privacy preservation in the local setting has become increasingly relevant. The local setting refers to the scenario where a user is willing to share his/her information only if it has been properly sanitized before leaving his/her own device. Moreover, a user may hold only a single data element to share, instead of a database. Despite its ubiquitousness, the above constraints make the local setting substantially more challenging than the traditional centralized or distributed settings. In this paper, we initiate the study of private spatial data aggregation in the local setting, which finds its way in many real-world applications, such as Waze and Google Maps. In response to users' varied privacy requirements that are natural in the local setting, we propose a new privacy model called personalized local differential privacy (PLDP) that allows to achieve desirable utility while still providing rigorous privacy guarantees. We design an efficient personalized count estimation protocol as a building block for achieving PLDP and give theoretical analysis of its utility, privacy and complexity. We then present a novel framework that allows an untrusted server to accurately learn the user distribution over a spatial domain while satisfying PLDP for each user. This is mainly achieved by designing a novel user group clustering algorithm tailored to our problem. We confirm the effectiveness and efficiency of our framework through extensive experiments on multiple real benchmark datasets.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Sociology and Political Science

Citations in the corpus

Marginal Release Under Local Differential Privacy (2017, methodology): “use it on spatial data to build user movement models under LDP [8].”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Differential privacy [16] is a strong privacy standard that provides semantic, information-theoretic guarantees on individuals’ privacy, which has attracted much attention from various fields, including data management [8], [10], [27], machine learning [4], theory [5], [13], [25], and systems [6].”
Locally Differentially Private Protocols for Frequency Estimation (2017, methodology): “[8] uses BLH [6] to learn location information about users.”
PrivTrie: Effective Frequent Term Discovery under Local Differential Privacy (2018, background): “[35] present a generalized version of LDP that is parameterized with individual-specific privacy guarantees for publishing location data.”
Locally Differentially Private Heavy Hitter Identification (2017, background): “Chen et al. [9] uses BLH to learn location from users.”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “Initial work on this problem has extended LDP private frequency collection [7].”
Mutual Information Optimally Local Private Discrete Distribution Estimation (2016, background): “Randomized response and its mutant are still basic building blocks for many local private mechanisms, such as multivariate randomized response [1][20][16][17] for multiple options, binary randomized response [6][7][10] on bit maps, randomized 1 -bit response on random binary matrix [2][3].”
Local Differential Private Data Aggregation for Discrete Distribution Estimation (2019, unknown): “response on random binary matrix [36], [37].”
What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy (2017, background): “[9] focus on spatial data aggregation in the local setting and propose a framework that allows an untrusted server to learn the user distribution over a spatial domain relying on a personalized count estimation protocol and clustering.”