KVLMM: A Trajectory Prediction Method Based on a Variable-Order Markov Model With Kernel Smoothing

Abstract

With the dramatic proliferation of global positioning system (GPS) devices, a rich range of research has been conducted on the analysis of GPS trajectories. Research on trajectory prediction uses historical trajectory data to forecast future positions. The typical method is to use a statistical model based on the Markov chain. However, existing models are inefficient in two aspects. The methods of using lower-order Markov models use only current information and ignore historical information, degrading the prediction accuracy. In contrast, higher-order Markov models can improve the prediction accuracy but incur increased time and space complexity. Here, we propose the kernel variable length Markov model (KVLMM), a variable-order Markov model based on kernel smoothing, which combines sequence analysis with the Markov statistical model. The KVLMM can adaptively train trajectory data and learn rules from the training results. When training a large data sample, the KVLMM can rapidly execute training in linearly complex time and space. Moreover, this model uses kernel smoothing when training fewer data samples. In other words, the KVLMM improves the prediction accuracy and reduces the overhead of the data process. Our experimental results show that KVLMM has a lower algorithm complexity and a higher prediction accuracy.

Keywords

• Kernels
• suffix array
• trajectory pattern
• trajectory prediction
• variable-order Markov model