Journal Home > Volume 1 , Issue 2

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.


menu
Abstract
Full text
Outline
About this article

Location Prediction on Trajectory Data: A Review

Show Author's information Ruizhi WuGuangchun Luo( )Junming ShaoLing TianChengzong Peng
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China.

Abstract

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.

Keywords: data mining, location prediction, trajectory data

References(85)

[1]
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.
DOI
[2]
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.
[3]
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.
DOI
[4]
A. L. Barabási, The origin of bursts and heavy tails in human dynamics, Nature, vol. 435, no. 7039, pp. 207-211, 2005.
[5]
D. Brockmann, L. Hufnagel, and T. Geisel, The scaling laws of human travel, Nature, vol. 439, no. 7075, pp. 462-465, 2006.
[6]
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.
DOI
[7]
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.
DOI
[8]
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.
[9]
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.
DOI
[10]
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.
[11]
Y. Zheng, Trajectory data mining: An overview, ACM Trans. Intell. Syst. Technol., vol. 6, no. 3, p. 29, 2015.
[12]
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.
[13]
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.
[14]
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.
[15]
W. C. Lee and J. Krumm, Trajectory Preprocessing. New York, NY, USA: Springer, 2011.
DOI
[16]
J. Muckell, J. H. Hwang, V. Patil, C. T. Lawson, F. Ping, and S. S. Ravi, SQUISH: An online approach for GPS trajectory compression, in Proc. 2nd Int. Conf. Computing for Geospatial Research & Applications, Washington, DC, USA, 2011, p. 13.
DOI
[17]
J. Muckell, P. W. Olsen, J. H. Hwang, C. T. Lawson, and S. S. Ravi, Compression of trajectory data: A comprehensive evaluation and new approach, Geoinformatica, vol. 18, no. 3, pp. 435-460, 2014.
[18]
Q. Gao, F. L. Zhang, R. J. Wang, and F. Zhou, Trajectory big data: A review of key technologies in data processing, J. Softw., vol. 28, no. 4, pp. 959-992, 2017.
[19]
J. G. Lee, J. W. Han, and K. Y. Whang, Trajectory clustering: A partition-and-group framework, in Proc. 2007 ACM SIGMOD Int. Conf. Management of Data, Beijing, China, 2007, pp. 593-604.
DOI
[20]
S. Tiwari and S. Kaushik, Popularity estimation of interesting locations from visitor’s trajectories using fuzzy inference system, Open Comput. Sci., vol. 6, no. 1, pp. 8-24, 2016.
[21]
Y. Zheng, L. Z. Zhang, X. Xie, and W. Y. Ma, Mining interesting locations and travel sequences from GPS trajectories, in Proc. 18th Int. Conf. World Wide Web, Madrid, Spain, 2009, pp. 791-800.
DOI
[22]
C. Brunsdon, Computing with spatial trajectories, Int.J. Geogr. Inf. Sci., vol. 27, no. 1, pp. 208-209, 2013.
[23]
J. J. C. Ying, W. C. Lee, T. C. Weng, and V. S. Tseng, Semantic trajectory mining for location prediction, in Proc. 19th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Chicago, IL, USA, 2011, pp. 34-43.
DOI
[24]
C. S. Jensen and N. Tradišauskas, Map matching, in Encyclopedia of Database Systems, L. Liu and M. T. Özsu, eds. Springer, 2009, pp. 1692-1696.
DOI
[25]
J. S. Greenfeld, Matching GPS observations to locations on a digital map, in Proc. 81st Annual Meeting of the Transportation Research Board, Washington, DC, USA, 2002.
[26]
H. B. Yin and O. Wolfson, A weight-based map matching method in moving objects databases, in Proc. 16th Int. Conf. Scientific and Statistical Database Management, Santorini Island, Greece, 2004, pp. 437-438.
[27]
H. Y. Li, Y. Ge, R. C. Hong, and H. S. Zhu, Point-of-interest recommendations: Learning potential check-ins from friends, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 975-984.
DOI
[28]
Y. Zheng, Location-based social networks: Users. in Computing with Spatial Trajectories, Y. Zheng and X. F. Zhou, eds. Springer, 2011, pp. 243-276.
DOI
[29]
C. Barrios, H. Himberg, Y. Motai, and A. Sad, Multiple model framework of adaptive extended Kalman filtering for predicting vehicle location, in 2006 IEEE Intelligent Transportation Systems Conference, Toronto, Canada, 2006.
DOI
[30]
J. Hightower and G. Borriello, Particle filters for location estimation in ubiquitous computing: A case study, in Proc. 6th Int. Conf. Ubiquitous Computing, Nottingham, UK, 2004, pp. 88-106.
DOI
[31]
F. Gustafsson, Particle filter theory and practice with positioning applications, IEEE Aerosp. Electron. Syst. Mag., vol. 25, no. 7, pp. 53-82, 2010.
[32]
G. D. Qi, G. Pan, S. J. Li, Z. H. Wu, D. Q. Zhang, L. Sun, and L. T. Yang, How long a passenger waits for a vacant taxi-large-scale taxi trace mining for smart cities, in 2013 IEEE Int. Conf. Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and Social Computing, Beijing, China, 2013, pp. 1029-1036.
DOI
[33]
F. Z. Zhang, N. J. Yuan, D. Wilkie, Y. Zheng, and X. Xie, Sensing the pulse of urban refueling behavior: A perspective from taxi mobility, ACM Trans. Intell. Syst. Technol., vol. 6, no. 3, p. 37, 2015.
[34]
D. Q. Zhang, L. Sun, B. Li, C. Chen, G. Pan, S. J. Li, and Z. H. Wu, Understanding taxi service strategies from taxi GPS traces, IEEE Trans. Intell. Transp. Syst., vol. 16, no. 1, pp. 123-135, 2015.
[35]
H. J. Wang, Z. H. Li, and W. C. Lee, PGT: Measuring mobility relationship using personal, global and temporal factors, in 2014 IEEE Int. Conf. Data Mining, Shenzhen, China, 2014, pp. 570-579.
DOI
[36]
J. Hershberger and J. Snoeyink, Speeding up the Douglas-Peucker line-simplification algorithm, Vancouver, Canada: University of British Columbia, pp. 134-143, 1992.
[37]
N. Meratnia and R. A. De By, Spatiotemporal compression techniques for moving point objects, in Proc. 9th Int. Conf. Extending Database Technology, Heraklion, Crete, Greece, 2004, pp. 765-782.
DOI
[38]
A. Ballatore, G. McArdle, C. Kelly, and M. Bertolotto, RecoMap: An interactive and adaptive map-based recommender, in Proc. 2010 ACM Symposium on Applied Computing, Sierre, Switzerland, 2010, pp. 887-891.
DOI
[39]
O. Pink and B. Hummel, A statistical approach to map matching using road network geometry, topology and vehicular motion constraints, in Proc. 11th Int. IEEE Conf. Intelligent Transportation Systems, Beijing, China, 2008, pp. 862-867.
DOI
[40]
P. Newson and J. Krumm, Hidden Markov map matching through noise and sparseness, in Proc. 17th ACM Sigspatial Int. Conf. Advances in Geographic Information Systems, Seattle, WA, USA, 2009, pp. 336-343.
DOI
[41]
Y. Zheng, L. Capra, O. Wolfson, and H. Yang, Urban computing: Concepts, methodologies, and applications, ACM Trans. Intell. Syst. Technol., vol. 5, no. 3, p. 38, 2014.
[42]
S. S. Chawathe, Segment-based map matching, in Proc. 2007 IEEE Intelligent Vehicles Symposium, Istanbul, Turkey, 2007, pp. 1190-1197.
DOI
[43]
L. Song, D. Kotz, R. Jain, and X. N. He, Evaluating location predictors with extensive Wi-Fi mobility data, in Proc. 23rd Annual Joint Conf. of the IEEE Computer and Communications Societies, Hong Kong, China, 2004, pp. 1414-1424.
[44]
V. Bogorny, B. Kuijpers, and L. O. Alvares, ST-DMQL: A semantic trajectory data mining query language, Int.J. Geogr. Inf. Sci., vol. 23, no. 10, pp. 1245-1276, 2009.
[45]
L. O. Alvares, V. Bogorny, B. Kuijpers, B. Moelans, J. A. F. de Macedo, and A. Tietbohl Palma, Towards semantic trajectory knowledge discovery, Technical Report, Hasselt University, Belgium, 2007.
[46]
C. Parent, S. Spaccapietra, C. Renso, G. Andrienko, N. Andrienko, V. Bogorny, M. L. Damiani, A. Gkoulalas-Divanis, J. Macedo, N. Pelekis, et al., Semantic trajectories modeling and analysis, ACM Comput. Surv., vol. 45, no. 4, p. 42, 2013.
[47]
Y. Z. Wang, N. J. Yuan, D. F. Lian, L. L. Xu, X. Xie, E. H. Chen, and Y. Rui, Regularity and conformity: Location prediction using heterogeneous mobility data, in Proc. 21st ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 1275-1284.
DOI
[48]
D. F. Lian, X. Xie, V. W. Zheng, N. J. Yuan, F. Z. Zhang, and E. H. Chen, CEPR: A collaborative exploration and periodically returning model for location prediction, ACM Trans. Intell. Syst. Technol., vol. 6, no. 1, p. 8, 2015.
[49]
Q. Liu, S. Wu, L. Wang, and T. N. Tan, Predicting the next location: A recurrent model with spatial and temporal contexts, in Proc. 30th AAAI Conf. Artificial Intelligence, Phoenix, AZ, USA, 2016, pp. 194-200.
[50]
Y. X. Li, Y. Zheng, H. C. Zhang, and L. Chen, Traffic prediction in a bike-sharing system, in Proc. 23rd Sigspatial Int. Conf. Advances in Geographic Information Systems, Seattle, WA, USA, 2015, p. 33.
DOI
[51]
D. Ashbrook and T. Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, vol. 7, no. 5, pp. 275-286, 2003.
[52]
E. Cho, S. A. Myers, and J. Leskovec, Friendship and mobility: User movement in location-based social networks, in Proc. 17th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Diego, CA, USA, 2011, pp. 1082-1090.
DOI
[53]
F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, Trajectory pattern mining, in Proc. 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 330-339.
DOI
[54]
T. Kim, Y. S. Yue, S. Taylor, and I. Matthews, A decision tree framework for spatiotemporal sequence prediction, in Proc. 21th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Sydney, Australia, 2015, pp. 577-586.
DOI
[55]
Z. H. Li, J. W. Han, M. Ji, L. A. Tang, Y. T. Yu, B. L. Ding, J. G. Lee, and R. Kays, MoveMine: Mining moving object data for discovery of animal movement patterns, ACM Trans. Intell. Syst. Technol., vol. 2, no. 4, p. 37, 2011.
[56]
A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti, WhereNext: A location predictor on trajectory pattern mining, in Proc. 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 637-646.
DOI
[57]
S. Lee, J. Lim, J. Park, and K. Kim, Next place prediction based on spatiotemporal pattern mining of mobile device logs, Sensors, vol. 16, no. 2, p. 145, 2016.
[58]
P. Bhargava, T. Phan, J. Y. Zhou, and J. H. Lee, Who, what, when, and where: Multi-dimensional collaborative recommendations using tensor factorization on sparse user-generated data, in Proc. 24th Int. Conf. World Wide Web, Florence, Italy, 2015, pp. 130-140.
DOI
[59]
H. J. Gao, J. L. Tang, and H. Liu, gSCorr: Modeling geo-social correlations for new check-ins on location-based social networks, in Proc. 21st ACM Int. Conf. Information and Knowledge Management, Maui, HI, USA, 2012, pp. 1582-1586.
DOI
[60]
H. J. Guo, J. L. Tang, and H. Liu, Exploring social-historical ties on location-based social networks, in Proc. 6th Int. AAAI Conf. Weblogs and Social Media, Dublin, Ireland, 2012.
[61]
Y. W. Teh, A hierarchical Bayesian language model based on Pitman-Yor processes, in ACL-44 Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, 2006, pp. 985-882.
DOI
[62]
A. Sadilek, H. Kautz, and J. P. Bigham, Finding your friends and following them to where you are, in Proc. 5th ACM International Conference on Web Search and Data Mining, Seattle, WA, USA, 2012, pp. 723-732.
DOI
[63]
N. Du, H. J. Dai, R. Trivedi, U. Upadhyay, M. Gomez-Rodriguez, and L. Song, Recurrent marked temporal point processes: Embedding event history to vector, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 1555-1564.
DOI
[64]
A. Zarezade, S. Jafarzadeh, and H. R. Rabiee, Spatio-temporal modeling of check-ins in location-based social networks, arXiv preprint arXiv: 1611.07710, 2016.
[65]
A. Noulas, S. Scellato, N. Lathia, and C. Mascolo, Mining user mobility features for next place prediction in location-based services, in Proc. 12th Int. Conf. Data Mining, Brussels, Belgium, 2012, pp. 1038-1043.
DOI
[66]
G. E. Hinton, S. Osindero, and Y. W. Teh, A fast learning algorithm for deep belief nets, Neural Comput., vol. 18, no. 7, pp. 1527-1554, 2006.
[67]
J. B. Zhang, Y. Zheng, and D. K. Qi, Deep spatio-temporal residual networks for citywide crowd flows prediction. in Proc. 21st AAAI Conf. Artificial Intelligence, San Francisco, CA, USA, 2016.
[68]
J. B. Zhang, Y. Zheng, D. K. Qi, R. Y. Li, and X. W. Yi, DNN-based prediction model for spatio-temporal data, https://www.microsoft.com/en-us/research/publication/dnn-based-prediction-model-spatial-temporal-data, 2017.
DOI
[69]
A. Noulas, S. Scellato, C. Mascolo, and M. Pontil, An empirical study of geographic user activity patterns in foursquare. in Proc. 5th Int. AAAI Conf. Weblogs and Social Media, Barcelona, Spain, 2011.
[70]
O. Bouidghaghen, L. Tamine, and M. Boughanem, Personalizing mobile web search for location sensitive queries, in Proc. IEEE 12th Int. Conf. Mobile Data Management, Lulea, Sweden, 2011, pp. 110-118.
DOI
[71]
A. Y. Xue, R. Zhang, Y. Zheng, X. Xie, J. Huang, and Z. H. Xu, Destination prediction by sub-trajectory synthesis and privacy protection against such prediction, in Proc. 29th Int. Conf. Data Engineering, Brisbane, Australia, 2013, pp. 254-265.
DOI
[72]
J. J. C. Ying, W. C. Lee, and V. S. Tseng, Mining geographic-temporal-semantic patterns in trajectories for location prediction, ACM Trans. Intell. Syst. Technol., vol. 5, no. 1, p. 2, 2013.
[73]
J. Bao, Y. Zheng, D. Wilkie, and M. Mokbel, Recommendations in location-based social networks: A survey, Geoinformatica, vol. 19, no. 3, pp. 525-565, 2015.
[74]
A. Noulas, S. Scellato, C. Mascolo, and M. Pontil, An empirical study of geographic user activity patterns in foursquare, in Proc. 5th International AAAI Conference on Weblogs and Social Media, Barcelona, Spain, 2011.
[75]
J. Bao, Y. Zheng, and M. F. Mokbel, Location-based and preference-aware recommendation using sparse geo-social networking data, in Proc. 20th Int. Conf. Advances in Geographic Information Systems, Redondo Beach, CA, USA, 2012, pp. 199-208.
DOI
[76]
Y. Zheng, Q. N. Li, Y. K. Chen, X. Xie, and W. Y. Ma, Understanding mobility based on GPS data, in Proc. 10th Int. Conf. Ubiquitous Computing, Seoul, Korea, 2008, pp. 312-321.
DOI
[77]
C. D. Manning, P. Raghavan, and H. Schutze, Introduction to Information Retrieval. Cambridge, UK: Cambridge University Press, 2008.
DOI
[78]
Y. Arase, X. Xie, T. Hara, and S. Nishio, Mining people’s trips from large scale geo-tagged photos, in Proc. 18th ACM Int. Conf. Multimedia, Firenze, Italy, 2010, pp. 133-142.
DOI
[79]
Y. Wei, Y. Zheng, and Q. Yang, Transfer knowledge between cities, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 1905-1914.
DOI
[80]
J. Y. Zhu, C. Zhang, H. C. Zhang, S. Zhi, V. O. K. Li, J. W. Han, and Y. Zheng, pg-causality: Identifying spatiotemporal causal pathways for air pollutants with urban big data, IEEE Trans. Big Data, .
[81]
Y. Liu, Y. Zheng, Y. X. Liang, S. M. Liu, and D. S. Rosenblum, Urban water quality prediction based on multi-task multi-view learning, in Proc. 25th Int. Joint Conf. Artificial Intelligence, New York, NY, USA, 2016.
[82]
H. J. Wang, D. Kifer, C. Graif, and Z. H. Li, Crime rate inference with big data, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 635-644.
DOI
[83]
C. Lopez and Y. P. P. Chen, Using object and trajectory analysis to facilitate indexing and retrieval of video, Knowl.-Based Syst., vol. 19, no. 8, pp. 639-646, 2006.
[84]
Z. Y. Cheng, J. Caverlee, K. Lee, and D. Z. Sui, Exploring millions of footprints in location sharing services, in Proc. 5th Int. AAAI Conf. Weblogs and Social Media, Barcelona, Spain, 2011.
[85]
L. Backstrom, E. Sun, and C. Marlow, Find me if you can: Improving geographical prediction with social and spatial proximity, in Proc. 19th Int. Conf. World Wide Web, Raleigh, NC, USA, 2010, pp. 61-70.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 20 November 2017
Accepted: 10 January 2018
Published: 12 April 2018
Issue date: June 2018

Copyright

© The author(s) 2018

Acknowledgements

We thank the editors and reviewer for everything you have done for us. This research was supported by the Foundation of Science & Technology Department of Sichuan Province (Nos. 2017JY0027 and 2016GZ0075), the National Key Research and Development Program (2016YFB0502300).

Rights and permissions

Return