  Map matching has been used to reduce the noisiness of the location estimates
by aligning them to the road network on a digital map. A growing number of
applications, e.g. energy-efficient localization and cellular provider side
localization, depend on the availability of only sparse and coarse-grained
positioning data; leading to a challenging map matching process.
  In this paper, we present semMatch: a system that can provide accurate
HMM-based map matching for challenging positioning traces. semMatch leverages
the smartphone's inertial sensors to detect different road semantics; such as
speed bumps, tunnels, and turns; and uses them in a mathe-matically-principled
way as hints to overcome the sparse, noisy, and coarse-grained input
positioning data, improving the HMM map matching accuracy and efficiency. To do
that, semMatch applies a series of preprocessing modules to handle the noisy
locations. The filtered location data is then processed by the core of semMatch
system using a novel incremental HMM algorithm that combines a
semantics-enriched digital map and the car's ambient road semantics in its
estimation process.
  We have evaluated semMatch using traces collected from different cities
covering more than 150km under different harsh scenarios including
coarse-grained cellular-based positioning data, sparse GPS traces with
extremely low sampling rate, and noisy traces with a large number of
back-and-force transitions. The results show that semMatch significantly
outperforms traditional map matching algorithms under all scenarios, with an
enhancement of at least 416% and 894% in precision and recall respectively in
the most difficult cases. This highlights its promise as a next generation map
matching algorithm for challenging environments.
