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

Clc Number:

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
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • 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
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 07,2017
  • Revised:June 16,2017
  • Adopted:
  • Online: November 14,2017
  • Published:
You are the firstVisitors
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