Summary
The 2018 International Symposium on Information Theory and Its Applications　(ISITA2018)
2018
Session Number:Mo-PM-1-4
Session:
Number:Mo-PM-1-4.2
A Succinct Model for Re-identification of Mobility Traces Based on Small Training Data
Takao Murakami,
pp.164-168
Publication Date:2018/10/18
Online ISSN:2188-5079
DOI:10.34385/proc.55.Mo-PM-1-4.2
PDF download
Summary:
Re-identification of mobility traces based on the Markov chain model has been widely studied to understand the risk of location privacy. It is well known that this model can re-identify the traces with very high accuracy when the amount of training data is large. However, the amount of training data can be very small in practice, since a user generally discloses only a small number of locations to the public. A state-of-theart method in this scenario is to train the Markov chain model (transition matrices) via tensor factorization. The previous work has shown that this method outperforms a random guess even when the amount of training data is very small. In this paper, we propose a succinct model for re-identification that outperforms the state-of-the-art method explained above. Our proposed method does not model a transition pattern (unlike the Markov chain model) but models a probability of being located in each region via matrix factorization. Then it re-identifies traces based on the JS (Jensen-Shannon) divergence between two probability distributions. We evaluate the proposed method using the Gowalla dataset, and demonstrate that the proposed method significantly outperforms the tensor factorization-based Markov chain model. We also demonstrate that the proposed method significantly outperforms a random guess even when only one single location is available per user as training data.