How to Achieve Accurate GPS Map Matching with ST‑Matching: A Practical Guide

1 Background

As shown in the figure, three GPS points (1, 2, 3) are the vehicle's positioning results, which deviate from the actual road. Map matching is the process of aligning a sequence of sampled latitude‑longitude points with a digital road network, essentially a planar line‑segment pattern‑matching problem (Alt et al., 2003).

In practice, GPS signal quality heavily influences map‑matching results: lower sampling frequency, larger positioning errors, and signal loss all increase mismatching. These issues are common, making it a valuable research problem to maintain high matching accuracy under such conditions.

The ACM SIGSPATIAL competition introduced in 2012 focused on map matching. Three years ago the author participated with Dr. Yang Anran from the National University of Defense Technology, and this post summarizes that work.

2 Map Matching Algorithm Overview

2.1 Classification by Information Used

Existing algorithms can be divided into four categories: geometric, topological, probabilistic, and advanced.

Geometric algorithms consider the geometry between GPS points and roads, such as distance and angle.

Topological algorithms use road network topology to constrain matching.

Probabilistic methods incorporate the probability of GPS points.

Advanced algorithms combine multiple information sources, including Kalman filters, fuzzy‑logic models, and hidden Markov models.

2.2 Classification by Sampled‑Point Range

Based on the range of sampled points considered, algorithms are split into local/incremental (online) and global (offline) methods. Local/incremental algorithms are greedy, fixing one match at a time. Global algorithms search the entire road network for the trajectory that best fits the sampled points, often using Frechet or weak Frechet distances, spatio‑temporal matching, or voting schemes.

2.3 Classification by Sampling Frequency

According to trajectory sampling frequency, algorithms are categorized as:

High‑frequency sampling algorithms (all local methods and some global methods such as Frechet‑based discrimination).

Low‑frequency sampling algorithms (e.g., ST‑matching, IVVM).

Generally, a sampling interval ≥30 s is considered low‑frequency, while 1 s–10 s is high‑frequency.

3 Our Training Data

a) Road network data: Washington State, USA (1.28 million edges).

b) GPS data: sampling frequency 1–30 s.

4 Adopted Algorithm

We employed the ST‑Matching algorithm (Lou et al., 2009), a global method that integrates geometric information (distance between GPS points and roads), topological information (shortest path), and road attributes (speed limits), offering high precision and stability.

4.1 Candidate Set Generation

4.2 Weight Determination

a) Spatial factor weight (Fs)

b) Temporal factor weight (Ft)

5 Experimental Results

(Results are described in the original competition report.)

6 Technical Implementation Highlights

6.1 Map Projection Issue

Problem: The original road‑network coordinates and trajectory points are in different coordinate systems, preventing direct computation.

Solution: Use the PROJ.4 projection library to project both datasets into a unified coordinate system.

6.2 Large Road‑Network Data Loading

Problem: The network contains 1.28 million edges; using C++ new/delete for each edge would require 1.28 million allocations, which is highly inefficient.

Solution: Apply a memory‑pool technique to allocate edge objects in bulk.

6.3 Shortest‑Path Algorithm Choice

Problem: Computing shortest paths between candidate points using Dijkstra’s algorithm is too slow.

Solution: Adopt the heuristic A* algorithm for faster shortest‑path calculations.

6.4 Indexing

Problem: Building a full index is unnecessary for the competition’s varied test road networks, yet calculating candidate sets without any filtering is inefficient.

Solution: For each GPS point, create a 200 m square around it, build a local sub‑network within that square, and compute candidates only against this reduced dataset.