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

George Theodorakopoulos

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.