%0 Journal Article
%A LIU Leijun
%A ZHANG Lei
%A ZHU Meng
%T Sparse trajectory prediction method based on iterative grid partition and entropy estimation
%D
%R 10.11772/j.issn.1001-9081.2015.11.3161
%J Journal of Computer Applications
%P 3161-3165
%V 35
%N 11
%X Concerning the "data sparsity" problem of moving object's trajectory prediction, i.e., the available historical trajectories are far from enough to cover all possible query trajectories that can obtain predicted destinations, a Trajectory Prediction Algorithm suffer from Data Sparsity based on Iterate Grid Partition and Entropy Estimation (TPDS-IGP&EE) was proposed. Firstly, the moving region of trajectories was iteratively divided into a two-dimensional plane grid graph, and then the original trajectories were mapped to the grid graph so that each trajectory could be represented as a grid sequence. Secondly, an L-Z entropy estimator was used to calculate the entropy value of trajectory sequence, and a new trajectory space was generated by doing trajectory synthesis based on trajectory entropy. At last combining with the Sub-Trajectory Synthesis (SubSyn) algorithm, sparse trajectory prediction was implemented. The experimental results show when trajectory completed percentage increases towards 90%, the coverage of the Baseline algorithm decreases to almost 25%. TPDS-IGP&EE algorithm successfully coped with it as expected with only an unnoticeable drop in coverage, and could constantly answer almost 100% of query trajectories. And TPDS-IGP&EE algorithm's prediction accuracy was generally 4% higher than Baseline algorithm. At the same time, the prediction time of Baseline algorithm to 100 ms was too long, while the prediction time of TPDS-IGP&EE algorithm could be negligible (10 μs). TPDS-IGP&EE algorithm can make an effective prediction for the sparse trajectory, providing much wider predicting range, faster predicting speed and better predicting accuracy.
%U http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2015.11.3161