Combining Markov model and Prediction by Partial Matching compression technique for route and destination prediction

摘要

Thanks to the built-in GPS device embedded in almost all smartphones, the facility of tracking users’ positions fostered new research opportunities. Among these opportunities, of particular interest in this work is the field of route and destination prediction. Suggesting a user to take a deviation to avoid a congested route is among the potential benefits of our research. Many of the approaches available in the literature consolidate the Markov model as suitable to prediction. Moreover, the Prediction by Partial Matching (PPM) compression technique has presented encouraging results for predicting route and destination. Thus, this paper proposes a novel predictor that combines Markov model with PPM technique, extracting the better of these two approaches. Our user-personalized predictor is able to predict the route and destination automatically in a real-time manner, including places never visited by the user. We evaluated our model with real world data collected from 21 users, obtaining a precision rate between 63% and 82%.