compute candidates on the fly if possible?

[kodonnell]

See here. To summarize, finding candidates on the fly (i.e. at each step of the viterbi sequence) would be beneficial as

• it's probably cleaner - when first reading the code it's confusing why we first find the candidates, then look them up, then create all the time steps, etc.
• less memory (e.g. long routes)
• possibly opens some avenues for optimization e.g. where we know we don't need to find any candidates for the point (e.g. if the timestamp is the same as a last one).
• means an online viterbi algorithm is possible ...

The main challenge seems to be implementation - we can't call queryGraph.lookup multiple times, and we can't (?) create separate queryGraphs without getting duplicate virtual node IDs. So, we can focus on trying to fix this - or there may be another solution (e.g. if we use edge-based traversal it may change things).

For now, I'm flagging this as an issue, but I suggest we wait until the main algorithm/API stabilises somewhat (e.g. #88 and #87) before we try to find a solution.

[stefanholder]

means an online viterbi algorithm is possible ...

Just a minor note: I guess you mean online HMM algorithms in general with this. Usually the forward algorithm would be used to do HMM-based online map matching. There are also online Viterbi variants such as described in this paper but usually one either uses the Forward algorithm or the standard Viterbi algorithm.