Location Prediction for Context-Aware Applications

Neal H. Walfield, Johns Hopkins University

Context-aware applications are programs that are able to improve their performance by adapting to the current conditions, which include the user’s behavior, networking conditions, and charging opportunities. In many cases, the user’s location is an excellent predictor of the context. Thus, by predicting the user’s future location, we can predict the future conditions.

In this talk, I will discuss the techniques that we developed to identify and predict the user’s location over the next 24 hours with a minimum median accuracy of 80%. I will start by describing the user study that we conducted, and some salient conclusions from our analysis. These include our observation that cell phones sample the towers in their vicinity, which makes cell towers as-is inappropriate for use as landmarks. Motivated by this observation, I will then present two techniques for processing the cell tower traces so that landmarks more closely correspond to locations, and cell tower transitions more closely correspond to user movement. Then, I will present our prediction engine, which is based on simple sampling distributions of the form f(t, c), where t is the predicted tower, and c is a set of conditions. The conditions that we considered include the time of the day, the day of the week, the current regime, and the current tower. Our family of algorithms, called TomorrowToday, achieves 89% prediction precision across all prediction trials for predictions 30 minutes in the future. This decreases slowly for predictions further in the future, and levels off for predictions approximately 4 hours in the future, at which point we achieve 80% prediction precision across all prediction trials up to 24 hours in the future. This represents a significant improvement over NextPlace, a well-cited prediction algorithm based on non-linear time series, which achieves appropriately 80% prediction precision (self reported) for predictions 30 minutes in the future, but, unlike our predictors, which try all prediction attempts, NextPlace only attempts 7% of the prediction trials on our data set.

Speaker Biography

Neal is a PhD study at Johns Hopkins University and is being advised by Christian Grothoff. Neal’s main academic interests are in systems and security. While finishing his PhD, he worked part time on GnuPG, a widely used encryption and data authentication program.