Destination Prediction by Sub-Trajectory Synthesis and Privacy Protection Against Such Prediction
报告人：张瑞 博士 澳大利亚墨尔本大学计算与信息系统系高级讲师、澳大利亚研究理事会（ARC）2012年未来学者计划获得者
Senior Lecturer，Department of Computing and Information Systems，The University of Melbourne，Australia；ARC Future Fellow awarded in 2012
Abstract: Destination prediction is an essential task for many emerging location based applications such as recommending sightseeing places and targeted advertising based on destination. A common approach to destination prediction is to derive the probability of a location being the destination based on historical trajectories. However, existing techniques using this approach suffer from the “data sparsity problem”, i.e., the available historical trajectories is far from being able to cover all possible trajectories. This problem considerably limits the number of query trajectories that can obtain predicted destinations. We propose a novel method named Sub-Trajectory Synthesis (SubSyn) algorithm to address the data sparsity problem. SubSyn algorithm first decomposes historical trajectories into sub-trajectories comprising two neighbouring locations, and then connects the sub-trajectories into “synthesised” trajectories. The number of query trajectories that can have predicted destinations is exponentially increased by this means. Experiments based on real datasets show that SubSyn algorithm can predict destinations for up to ten times more query trajectories than a baseline algorithm while the SubSyn prediction algorithm runs over two orders of magnitude faster than the baseline algorithm. In this paper, we also consider the privacy protection issue in case an adversary uses SubSyn algorithm to derive sensitive location information of users. We propose an efficient algorithm to select a minimum number of locations a user has to hide on her trajectory in order to avoid privacy leak. Experiments also validate the high efficiency of the privacy protection algorithm.
Bio: Dr Rui Zhang is currently a senior lecture in the University of Melbourne. He obtained his bachelor's degree from Tsinghua University in 2001 and PhD from National University of Singapore in 2006. He has been a visiting researcher at Microsoft Research Asia in Beijing during August to November 2011. He has authored and co-authored over 50 publications in prestigious conferences and journals. His research interest is data and information management in general, particularly in areas of indexing techniques, moving object management, web services, data streams and sequence databases. He regularly serves as PC members of top conferences in data management and mining such as SIGMOD, VLDB, ICDE and KDD. He is an Australian Future Fellow (equivalent of mid-career "Thousand Talent Plan" in Australia).