Inferring Semantic Information from User Mobility Data

Thanks to the ubiquity of GPS sensors in a variety of everyday devices, a tremendous amount of data concerning users' mobility patterns is currently being generated and collected. These rich datasets present a unique opportunity to infer a range of useful phenomena, in several different application areas. One area concerns the inference of road maps, where algorithms are designed to automatically infer new sections of the map, thereby reducing the need for expensive road surveys. In this thesis we examine the state of the art algorithms, and identify areas for improvement. We then investigate methods for mitigating the problems presented by infrequently-sampled data, and develop a new hybrid map inference technique for overcoming existing sensitivities to GPS noise and disparity. Next, we look at ways to reduce the data uplink usage of online GPS tracking systems while preserving accuracy. With the most commonly used method for reducing usage in practice being simple uniform periodic sampling, there is substantial room for improvement. We develop a system that combines a unified extrapolator which is able to infer users' future movements, with an adaptive sampler that allows a system operator to specify an error or budget-based performance target, and evaluate its performance against the current status quo. We then look at inferring the necessary phenomena to create a fully automatic transit tracking and arrival time prediction system. Although commercial products exist for this purpose, they can be cost-prohibitive for small agencies. Our system enables the same functionality, with smartphones being the only required hardware. To achieve this goal, we develop the necessary algorithms for automatically inferring routes, stops, and schedules, as well as for providing real-time arrival time predictions, and demonstrate their accuracy against real-world data. Finally, we work to find algorithms for measuring the similarity of a person's days recorded by GPS, in a way that approximates human assessments. Having this capability allows us to provide a useful metric for systems that identify anomalous behavior, or predict how a day is likely to evolve. By conducting a user-study we identify suitable algorithms for this task and evaluate their ability to cluster days.