Effectively computing transition patterns with privacy-preserved trajectory datasets

by Jong Wook Kim, Beakcheol Jang

Recent advances in positioning techniques, along with the widespread use of mobile devices, make it easier to monitor and collect user trajectory information during their daily activities. An ever-growing abundance of data about trajectories of individual users paves the way for various applications that utilize user mobility information. One of the most common analysis tasks in these new applications is to extract the sequential transition patterns between two consecutive timestamps from a collection of trajectories. Such patterns have been widely exploited in diverse applications to predict and recommend next user locations based on the current position. Thus, in this paper, we explore the computation of the transition patterns, especially with a trajectory dataset collected using differential privacy, which is a de facto standard for privacy-preserving data collection and processing. Specifically, the proposed scheme relies on geo-indistinguishability, which is a variant of the well-known differential privacy, to collect trajectory data from users in a privacy-preserving manner, and exploits the functionality of the expectation-maximization algorithm to precisely estimate hidden transition patterns based on perturbed trajectory datasets collected under geo-indistinguishability. Experimental results using real trajectory datasets confirm that a good estimation of transition pattern can be achieved with the proposed method.