That's fun - when I was working on this problem a few years ago and unable to find sufficient academic literature on the subject I thought I'd "invented" what turns out to be known as the Viterbi algorithm (duh) and hadn't thought too much of it. Turns out what I thought I'd invented is also a HMM, which is doubly funny because I've never <i>quite</i> managed to wrap my head around HMMs (though several times I've tried). It's interesting how a lot of algorithms are a lot more intuitive than most of the rigorous academic notation make them seem...<p>Code for anyone interested <a href="https://bitbucket.org/ris/tsbp/src" rel="nofollow">https://bitbucket.org/ris/tsbp/src</a> <a href="http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible" rel="nofollow">http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible</a><p>Interesting to look back on the code and see that as much effort is spent on heuristics trying to decide where in the track to spend the calculation effort than anything else.
If you'd like to try map matching as a hosted API right away, see screenshots, demos, and more at <a href="https://mapzen.com/blog/map-matching/" rel="nofollow">https://mapzen.com/blog/map-matching/</a><p>Context: This is a link in to Valhalla documentation. Valhalla is an open-source routing engine led by Mapzen. We also offer it as a hosted SaaS on mapzen.com<p>Disclaimer: I work for Mapzen.