Hidden Markov Map Matching
Architecture
Why Map Matching Is Hard
GPS gives a latitude and longitude. The road graph uses segment IDs. Map matching converts one to the other: (lat, lng) → segment_id. Every downstream system depends on this. Traffic aggregation groups speeds by segment. Routing uses segment-level weights. ETA sums segment travel times. If the segment assignment is wrong, everything downstream is wrong.
The problem is ambiguity. GPS accuracy is 5-10m in open sky, 20-50m in urban canyons. A point near a highway overpass could belong to the highway or the road below. Two parallel streets 15m apart produce overlapping GPS traces. An intersection with 4 roads meeting at one point has 4 plausible matches for every GPS point near it.
Simple "snap to nearest road" works most of the time. But it fails exactly where it matters most: at overpasses, parallel roads, and dense intersections. These are high-traffic areas where wrong matches corrupt traffic data for both the correct and incorrect roads.
Basic Terms
| Term | Meaning |
|---|---|
| GPS Point | A raw (lat, lng, speed, heading, timestamp) from a device |
| Candidate Segment | A road segment close enough to a GPS point to be a plausible match |
| Emission Probability | How likely a GPS point was generated by a vehicle on a specific segment. Closer = higher |
| Transition Probability | How likely a vehicle moved from one segment to another between consecutive GPS points |
| Viterbi Path | The most likely sequence of segments for the entire trajectory, found by dynamic programming |
| Sigma (σ) | GPS accuracy parameter. Typically 5-10m. Controls how quickly emission probability drops with distance |
Complete Example
The Setup
A road network with a highway overpass:
Road A (highway, elevated): ═══════════════════════════════
Road B (surface street): ───────────────────────────────
│
Road C (cross street): ───────────┘
Road A runs above Road B. At ground level they are 12m apart vertically, but in 2D GPS coordinates they overlap. Road C connects to Road B at an intersection.
A vehicle drives on the highway (Road A), then takes an exit ramp to the surface street (Road B).
GPS trace: 5 points over 20 seconds.
P1 ──── P2 ──── P3 ──── P4 ──── P5
(on A) (on A) (on A) (exit) (on B)
Step 1: Find Candidate Segments
For each GPS point, find all road segments within 20m:
| GPS Point | Candidates | Why |
|---|---|---|
| P1 | A, B | Both roads within GPS error range |
| P2 | A, B | Same area, both roads overlap in 2D |
| P3 | A, B, C | Near the intersection where C meets B |
| P4 | B, C | Past the exit ramp, highway A is now further away |
| P5 | B | Only surface street in range |
Step 2: Compute Emission Probabilities
For each (GPS point, candidate) pair, measure the perpendicular distance from the point to the road segment. Apply a Gaussian:
P(GPS point | segment) = exp(-distance² / (2 × σ²))
where σ = 8m (GPS accuracy in this urban area)
| GPS Point | Candidate | Distance | P(emission) |
|---|---|---|---|
| P1 | A | 3m | 0.93 |
| P1 | B | 10m | 0.54 |
| P2 | A | 4m | 0.88 |
| P2 | B | 9m | 0.57 |
| P3 | A | 5m | 0.82 |
| P3 | B | 7m | 0.68 |
| P3 | C | 6m | 0.75 |
| P4 | B | 4m | 0.88 |
| P4 | C | 11m | 0.49 |
| P5 | B | 2m | 0.97 |
Looking at emission probabilities alone, P1-P3 favor Road A (highway), P4-P5 favor Road B (surface street). But emission alone is not enough. P3 on Road C has probability 0.75, which is close to P3 on Road A (0.82). Without context, the model might flip between roads.
Step 3: Compute Transition Probabilities
For each pair of consecutive GPS points, compute how plausible the movement is between candidate segments.
Transition score = exp(-|route_distance - gps_distance| / β)
where β = 15m (tolerance for route vs GPS distance mismatch)
P1 → P2 transitions (GPS distance between P1 and P2: 50m):
| From | To | Route distance | Diff | P(transition) |
|---|---|---|---|---|
| A | A | 52m | 2m | 0.88 |
| A | B | 130m (exit ramp) | 80m | 0.005 |
| B | A | 130m (entrance ramp) | 80m | 0.005 |
| B | B | 48m | 2m | 0.88 |
Key insight: moving from A to B or B to A requires using a highway ramp (130m route distance for a 50m GPS displacement). The transition probability is near zero. This is what prevents the model from jumping between the highway and surface street.
P2 → P3 transitions (GPS distance: 55m):
| From | To | Route distance | Diff | P(transition) |
|---|---|---|---|---|
| A | A | 53m | 2m | 0.88 |
| A | B | 120m | 65m | 0.01 |
| A | C | 140m | 85m | 0.003 |
| B | B | 57m | 2m | 0.88 |
| B | C | 30m | 25m | 0.19 |
P3 → P4 transitions (GPS distance: 60m):
| From | To | Route distance | Diff | P(transition) |
|---|---|---|---|---|
| A | B | 75m (exit ramp) | 15m | 0.37 |
| A | C | 90m | 30m | 0.14 |
| B | B | 58m | 2m | 0.88 |
| B | C | 25m | 35m | 0.10 |
| C | B | 25m | 35m | 0.10 |
| C | C | 62m | 2m | 0.88 |
Notice: A→B at P3→P4 has a reasonable transition probability (0.37) because there is an exit ramp here. The route distance (75m) is not wildly different from the GPS distance (60m).
P4 → P5 transitions (GPS distance: 45m):
| From | To | Route distance | Diff | P(transition) |
|---|---|---|---|---|
| B | B | 47m | 2m | 0.88 |
| C | B | 50m | 5m | 0.72 |
Step 4: Viterbi Algorithm
Build a trellis. Each column is a GPS point. Each row is a candidate segment. Each cell stores the best probability of reaching that (point, segment) pair considering all previous points.
Column 1 (P1): Just emission probabilities.
| Candidate | Best prob | Best predecessor |
|---|---|---|
| A | 0.93 | (start) |
| B | 0.54 | (start) |
Column 2 (P2): For each candidate, find the best path from Column 1.
For P2 on A:
- From P1:A → emit(P2|A) × trans(A→A) = 0.93 × 0.88 × 0.88 = 0.72
- From P1:B → emit(P2|A) × trans(B→A) = 0.54 × 0.88 × 0.005 = 0.002
- Best: 0.72 via A
For P2 on B:
- From P1:A → emit(P2|B) × trans(A→B) = 0.93 × 0.57 × 0.005 = 0.003
- From P1:B → emit(P2|B) × trans(B→B) = 0.54 × 0.57 × 0.88 = 0.27
- Best: 0.27 via B
| Candidate | Best prob | Best predecessor |
|---|---|---|
| A | 0.72 | P1:A |
| B | 0.27 | P1:B |
Column 3 (P3):
For P3 on A:
- From P2:A → 0.72 × 0.82 × 0.88 = 0.52
- From P2:B → 0.27 × 0.82 × 0.01 = 0.002
- Best: 0.52 via A
For P3 on B:
- From P2:A → 0.72 × 0.68 × 0.01 = 0.005
- From P2:B → 0.27 × 0.68 × 0.88 = 0.16
- Best: 0.16 via B
For P3 on C:
- From P2:A → 0.72 × 0.75 × 0.003 = 0.002
- From P2:B → 0.27 × 0.75 × 0.19 = 0.038
- Best: 0.038 via B
| Candidate | Best prob | Best predecessor |
|---|---|---|
| A | 0.52 | P2:A |
| B | 0.16 | P2:B |
| C | 0.038 | P2:B |
Column 4 (P4):
For P4 on B:
- From P3:A → 0.52 × 0.88 × 0.37 = 0.17
- From P3:B → 0.16 × 0.88 × 0.88 = 0.12
- From P3:C → 0.038 × 0.88 × 0.10 = 0.003
- Best: 0.17 via A (the vehicle exited the highway)
For P4 on C:
- From P3:A → 0.52 × 0.49 × 0.14 = 0.036
- From P3:B → 0.16 × 0.49 × 0.10 = 0.008
- From P3:C → 0.038 × 0.49 × 0.88 = 0.016
- Best: 0.036 via A
| Candidate | Best prob | Best predecessor |
|---|---|---|
| B | 0.17 | P3:A |
| C | 0.036 | P3:A |
Column 5 (P5):
For P5 on B:
- From P4:B → 0.17 × 0.97 × 0.88 = 0.145
- From P4:C → 0.036 × 0.97 × 0.72 = 0.025
- Best: 0.145 via B
| Candidate | Best prob | Best predecessor |
|---|---|---|
| B | 0.145 | P4:B |
Step 5: Backtrack
Start from the highest probability in the last column: P5:B (0.145).
Trace back through the "best predecessor" pointers:
P5 → B (predecessor: P4:B)
P4 → B (predecessor: P3:A)
P3 → A (predecessor: P2:A)
P2 → A (predecessor: P1:A)
P1 → A (start)
Final matched path: A → A → A → B → B
The vehicle was on the highway (Road A) for the first 3 points, took the exit ramp between P3 and P4, and ended on the surface street (Road B) for the last 2 points.
Why HMM Got This Right (and Nearest-Road Would Fail)
Simple nearest-road matching would assign every point to its closest road:
- P1: A (3m) correct
- P2: A (4m) correct
- P3: C (6m) wrong (should be A at 5m, but C is a valid candidate)
- P4: B (4m) correct
- P5: B (2m) correct
Nearest-road might also flip between A and B for early points since distances are close. HMM avoids this because the transition probability from A→B is near zero without a ramp, and C→B→B is an unlikely trajectory when A→A→B→B (highway to exit) explains the data better.
Performance
| Metric | Value |
|---|---|
| HMM cost per GPS point | ~0.5ms |
| Throughput needed | 50M points/sec |
| Raw CPU cores needed | 25,000 |
| With geometric fast path | ~5,000 cores (80% reduction) |
| Geometric snapping cost | ~0.01ms per point |
The geometric fast path: for GPS points on straight road segments with no ambiguity (one road within 10m, no intersections nearby), skip HMM and snap directly. Reserve HMM for complex areas. Most GPS points fall on unambiguous segments.
Production Pattern
GPS pings → Kafka (partitioned by S2 cell at level 12)
→ Flink (map matching per partition)
→ Output: (segment_id, speed_kmh, timestamp)
→ Redis (segment speed aggregation)
→ Traffic tile builder
Partitioning by S2 cell ensures all GPS points from the same geographic area land on the same Flink task manager. The map matcher loads the local road network into memory once and processes all points in that area. No cross-partition lookups needed.
When Things Go Wrong
Tunnel / parking garage. GPS signal drops. No points for 30-60 seconds. The vehicle exits the tunnel at a different location. Fix: dead reckoning from last known position + speed + heading. When GPS resumes, re-anchor with HMM starting from the first reliable point.
Urban canyons. Tall buildings reflect GPS signals, degrading accuracy from 5m to 50-100m. Fix: discard points where the device reports accuracy > 30m. Use only high-confidence points for map matching. Fewer points means lower throughput but correct matches.
Parallel roads. Two roads 10m apart (highway frontage road). GPS cannot distinguish them. Fix: HMM uses trajectory context. If the last 5 points were on the highway, the 6th is probably still on the highway even if the frontage road is 1m closer.
One-way streets. A GPS trace shows movement against a one-way street. Fix: encode one-way restrictions in the transition probability. The routing distance from A to B going the wrong way is infinity, making the transition probability zero. The model forces the match to a legal segment.
Key Points
- •Map matching converts raw GPS coordinates (lat, lng) into road segment IDs. GPS says 40.7512, -73.9876. The road graph has segment_42 and segment_43. These are different systems. Map matching bridges them. Every downstream operation (traffic aggregation, routing, ETA) depends on this conversion being correct.
- •The Hidden Markov Model treats each GPS point as an observation and each candidate road segment as a hidden state. The emission probability measures how close the GPS point is to the segment (Gaussian, closer = higher). The transition probability measures how realistic the movement is between two segments (routing distance vs GPS distance, similar = higher).
- •The Viterbi algorithm finds the most likely sequence of road segments given the full trajectory. It uses dynamic programming: for each GPS point, compute the best probability of reaching each candidate segment considering all previous points. Then backtrack to recover the path. This is what makes HMM better than simple nearest-road snapping.
- •Simple nearest-road matching fails at overpasses, parallel streets, and intersections. A GPS point 5m from a highway overpass and 8m from the road below would snap to the highway. But if the vehicle was on the surface street for the last 10 points, HMM correctly keeps it on the surface street because the transition probability from surface→highway is low.
- •At 50M GPS points per second, HMM at 0.5ms per point would need 25,000 CPU cores. The optimization: use simple geometric snapping (nearest road within 10m) for unambiguous straight segments. Reserve HMM for complex areas (overpasses, parallel roads, dense intersections). This reduces HMM calls by ~80%, bringing compute down to ~5,000 cores.
- •In production, map matching runs inside Apache Flink on GPS streams partitioned by S2 cell. All GPS points from the same geographic area land on the same partition, so the map matcher has the full local road network in memory. Output is (segment_id, speed, timestamp) fed to downstream traffic aggregation.
Used By
Common Mistakes
- ✗Using nearest-road snapping instead of HMM. Nearest-road works 90% of the time but fails catastrophically at overpasses, parallel roads, and complex intersections. These are exactly the high-traffic areas where accuracy matters most. A vehicle incorrectly matched to a highway overpass instead of the congested road below produces wrong traffic data for both roads.
- ✗Not handling GPS dropouts in tunnels and parking garages. When GPS signal is lost, the vehicle continues moving but produces no points. Naive implementations leave a gap. The fix: dead reckoning from last known position + speed + heading until GPS resumes, then re-anchor with HMM on the first reliable point.
- ✗Setting the GPS accuracy sigma too tight. If sigma is 3m but actual GPS accuracy is 8m in urban canyons, the emission probabilities become too peaked and the model rejects correct matches. Use the device-reported accuracy or a conservative default (5-10m).
- ✗Running HMM on every single GPS point at scale. At 50M points/sec, this is 25,000 CPU cores. The geometric fast path (snap to nearest for unambiguous segments, HMM only for complex areas) reduces this by 80%. Without this optimization, the map matching pipeline becomes the most expensive component in the entire traffic system.
- ✗Ignoring one-way streets and turn restrictions in transition probabilities. If the routing distance from segment A to segment B via legal turns is 500m, but the GPS distance is only 50m, the transition probability should be very low. Without turn restrictions, the model may match vehicles to segments they could not legally reach.