Location Prediction on Trajectory Data: A Review
Location prediction is the key technique in many location based services including route navigation, dining location recommendations, and traffic planning and control, to mention a few. This survey provides a comprehensive overview of location prediction, including basic definitions and concepts, algorithms, and applications. First, we introduce the types of trajectory data and related basic concepts. Then, we review existing location-prediction methods, ranging from temporal-pattern-based prediction to spatiotemporal-pattern-based prediction. We also discuss and analyze the advantages and disadvantages of these algorithms and briefly summarize current applications of location prediction in diverse fields. Finally, we identify the potential challenges and future research directions in location prediction.
Urban planning, relieving traffic congestion, and effective location recommendation systems are important objectives worldwide and have received increasing attention in recent years. Spatiotemporal data mining is the key technique involved in these practical applications Trajectory data brings new opportunities and challenges in the mining of knowledge about moving objects. To present, many researchers have used trajectory data to mine latent patterns that are hidden in data. These patterns can also be extracted for the analysis of the behavior of moving objects. Location prediction, as the primary task of spatiotemporal data mining, predicts the next location of an object at a given time. In recent years, researchers in location prediction have made much progress. For instance, early studies traced student ID cards to identify frequent temporal patterns and used these patterns to predict their next location Since then, location prediction has had a wide range of applications in daily life, e.g., travel recommendation, location-aware advertisements, and early warning of potential public emergencies, to mention a few.
Introduce these two types of trajectory data below. _ Active recording trajectory data: People actively record their locations when they login to social networks or travel to places of interest and share their life experiences. Typical data types include check-in data (e.g., Twitter, Weibo, QQ, etc.), and location-based data such as travel photos. Figure 1 shows the correlation of users and locations in social networks. In Flickr, a sufficient number of geotagged photos can be formulated as a trajectory, whereby each photo is associated with a location tag and a time stamp. Due to the random behaviors of users, active recording data is typically characterized by its sparsity. When mining this trajectory data, additional social information is usually added. _ Passive recording trajectory data: With the development of positioning techniques, many moving objects are equipped with positioning position devices that record location information. These include global positioning systems GPS in vehicles and radiofrequency identification devices for tracing objects.
In this article, we provided an overview of location prediction ranging from trajectory data preprocessing to forecasting location and the evaluation of location prediction systems. First, we introduced the basic concepts of location prediction, the different types of data sources, the challenges associated with location predictions and the location prediction framework. We introduced trajectory data preprocessing methods and then identified the classification of location prediction model types and discussed these models in detail. Next, we categorized location-prediction models as either single-object or group models or shared insights about these approaches. We also listed the available public datasets and evaluation methods to help readers conduct their own research. Lastly, we discussed locationprediction applications and future work.
 Y. L. Wang, Y. Zheng, and Y. X. Xue, Travel time estimation of a path using sparse trajectories, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 25–34.
 H. K. Pao, J. Fadlil, H. Y. Lin, and K. T. Chen, Trajectory analysis for user verification and recognition, Knowl.- Based Syst., vol. 34, pp. 81–90, 2012.
 J. Yuan, Y. Zheng, X. Xie, and G. Z. Sun, Driving with knowledge from the physical world, in Proc. 17th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Diego, CA, USA, 2011, pp. 316–324.
 A. L. Barab´asi, The origin of bursts and heavy tails in human dynamics, Nature, vol. 435, no. 7039, pp. 207–211, 2005.
 D. Brockmann, L. Hufnagel, and T. Geisel, The scaling laws of human travel, Nature, vol. 439, no. 7075, pp. 462– 465, 2006.
 A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, F. F. Li, and S. Savarese, Social LSTM: Human trajectory prediction in crowded spaces, in IEEE Conf. Computer Vision and Pattern Recognition, Las Vegas, NV, USA, 2016, pp. 961–971.
 F. Wu and Z. H. Li, Where did you go: Personalized annotation of mobility records, in Proc. 25th ACM Int. Conf. Information and Knowledge Management, Indianapolis, IN, USA, 2016, pp. 589–598.
 C. L. Wang, D. De, and W. Z. Song, Trajectory mining from anonymous binary motion sensors in Smart Environment, Knowl.-Based Syst., vol. 37, pp. 346–356, 2013.
 W. Y. Zhu, W. C. Peng, L. J. Chen, K. Zheng, and X. F. Zhou, Modeling user mobility for location promotion in location-based social networks, in Proc. 21th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 1573–1582.
 M. Q. Lv, L. Chen, Y. B. Shen, and G. C. Chen, Measuring cell-id trajectory similarity for mobile phone route classification, Knowl.-Based Syst., vol. 89, pp. 181– 191, 2015.
 Y. Zheng, Trajectory data mining: An overview, ACM Trans. Intell. Syst. Technol., vol. 6, no. 3, p. 29, 2015.
 J. J. Liu, K. Zhao, P. Sommer, S. Shang, B. Kusy, J. G. Lee, and R. Jurdak, A novel framework for online amnesic trajectory compression in resource-constrained environments, IEEE Trans. Knowl. Data Eng., vol. 28, no. 11, pp. 2827–2841, 2016.
 K. F. Richter, F. Schmid, and P. Laube, Semantic trajectory compression: Representing urban movement in a nutshell, J . Spat. Inf. Sci., vol. 2012, no. 4, pp. 3–30, 2012.
 Y. T. Jia, Y. Z. Wang, X. L. Jin, and X. Q. Cheng, Location prediction: A temporal-spatial Bayesian model, ACM Trans. Intell. Syst. Technol., vol. 7, no. 3, p. 31, 2016.
 W. C. Lee and J. Krumm, Trajectory Preprocessing. New York, NY, USA: Springer, 2011.