Predicting human mobility based on location data modeled by Markov chains

Recently, location-based services have attracted significant attention. Against this background, one pivotal and challenging problem is predicting the future location of a user given his or her current location and associated historical mobility data. Predicting human mobility enables many interesting applications such as navigation services, traffic management and location-based advertisements. In this paper, we first extract the region-of-interest (ROI) from the historical location data. With plenty of statistics the original trajectory is represented by Markov chains composed by many ROIs. To improve the performance of the prediction, we extend 1st-order Markov chains to Kth-order Markov chains by reconstituting the structure of priori knowledge, which is intended to take more significant historical information into consideration. We evaluate the certainty of the prediction outcomes in terms of information entropy. We demonstrate that the prediction using a higher-order Markov chain can be more accurate compared with a 1st-order Markov chain.