Road Matching: Definitions, Applications, and Key Algorithms

Introduction Road matching is a fundamental theory in map data processing, essential for many road‑related services. It addresses the problem of determining which road in map B corresponds to a road in map A when no unique IDs are available.

Definition Road matching is a subset of map‑matching theory that focuses on linear features (road networks). It involves mapping a target location onto the actual road network using appropriate algorithms.

Key Aspects of Road Matching

Primary subset of map‑matching theory

Matching mode for vector topological road data

Key for heterogeneous road‑data fusion

Important technique for improving navigation positioning accuracy

Typical Application Scenario

Road matching is most intuitively used in map navigation. Mobile GPS accuracy (~10 m) is insufficient to determine the exact lane (2‑3 m wide). Navigation systems (e.g., Gaode) correct GPS positions by continuously computing the registration relationship between GPS points and the road network, thereby improving positioning precision.

General Methods for Spatial Distance and Curve Similarity

Discrete Point Set Matching uses Euclidean distance to snap random points, suitable for heat‑map generation.

Curve Fitting evaluates similarity between trajectories and road networks, considering length, shape, curvature, topology, direction, distance, and attributes such as traffic rules.

Spatial Distance Measures

Minkowski Distance

Euclidean Distance

Manhattan Distance

Chebyshev Distance

Hamming Distance

Jaccard Similarity Coefficient

Hausdorff Distance

Fréchet Distance

Fréchet Distance

Fréchet distance (also called “dog‑leash distance”) measures the minimum leash length required for a person walking along curve A and a dog along curve B to traverse their paths simultaneously. It is defined as the minimum over all possible parameterizations of the maximum point‑wise distance.

Discrete Fréchet distance evaluates the cost of a paired walk (K‑WALK) between two chains of points, seeking the alignment with minimal total cost.

Global Matching Algorithms

When trajectories are long, a many‑to‑many (M:N) global optimization is required. Fréchet distance can be used to weight candidate road segments, construct a network graph, and compute the shortest path for the best overall match.

Hidden Markov Model (HMM) for Road Matching

HMM, originally developed for speech recognition, is now widely applied to map matching due to its high accuracy. An HMM consists of hidden states, observable states, transition matrix A, emission matrix B, and initial state distribution π. The Viterbi algorithm finds the most probable hidden state sequence given observed GPS points.

Open‑source implementations (e.g., Graphhopper‑mapmatching) use HMM for map matching.

HMM‑based matching solves three problems: decoding the hidden road sequence, handling observation noise, and providing robust global alignment.

Industry Recognition

The 2012 ACM SIGSPATIAL Cup, a global competition on map‑matching algorithms, highlighted that the two most accurate submissions were HMM‑based.

Business Applications

Road matching is used in automated projects for trajectory fitting, automatic road identification, heterogeneous data fusion, traffic data mining, urban planning, and more.