A hybrid model towards moving route prediction under data sparsity

Moving route prediction offers important benefits for many emerging location-aware applications such as target advertising and urban traffic management. A common approach to route prediction is to match similar trace recordings from a larger volume of historical trajectories, and return the targeted recorded path as desired answer. However, due to privacy concerns, incentive mechanism and other reasons, especially in small business environment, a limited dataset with sparse trajectories is only available. Actually, the existing sparse dataset cannot cover sufficient query routes, and then the match-based approach may return no results at all. Moreover, the existing sparse dataset may fail many trajectory mining approaches that work well on general environment. In this paper, we investigate moving route prediction from sparse trajectory dataset, and propose a novel hybrid model, namely HMRP, to address the above problem. To avoid sparse distribution over spatial semantic layer, a road network map reconstruction methods are proposed to accommodate the sparse trajectories in semantic transformation. And then, by training historical trajectories, the implicit mobility patterns and Markov transition model are constructed to support route prediction. When a query trajectory arrives, towards its derived potential destination, our proposed HMRP model integrates pattern matching strategy and Markov probability distribution to predict its future route gradually in a complementary way. Experiments on real-life taxicab GPS recorded dataset demonstrate that HMRP method can improve movement prediction precision significantly, comparing with the baseline prediction algorithms. And the response time for each query trajectory is acceptable for most application cases.