关键词: 变长马尔可夫模型, 概率后缀树, 历史轨迹, 轨迹预测

Abstract: In the prediction of moving object trajectory, concerning the low accuracy rate of low order Markov model and the expansion of state space in high order model, a dynamic adaptive Probabilistic Suffix Tree (PST) prediction method based on variable length Markov model was proposed. Firstly, moving objects trajectory path was serialized according to the time; then the probability characteristic of sequence context was trained and calculated from the historical trajectory data of moving objects, the probabilistic suffix tree model based path sequence was constructed, combined with the actual trajectory data, thus the future trajectory information could be predicted dynamically and adaptively. The experimental results show that the highest prediction accuracy was obtained in second order model, with the order of the model increasing, the prediction accuracy was maintained at about 82% and better prediction results were achieved. In the meantime, space complexity was decreased exponentially and storage space was reduced greatly. The proposed method made full use of historical data and current trajectory information to predict the future trajectory, and provided a more flexible and efficient location-based services.

Key words: variable order Markov model, Probabilistic Suffix Tree (PST), history trajectory, trajectory prediction