  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 $\epsilon$-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.
