School of Electronic Engineering and Computer Science

Seminar: Privacy for location histograms: How to look like a tourist in your hometown

20 February 2018

Time: 1:00 - 2:00pm
Venue: QMUL campus: Informatics Teaching Laboratory (ITL), Top floor

Hosted by the Theoretical Computer Science research group

Speaker: George Theodorakopoulos (Cardiff University)

Host: Arman Khouzani and Pasquale Malacaria


A location histogram comprises the number of visits by a user to each location in a region of interest (restaurants, hospitals, cinemas, etc.). Such histograms are useful in location analytics for product recommendation and advertising, and also more generally for clustering and classification. However, disclosing a histogram may lead to inference of sensitive information about, e.g., the user's wealth level.

I will present joint work on protection algorithms for location histograms. We introduce two new privacy notions for individuals: sensitive location hiding and target avoidance/resemblance. The former aims to conceal all visits to a certain subset of locations that are deemed sensitive, whereas the latter aims to modify the histogram to make it look like any desirable histogram (e.g. a tourist's typical histogram) or to make it look as dissimilar as possible to a given 
histogram. For each privacy notion, we formulate an optimization problem that aims to maximize the corresponding notion, appropriately quantified, subject to a constraint on the acceptable quality deterioration of the histogram. We solve these problems optimally using a constrained shortest path algorithm, and we present heuristics that speed up the computation by at least two orders of magnitude while still being almost as effective as the optimal solution.

Non QMUL visitors:

As the building has card access, it is best to inform us that you will be coming (