Differentially private publication of location entropy
By Hien To, Kien Nguyen, Cyrus Shahabi. 2016
21 citations recorded by the source corpus.
Location entropy (LE) is a popular metric for measuring the popularity of various locations (e.g., points-of-interest). Unlike other metrics computed from only the number of (unique) visits to a location, namely frequency, LE also captures the diversity of the users' visits, and is thus more accurate than other metrics. Current solutions for computing LE require full access to the past visits of users to locations, which poses privacy threats. This paper discusses, for the first time, the problem of perturbing location entropy for a set of locations according to differential privacy. The problem is challenging because removing a single user from the dataset will impact multiple records of the database; i.e., all the visits made by that user to various locations. Towards this end, we first derive non-trivial, tight bounds for both local and global sensitivity of LE, and show that to satisfy ε-differential privacy, a large amount of noise must be introduced, rendering the published results useless. Hence, we propose a thresholding technique to limit the number of users' visits, which significantly reduces the perturbation error but introduces an approximation error. To achieve better utility, we extend the technique by adopting two weaker notions of privacy: smooth sensitivity (slightly weaker) and crowd-blending (strictly weaker). Extensive experiments on synthetic and real-world datasets show that our proposed techniques preserve original data distribution without compromising location privacy.
Subfields: Artificial Intelligence, Epidemiology, Transportation
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
- Emiliano De Cristofaro
- Nikita Borisov
- Bo Li
- Carmela Troncoso
- Haojin Zhu
- Qingrong Chen
- Dali Kaafar
- Chong Xiang
In Epidemiology
In Transportation
Citations in the corpus
- Knock Knock, Who's There? Membership Inference on Aggregate Location Data (2017, background): “[32] release the entropy of certain locations with DP guarantees, and show how to achieve better utility although with weaker privacy notions.”
- Differentially Private Data Generative Models (2018, background): “In practice, differentially private schemes are often tailored to the spatio-temporal location privacy analysis [9, 45, 53, 58, 60].”
- What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy (2017, background): “[45] focus on releasing location entropy for ROIs under differential privacy guarantees: they study the bounds of location entropy and show that -differential privacy requires an excessive amount of noise, so they use weaker notions achieving better utility.”