Probabilistic Map Matching of Sparse and Noisy Smartphone Location Data

There is an immense amount of location data being collected today from smartphone users by various service providers. Due to bandwidth and battery-life considerations, smartphone locations are generally sampled at sparse intervals using energy-efficient, but inaccurate, alternatives to the power-hungry Global Positioning System (GPS). If sparse sequences of coarse location data obtained from mobile users can be accurately map-matched to travel paths on the road network, then this data can be effectively used for several traffic-related applications. Unlike most other map-matching methods in the literature, we, in this paper, focus on the problem of map-matching sparse and noisy non-GPS smartphone location data. We adopt the widely-followed Hidden Markov Model (HMM) approach and propose new probabilistic models for the observation and transition probabilities tailored towards the type of data being considered. Our map-matching method has been evaluated using ground-truth labelled non-GPS location data collected from real drives. Tests show that the accuracy of the proposed method is about 12% more than that of a comparable HMM-based method from the literature. Our results also show that the runtime and latency of the proposed method can be kept within reasonable bounds using simple techniques.