3 ms·

Map Matching in a Programmer's Perspective

40 points by hodgesmr 9y ago

drewda 9y ago
If you'd like to try map matching as a hosted API right away, see screenshots, demos, and more at https://mapzen.com/blog/map-matching/ https://mapzen.com/blog/map-matching/ 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 Disclaimer: I work for Mapzen.
ris 9y ago
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 quite 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... Code for anyone interested https://bitbucket.org/ris/tsbp/src https://bitbucket.org/ris/tsbp/src http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible 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.
- adrianratnapala 9y ago
  Indeed. The need for rigor often means certain parts of an argument get emphazised when they distract from the intuitive explanation. Also, when things get mathematically people have an urge to show how it connects to other mathematical results. Those connections are interesting in their own right, but they might not be related to the engineering problem at hand. The result is that understanding the literature can involve a long hard slog through other literature, just to discover that most of what you read was irrelevant. This is what it is often easier to discover things in the lab than in the library.

40 points by hodgesmr 9y ago

If you'd like to try map matching as a hosted API right away, see screenshots, demos, and more at https://mapzen.com/blog/map-matching/ https://mapzen.com/blog/map-matching/ 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 Disclaimer: I work for Mapzen.

ris 9y ago

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 quite 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... Code for anyone interested https://bitbucket.org/ris/tsbp/src https://bitbucket.org/ris/tsbp/src http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible http://wiki.openstreetmap.org/wiki/That_Shouldnt_Be_Possible 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.

adrianratnapala 9y ago
Indeed. The need for rigor often means certain parts of an argument get emphazised when they distract from the intuitive explanation. Also, when things get mathematically people have an urge to show how it connects to other mathematical results. Those connections are interesting in their own right, but they might not be related to the engineering problem at hand. The result is that understanding the literature can involve a long hard slog through other literature, just to discover that most of what you read was irrelevant. This is what it is often easier to discover things in the lab than in the library.