Abstract: Recently， with the wide use of mobile devices and location technology， LBS (location based service) becomes research hotspot. Location prediction is a primary research aspect of LBS. The location prediction based on GPS trajectories was researched. Markov model can represent temporal data well， so it was used in location modeling and prediction. In Markov based location prediction， 1-order Markov model cannot employ trajectory data sufficiently， so the prediction precision is low. The state space of multi-order Markov model will increase rapidly with the order number increasing. For these problems， a novel location prediction method was proposed based on hybrid multi-step Markov model， which transformed the original GPS trajectories into region trajectories. On this basis， all multi-step Markov models were merged. In the course of it， an Adaboost frame based method generating the influence coefficient of each multi-step model was presented. So， the prediction precision was improved， and the state space did not increase. The experiments on real GPS trajectory data show the effectiveness of the location prediction method proposed by the paper.

Key words: location prediction, hybrid multi-step Markov model, region trajectory, the influence coefficient of Markov model, map region partitioning