Map Matching

The dominant probabilistic framework for map matching. The true road segment is the hidden state, and the noisy GPS point is the observation.

• Emission Probability: Models how likely a GPS point was generated from a specific road segment, typically using a Gaussian distribution over the point-to-segment distance.
• Transition Probability: Models the likelihood of moving from one road segment to another, often comparing the great-circle distance between GPS points to the shortest-path network distance between candidate segments.
• The Viterbi algorithm decodes the most likely sequence of hidden road segments, producing a path that is both spatially close to the raw trace and topologically valid on the road network.

Map matching engines operate in two distinct modes depending on latency requirements and data availability.

• Batch (Offline) Processing: The entire GPS trajectory is available before matching begins. This allows the Viterbi algorithm to consider future points when resolving ambiguous earlier segments, yielding the globally optimal path. Used for fleet analytics and route reconstruction.
• Incremental (Online) Processing: Each GPS point is matched as it arrives in real-time. The engine maintains a set of partial hypotheses and commits to a road segment only after a stabilization delay or when the vehicle has passed a decision point. Essential for live ETA updates and turn-by-turn navigation.
• Sliding Window Hybrid: A practical compromise that runs batch matching on a rolling window of recent points, balancing latency with accuracy.

Pure spatial proximity is insufficient for dense urban canyons or stacked highways. Advanced engines enforce physical and logical constraints.

• Network Connectivity: The matched path must follow legal road transitions. A jump between two nearby but disconnected segments (e.g., separated by a median) is penalized with infinite cost.
• Turn Restrictions: Explicitly models prohibited maneuvers (no left turns, one-way streets) to prevent physically impossible matched paths.
• Speed Bounds: Compares the implied travel speed between consecutive matched points against the road segment's speed limit. A segment requiring 200 km/h to traverse is heavily penalized.
• Tunnel & Canyon Handling: Uses dead reckoning and inertial sensor fusion when GPS signal is lost, maintaining a position estimate until signal reacquisition triggers a re-match.

The road network is modeled as a directed, weighted graph where edges represent road segments and nodes represent intersections. The map matching engine assigns dynamic costs to edges based on real-time context.

• Base Cost: The physical length or free-flow travel time of the segment.
• Emission Cost: The negative log-likelihood of the GPS point given the segment, derived from the HMM emission probability.
• Transition Cost: The negative log-likelihood of the route between two candidate segments, derived from the HMM transition probability.
• Penalty Costs: Added for violating turn restrictions, exceeding speed limits, or deviating from the driver's historical preferred routes.
• The Viterbi algorithm finds the minimum-cost path through this graph, which corresponds to the maximum-likelihood sequence of road segments.

Evaluating a map matching engine requires quantifying both its correctness and its computational efficiency.

• Route Mismatch Fraction (RMF): The percentage of the total trip distance matched to incorrect road segments. The gold-standard metric for accuracy.
• Segment Precision & Recall: Measures whether the engine correctly identifies the specific road segments traversed, treating it as a binary classification per segment.
• Latency (ms per point): The average processing time per GPS point. Online engines target sub-10ms per point to keep pace with 1 Hz GPS streams.
• Throughput (points/sec): The total processing capacity for batch workloads, critical for replaying millions of historical trips.
• Robustness to Noise: Measured by accuracy degradation under increasing GPS error (urban canyons) and sampling intervals (from 1s to 60s).

A statistical framework that models map matching as a sequence of hidden states (true road segments) emitting observable emissions (noisy GPS points). The Viterbi algorithm computes the most probable sequence of road links by balancing emission probability (how close a GPS point is to a candidate road) against transition probability (how likely a vehicle is to move between two segments). HMM-based matchers remain the industry standard for their robustness to urban canyon multipath errors and computational efficiency at scale.

A recursive estimation algorithm that fuses noisy sensor measurements with a motion model to produce statistically optimal position estimates. In map matching, Kalman filters smooth raw GPS trajectories before snapping to the road network, reducing the impact of multipath reflections in dense urban environments. Extended Kalman Filters (EKF) and Unscented Kalman Filters (UKF) handle the non-linear dynamics of vehicle motion more accurately than the linear variant.

A navigation technique that estimates current position by advancing a previously determined fix using inertial sensors (accelerometer, gyroscope) and odometry pulses. When GPS signals are lost in tunnels or parking garages, dead reckoning provides continuous position estimates that map matching algorithms can project onto the road network. Modern systems fuse inertial measurement unit (IMU) data with wheel speed sensors for sub-meter accuracy during signal outages.

A mathematical metric measuring the similarity between two curves that accounts for both location and ordering of points along the curves. Unlike Hausdorff distance, Fréchet distance respects the temporal sequence of trajectory points, making it the preferred evaluation metric for map matching accuracy. It quantifies the minimum leash length required for a person and dog to traverse their respective paths without backtracking.