Abstract: With the popularity of mobile devices and the maturity of location technologies,a variety of location-based applications emerge.In order to make such applications provide users with accurate location-based services,timely,accurately,reliably forecast uncertainty track of moving objects is particularly important.Currently,most traditional methodspredict the destination of a given trajectory by calculating the similarity between two trajectories,and this algorithm does not fully consider the drawbacks of backward and forward linkages between trajectory time series,resulting in a larger prediction error.Theory demonstrates that the Markov model to deal with time series data have very good effect.Therefore,we proposed a sparse trajectory destination prediction algorithm based on Markov model.Meanwhile we investigated a new partitioning strategies for the sample motion space——grid partitioning based on K-d tree.The experimental results show that compared with traditional methods,using Markov model to predict the destination of the tra-jectory will significantly improve the accuracy of the algorithm,and the predicted time will be shortened.

Key words: Trajectory mining,Destination prediction,Markov model