  A location histogram is comprised of the number of times a user has visited
locations as they move in an area of interest, and it is often obtained from
the user in applications such as recommendation and advertising. However, a
location histogram that leaves a user's computer or device may threaten privacy
when it contains visits to locations that the user does not want to disclose
(sensitive locations), or when it can be used to profile the user in a way that
leads to price discrimination and unsolicited advertising. Our work introduces
two privacy notions to protect a location histogram from these threats:
sensitive location hiding, which aims at concealing all visits to sensitive
locations, and target avoidance/resemblance, which aims at concealing the
similarity/dissimilarity of the user's histogram to a target histogram that
corresponds to an undesired/desired profile. We formulate an optimization
problem around each notion: Sensitive Location Hiding (SLH), which seeks to
construct a histogram that is as similar as possible to the user's histogram
but associates all visits with nonsensitive locations, and Target
Avoidance/Resemblance (TA/TR), which seeks to construct a histogram that is as
dissimilar/similar as possible to a given target histogram but remains useful
for getting a good response from the application that analyzes the histogram.
We develop an optimal algorithm for each notion and also develop a greedy
heuristic for the TA/TR problem. Our experiments demonstrate that all
algorithms are effective at preserving the distribution of locations in a
histogram and the quality of location recommendation. They also demonstrate
that the heuristic produces near-optimal solutions while being orders of
magnitude faster than the optimal algorithm for TA/TR.
