How to Achieve High-Accuracy GPS Map Matching: Algorithms, Data, and Implementation

1 Background

As shown in the figure, three GPS points (1, 2, 3) represent a vehicle’s location but deviate from the actual road. Map matching aligns sampled latitude‑longitude trajectories with a digital road network, essentially a planar line‑segment pattern‑matching problem (Alt et al., 2003).

In practice, GPS signal quality (low sampling frequency, large positioning error, signal loss) severely affects map‑matching accuracy, making robust algorithms a valuable research topic.

The 2012 ACM SIGSPATIAL competition focused on map matching; the author participated with Dr. Yang Anran from the National University of Defense Technology and now summarizes the work.

2 Survey of Map Matching Algorithms

2.1 Classification by Information Used

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

Geometric algorithms consider GPS‑to‑road geometry such as distance and angle.

Topological algorithms use road network topology.

Probabilistic methods incorporate the probability of GPS points.

Advanced algorithms combine comprehensive information, e.g., Kalman filter, fuzzy‑logic models, hidden Markov models.

2.2 Classification by Sampling Scope

Based on the range of sampled points, algorithms are local/incremental (greedy, online) or global (offline). Local methods determine a match point greedily and proceed to the next, while global methods search the entire road network for a trajectory that best fits the sampled points, often using Frechet or weak‑Frechet distance, spatio‑temporal matching, or voting schemes.

2.3 Classification by Sampling Frequency

According to trajectory sampling frequency, algorithms are:

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

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

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

3 Training Data

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

b) GPS data: sampling interval 1‑30 s.

4 Adopted Algorithm

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

4.1 Candidate Set Preparation

4.2 Weight Determination

Spatial factor weight (Fs):

Temporal factor weight (Ft):

5 Experimental Results

6 Key Implementation Points

6.1 Map Projection Issue

Problem: Road network coordinates and trajectory points are in different coordinate systems, preventing direct calculations.

Solution: Use the PROJ.4 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; naïvely allocating and deallocating each edge in C++ would be extremely inefficient.

Solution: Apply a memory‑pool technique to manage edge objects.

6.3 Shortest‑Path Algorithm Choice

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

Solution: Use the heuristic A* algorithm for faster shortest‑path computation.

6.4 Indexing

Problem: Real‑world tests involve many different road networks, making a global index unnecessary, and calculating candidate sets over the entire network is costly.

Solution: Perform spatial slicing around each GPS point (e.g., a 200 m square), build a local sub‑graph within that window, and limit candidate calculations to this subset.