Regions-of-interest discovering and predicting in smartphone environments

Location-Based Services (LBSs) provide users especially in smartphones with information and services based on their location and interests. Predicting people's next location could help in improving the quality of such services and, in turn, boosting people's confidence on those services. Any successful LBS algorithm or model should target three major goals: Location prediction accuracy, high throughput or fast response and efficiency in terms of utilizing smartphone resources. This paper proposes a new approach to discover and predict people's next location based on their mobility patterns, while being computationally efficient. The approach starts by discovering Regions-of-Interest (RoIs) in people's historical trajectories (which denote the locations where users have been previously, frequently). A new model based on Markov Chain (MC) is proposed to overcome the drawback of classical MC. Our proposed model considers both space and time contexts where the space represents a specific location that has been visited by a user while the time represents the location visiting time. We show how classical MC model can be extended to include movement times and how time will improve prediction accuracy. One unique finding in our research is related to the value of integrating users' mobility location/space with time context. In particular, time context is formulated in a way to add extra information to the space context. For better abstraction during building the model, a general transformation function is used to transform the n-order MC into first order. Results show that the proposed approach provides significant improvements in predicting people's next location compared with the state-of-the-art models when applied on two large real-life datasets, GeoLife and Gowalla.