Large-Scale Trajectory Prediction Model Based on Prefix Projection Technique
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61772091, 61100045, 61363037); Planning Foundation for Humanities and Social Sciences of the Ministry of Education of China (15YJAZH058); Youth Foundation for Humanities and Social Sciences of the Ministry of Education of China (14YJCZH046); Soft Science Foundation of Chengdu (2015-RK00-00059-ZF); Foundation of Educational Commission of Sichuan Province (14ZB0458)

  • Article
  • | |
  • Metrics
  • |
  • Reference [25]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Smart phones, GPS equipped vehicles and wearable devices can generate a large number of trajectory data. These data can not only describe the historical trajectory of moving objects, but also accurately reflect the characteristics of moving objects. The existing trajectory prediction approaches have the following drawbacks:both prediction accuracy and efficiency cannot be guaranteed together, effective trajectory prediction is limited to road-network constrained local spatial areas, and complex and large-scale location data are difficult to process. Aiming to cope with the aforementioned problems, a prefix projection based trajectory prediction model targeting massive trajectory data of moving objects is proposed by employing the basic idea of frequent sequential patterns discovery. The new model, called PPTP (prefix projection based trajectory prediction model), includes two essential steps:(1) Discovering frequent trajectory patterns by creating projected databases and iteratively mining frequent prefix trajectory patterns from projected databases; (2) Trajectory matching by incrementally extending the postfix trajectory based on each frequent sequential pattern and outputting the longest continuous trajectory that is greater than the threshold of minimum support count. The advantages of the proposed algorithm are that it can generate long-term trajectory patterns via short frequent sequential patterns in an incremental manner, and it will not generate useless candidate trajectory sequences in order to overcome the drawback of time-intensive in discovering frequent sequential patterns. Extensive experiments are conducted on real large-scale trajectory data from multiple aspects, and the results show that PPTP algorithm has very high trajectory prediction accuracy when comparing to 1st-order Markov chain prediction algorithm and the average improvement of accuracy can reach to 39.8%. A generic trajectory prediction system is developed based on the proposed trajectory prediction model, and the complete prediction trajectories are visualized in order to provide assistance for users in path planning.

    Reference
    [1] Guo C, Liu JN, Fang Y, Luo M, Cui JS. Value extraction and collaborative mining methods for location big data. Ruan Jian Xue Bao/Journal of Software, 2014,25(4):713-730(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4570.htm[doi:10.13328/j.cnki.jos.004570]
    [2] Qiao SJ, Han N, Zhu W, Gutierrez LA. TraPlan:An effective three-in-one trajectory prediction model in transportation networks. IEEE Trans. on Intelligent Transportation Systems, 2015,16(3):1188-1198.[doi:10.1109/TITS.2014.2353302]
    [3] Yuan J, Zheng Y, Xie X, Sun G. T-Drive:Enhancing driving directions with taxi drivers' intelligence. IEEE Trans. on Knowledge and Data Engineering, 2013,25(1):220-232.[doi:10.1109/TKDE.2011.200]
    [4] Qiao SJ, Shen DY, Wang XT, Han N, Zhu W. A self-adaptive parameter selection trajectory prediction approach via hidden markov models. IEEE Trans. on Intelligent Transportation Systems, 2015,16(1):284-296.[doi:10.1109/TITS.2014.2331758]
    [5] Zheng Y. Trajectory data mining:an overview. ACM Trans. on Intelligent Systems and Technology, 2015,6(3):Article 29.[doi:10. 1145/2743025]
    [6] Bao J, Zheng Y, Wilkie D, Mokbel M. Recommendations in location-based social networks:A survey. Geoinformatica, 2015,19(3):525-565.[doi:10.1007/s10707-014-0220-8]
    [7] Zheng K, Zheng Y, Yuan J, Shang S, Zhou XF. Online discovery of gathering patterns over trajectories. IEEE Trans. on Knowledge and Data Engineering, 2014,26(8):1974-1988.[doi:10.1109/TKDE.2013.160]
    [8] Prentow T, Thom A, Blunck H, Vahrenhold J. Making sense of trajectory data in indoor spaces. In:Proc. of the 16th IEEE Int'l Conf. on Mobile Data Management. Washington:IEEE, 2015. 116-121.[doi:10.1109/MDM.2015.44]
    [9] Dai J, Ding Z, Xu J. Context-Based moving object trajectory uncertainty reduction and ranking in road network. Journal of Computer Science and Technology, 2016,31(1):167-184.[doi:10.1007/s11390-016-1619-5]
    [10] Tao Y, Faloutsos C, Papadias D, Liu B. Prediction and indexing of moving objects with unknown motion patterns. In:Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. New York:ACM Press, 2004. 611-622.[doi:10.1145/1007568.1007637]
    [11] Morzy M. Mining frequent trajectories of moving objects for location prediction. In:Proc. of 5th Int'l Conf. on Machine Learning and Data Mining in Pattern Recognition. Berlin:Springer-Verlag, 2007. 667-680.[doi:10.1007/978-3-540-73499-4_50]
    [12] Song C, Qu Z, Blumm N, Barabási AL. Limits of predictability in human mobility. Science, 2010,327(5968):1018-1021.[doi:10. 1126/science.1177170]
    [13] Pentland A. Society's nervous system:Building effective government, energy, and public health systems. IEEE Computer, 2012, 45(1):31-38.[doi:10.1109/MC.2011.299]
    [14] Ding Z, Yang B, Güting RH, Li Y. Network-Matched trajectory-based moving-object database:Models and applications. IEEE Trans. on Intelligent Transportation Systems, 2015,16(4):1918-1928.[doi:10.1109/TITS.2014.2383494]
    [15] Qiao SJ, Jin K, Han N, Tang CJ, Gesangduoji, Gutierrez LA. Trajectory prediction algorithm based on Gaussian mixture model. Ruan Jian Xue Bao/Journal of Software, 2015,26(5):1048-1063(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4796.htm[doi:10.13328/j.cnki.jos.004796]
    [16] Dai J, Yang B, Guo C, Ding Z. Personalized route recommendation using big trajectory data. In:Proc. of the 31st IEEE Int'l Conf. on Data Engineering. Washington:IEEE, 2015. 543-554.[doi:10.1109/ICDE.2015.7113313]
    [17] Yuan G, Zhao J, Xia S, Zhang Y, Li W. Multi-Granularity periodic activity discovery for moving objects. Int'l Journal of Geographical Information Science, 2017,31(3):435-462.[doi:10.1080/13658816.2016.1205194]
    [18] Zhang L, Liu L, Xia Z, Li W, Fan Q. Sparse trajectory prediction based on multiple entropy measures. Entropy, 2016,18(9):No.327.[doi:10.3390/e18090327]
    [19] Chaulwar A, Botsch M, Utschick W. A hybrid machine learning approach for planning safe trajectories in complex traffic-scenarios. In:Proc. of 15th IEEE Int'l Conf. on Machine Learning and Applications. Washington:IEEE, 2016. 540-546.[doi:10.1109/ICMLA.2016.0095]
    [20] Pei J, Han J, Mortazavi-Asl B, Wang J, Pinto H, Chen Q, Dayal U, Hsu M. Mining sequential patterns by pattern-growth:The prefixspan approach. IEEE Trans. on Knowledge and Data Engineering, 2004,16(11):1424-1440.[doi:10.1109/TKDE.2004.77]
    [21] Yuan J, Zheng Y, Zhang C, Xie W, Xie X, Sun G, Huang Y. T-Drive:Driving directions based on taxi trajectories. In:Proc. of the 18th SIGSPATIAL Int'l Conf. on Advances in Geographic Information Systems. New York:ACM Press, 2010. 99-108.[doi:10.1145/1869790.1869807]
    [22] Gambs S, Killijian M, Cortez DP, Miguel N. Next place prediction using mobility Markov chains. In:Proc. of the 1st Workshop Measurement, Privacy, and Mobility. New York:ACM Press, 2012.[doi:10.1145/2181196.2181199]
    附中文参考文献:
    [1] 郭迟,刘经南,方媛,罗梦,崔竞松.位置大数据的价值提取与协同挖掘方法.软件学报,2014,25(4):713-730. http://www.jos.org.cn/1000-9825/25/713.htm[doi:10.13328/j.cnki.jos.004570]
    [15] 乔少杰,金琨,韩楠,唐常杰,格桑多吉,Gutierrez LA. 一种基于高斯混合模型的轨迹预测算法.软件学报,2015,26(5):1048-1063. http://www.jos.org.cn/1000-9825/4796.htm[doi:10.13328/j.cnki.jos.004796]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

乔少杰,韩楠,李天瑞,李荣华,李斌勇,王晓腾,Louis Alberto GUTIERREZ.基于前缀投影技术的大规模轨迹预测模型.软件学报,2017,28(11):3043-3057

Copy
Share
Article Metrics
  • Abstract:2763
  • PDF: 4427
  • HTML: 1557
  • Cited by: 0
History
  • Received:April 07,2017
  • Revised:June 16,2017
  • Online: November 14,2017
You are the first2033441Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063