Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Location histogram privacy by sensitive location hiding and target histogram avoidance/resemblance

Loukides, Grigorios ORCID: and Theodorakopoulos, Georgios ORCID: 2020. Location histogram privacy by sensitive location hiding and target histogram avoidance/resemblance. Knowledge and Information Systems 62 , pp. 2613-2651. 10.1007/s10115-019-01432-4

[thumbnail of Loukides-Theodorakopoulos2020_Article_LocationHistogramPrivacyBySens.pdf]
PDF - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (1MB) | Preview


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 the context of 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 (e.g. as 'wealthy' or 'minority member'). 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, which operates on a notion-specific search space graph and finds a shortest or longest path in the graph that corresponds to a solution histogram. In addition, we develop a greedy heuristic for the TA/TR problem, which operates directly on a user's histogram. 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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Publisher: Springer Verlag (Germany)
ISSN: 0219-1377
Date of First Compliant Deposit: 11 December 2019
Date of Acceptance: 23 November 2019
Last Modified: 26 Oct 2022 08:26

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics