What is Map Matching and Why Does It Matter?

Map matching is the process of aligning noisy GPS observations from a moving vehicle to a road network, then reconstructing the most likely path the vehicle actually took. Raw GPS data suffers from errors of tens of meters, especially in urban canyons where signals reflect off buildings or in areas with poor satellite visibility. A naive approach of simply snapping each point to the nearest road fails catastrophically on parallel roads, flyovers, and one way streets.

Production systems model this as a probabilistic problem using Hidden Markov Models (HMMs) with the Viterbi algorithm. For each GPS point, the system finds candidate road edges within a search radius using spatial indexes, computes an emission probability based on perpendicular distance to each candidate, and calculates transition probabilities between consecutive candidates using both straight line distance and shortest path distance on the road network. This considers both spatial proximity and network topology.

The impact on real systems is massive. At Uber, with 10,000 active vehicles sampling at 30 second intervals, the pipeline processes about 333 location points per second. Accurate map matching prevents billing disputes by computing distance from matched road segments rather than inflated straight line sums, enables correct turn by turn navigation by snapping vehicles to actual lanes, and feeds historical travel time databases for ETA prediction. Without it, a driver taking a parallel service road could be billed for highway miles, or navigation could give impossible turn instructions.

💡 Key Takeaways

•GPS errors of tens of meters are common due to atmospheric delay, multipath reflections, and clock drift, making raw location data unreliable for navigation and billing

•Hidden Markov Models with Viterbi algorithm consider both spatial proximity to road edges and network topology, unlike naive nearest road snap which fails on parallel roads

•At scale, systems like Uber process 333 points per second with 10,000 vehicles at 30 second intervals, requiring spatial indexes and efficient candidate search

•Emission probabilities use perpendicular distance and GPS accuracy, while transition probabilities compare shortest path distance on the road graph versus straight line haversine separation

•Accurate matching prevents billing inflation, enables correct turn by turn instructions, and feeds historical travel time databases for ETA prediction systems

📌 Examples

Uber processes location pings from 10,000 vehicles at 30 second intervals, generating 333 points per second that must be matched to road networks in real time

A driver on a parallel service road with raw GPS showing 50 meter error could be incorrectly billed for highway miles without proper map matching

Google Roads API limits requests to 100 locations per call, while HERE Route Matching v8 caps at 400 points, requiring batching for longer trajectories

← Back to Map Matching & Routing Overview