Matching GPS Traces to Roads (Map Matching)

Map matching is the problem of deciding which road a vehicle was on, given fixes that are several metres wrong and roads that are sometimes several metres apart. It is not a nearest-neighbour question, and treating it as one is why the results look drunk.

Why nearest-road snapping fails

Snap each fix independently to the closest road geometry and two failure modes appear immediately. On a divided highway with a parallel service road, consecutive fixes alternate between the two, producing a route that crosses the central reservation every few seconds. At a grade separation, a fix taken on the overpass snaps to the road underneath, because in two dimensions they are the same place.

The information that resolves both is not in any single fix. It is in the sequence: a vehicle that was on the highway a second ago is overwhelmingly likely to still be on it, because the alternative requires a manoeuvre the road network does not permit. Any method that decides one fix at a time throws that away. The standard formulation that keeps it is a hidden Markov model, set out by Paul Newson and John Krumm at Microsoft Research in Hidden Markov Map Matching Through Noise and Sparseness (ACM SIGSPATIAL 2009), which is what almost every open-source matcher implements today.

Candidates: the hidden states

The observations are the GPS fixes. The hidden states are road positions: for each fix, collect every road segment within a search radius — 200 m is a common default — and take the closest point on each segment. A fix in a dense city centre might have fifteen candidates; one on a rural road might have one. The output is a choice of one candidate per fix such that the whole sequence is the most probable one, subject to the candidates being connected by real routes.

Two parameters here decide everything downstream. Too small a search radius and the correct road is not in the candidate set at all, so no amount of clever sequencing recovers it. Too large and the candidate count per fix explodes, and Viterbi cost grows with the square of it.

The emission term

The emission probability answers: if the vehicle really was at candidate c, how likely was a fix to land where it did? Newson and Krumm model the great-circle distance between the fix and the candidate as zero-mean Gaussian noise:

p(fix | c)  =  (1 / (sqrt(2*pi) * sigma_z)) * exp( -0.5 * (d / sigma_z)^2 )

d       = great-circle distance from the fix to the candidate point, metres
sigma_z = GPS measurement standard deviation, metres

Their paper estimates sigma_z at 4.07 m from the median absolute deviation of their own dataset, and that value has been copied into a great many implementations since. It is theirs, not a constant of nature: fixes from a rooftop antenna in open country and fixes from a phone in a pocket in a street canyon have very different spreads, and fitting sigma_z to your own traces is the single highest-value tuning step available.

The transition term

The transition probability is what nearest-road snapping does not have. Between two consecutive fixes, compare two distances: the straight-line distance between the fixes, and the driving distance along the road network between the two candidates. If a vehicle really travelled that pair of candidates, the two should be similar. If matching fix 2 to a parallel service road requires 900 m of driving to cover 80 m of ground, the pair is implausible.

dt = | great_circle(fix_t, fix_t+1) - route_distance(c_t, c_t+1) |
p(c_t+1 | c_t) = (1 / beta) * exp( -dt / beta )

The exponential is a deliberately heavy-tailed choice: a large dt is punished but not made impossible, so one bad fix cannot veto an otherwise coherent route. beta is a scale in metres, fitted the same way sigma_z is, and it encodes how circuitous you expect real routes to be relative to straight lines. Valhalla’s Meili matcher documents its own default rather than inheriting the paper’s, which is the right instinct — the value depends on your sampling interval, and a trace sampled every 60 seconds needs a much larger beta than one sampled every second.

Viterbi over a worked trace

Take three fixes on a highway with a parallel service road 25 m to the side. Each fix has two candidates, H (highway) and S (service road). The fixes happen to sit closer to the service road:

fix 1: d(H) = 22 m   d(S) =  8 m
fix 2: d(H) = 19 m   d(S) = 11 m
fix 3: d(H) = 24 m   d(S) =  9 m

emission, sigma_z = 4.07 m, as -log values (smaller is better):
  0.5*(22/4.07)^2 = 14.6      0.5*(8/4.07)^2  = 1.93
  0.5*(19/4.07)^2 = 10.9      0.5*(11/4.07)^2 = 3.65
  0.5*(24/4.07)^2 = 17.4      0.5*(9/4.07)^2  = 2.44

pure nearest-road: S, S, S   total emission cost 8.02

Now the transitions. The fixes are 400 m apart in straight line. Staying on the highway costs about 400 m of route distance, so dt ≈ 0. But the service road, in this network, has no continuous link between the two candidate points: getting from candidate S1 to S2 requires exiting, crossing at a junction and returning, 1,100 m of driving. So dt ≈ 700 m for each S→S hop. With beta = 30 m, the transition cost dt / beta is about 23 per hop, over 46 for the pair — which swamps the 15-point emission advantage the service road had. Viterbi returns H, H, H. The vehicle stays on the highway, which is where it was.

Viterbi does this in one pass. For each candidate at step t + 1 it keeps only the best predecessor and the running cost, so the work is O(T × k²) for T fixes with k candidates each, not exponential in the trace length. The expensive part is not the dynamic programming; it is the k² shortest-path queries per step against the road network, and that is what the routing engine underneath is spending its time on.

Where it still breaks

• Sparse sampling. At one fix per minute a vehicle covers a kilometre between observations and many routes are equally plausible. The paper’s own experiments degrade with sampling interval, and no formulation fixes information that was never recorded.
• Stationary vehicles. A parked vehicle emits fixes that wander. Route distance between wandering candidates is nonzero while ground distance is near zero, so dt is large and the matcher invents motion. Filter out fixes below a speed threshold before matching.
• Map error. If the road is missing from the network — a new estate, a private service yard — the correct answer is not in the candidate set and the matcher confidently returns the best wrong one. A per-fix emission cost that stays high across a run is the signal to look for.
• Direction on a two-way segment. The HMM gives you the segment, not the side or the heading. That is a separate problem with its own set of causes.