Loukides, Grigorios  ORCID: https://orcid.org/0000-0003-0888-5061 and Theodorakopoulos, Georgios ORCID: https://orcid.org/0000-0003-2701-7809
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
|
Preview |
PDF
- Published Version
Available under License Creative Commons Attribution No Derivatives. Download (1MB) | Preview |
Abstract
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: | 05 May 2023 20:13 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/127455 |
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions
Cardiff University Information Services