Improving Grid-Based Location Prediction Algorithms

Itay Hazan, Asaf Shabtai

There is a vast research upon the problem of location prediction starting from the invention of the GPS and getting back attention due to the spread use of mobile devices containing GPS trackers. Existing methods for location prediction consists of two main parts: Spatial division that break the surface into smaller units and a probability function that maps a probability of moving from one unit to another according to both the previous movements of the user and contextual information gathered from the mobile device (eg day, hour or recent phone call).There are two main types of spatial division approaches: grid-based, and point of interest (POI)-based. In grid-based approach the map splits to cells according to a predefined grid and the prediction is for the next cell on the grid in which the user is expected to visit. In the POI-based approach several point-of-interest locations are marked as interested or might be interested for the user through expert tagging or automatic extraction, while the function predicts the next POI of the user. In both methods, at the moment of the prediction, the probability function map probabilities to cells (also refers to POIs) which indicates the likelihood of the user to visit them in some time in the future. The vector of cells and their probabilities produced by the algorithm will be referred as the probability vector.