A novel algorithm of low sampling rate GPS trajectories on map-matching

Yankai Liu, Zhuo LiEURASIP 2017 · DOI

Abstract

Map-matching is the essential process of aligning raw GPS coordinates with digital road networks. However, traditional algorithms designed for high-frequency data often fail when sampling intervals increase, leading to significant accuracy drops. This paper proposes a new probabilistic map-matching algorithm specifically designed for low-sampling-rate GPS trajectories (intervals of 1.5 to 2 minutes). By integrating road geometry, network topology, and temporal speed constraints, the algorithm identifies the most likely path through a complex network. A case study using taxi data from Beijing demonstrates that the algorithm maintains high accuracy and stable performance in dense urban environments.

The Challenge of Sparse Data

In many real-world applications, such as fleet management or mobile apps, GPS data is collected at low frequencies to conserve battery life and reduce data transmission costs. While high-frequency data (e.g., one point per second) is easy to match, sparse data creates ambiguity. If a vehicle pings at Point A and then again two minutes later at Point B, there may be several logical paths between them. Standard geometric methods often "snap" points to the nearest road, which can lead to error rates exceeding 50% when the sampling rate is low.

Methodology

The researchers developed a multi-stage probabilistic framework to address these challenges:

  1. Candidate Preparation: To maintain computational efficiency, the system uses a GeoHash algorithm to quickly identify road segments near a GPS point. It then calculates the closest "candidate points" on those segments, narrowing the search to the top five candidates.
  2. Spatial Analysis: The algorithm relies on two hypotheses: Continuity (vehicles tend to stay on a logical path rather than taking unnecessary detours) and Speed Constraints (vehicles are limited by the physical and legal speed limits of the road).
  3. Time and Speed Analysis: This is the core innovation. The algorithm calculates the average speed required to travel between two candidate points and uses a cosine similarity-based formula to compare this against known road constraints. If a path requires a physically impossible speed for that road type, its probability score is reduced.
Vehicle longitudinal trajectories illustrating the ambiguity between parallel road segments.
  1. Result Matching: Finally, the algorithm combines observation probability, transmission probability, and speed information. It utilizes the Dijkstra algorithm to find the shortest path between candidates and selects the sequence of points that maximizes the overall probability function.

Key Insights and Logic

One of the primary strengths of this algorithm is its handling of complex road structures like intersections and parallel roads.

  • Topological Consistency: By looking at the points before and after a specific ping, the algorithm can realize a vehicle likely stayed on a main road even if a specific coordinate is technically closer to a side street.
  • Speed as a Filter: Speed constraints are highly effective at distinguishing between parallel roads, such as a highway running next to a local service road. Even if the roads are geographically close, the vehicle's average speed usually reveals the correct segment.
Trajectory matching across a road network intersection.

Experimental Results

The study evaluated the algorithm using a road network of Beijing (sourced from OpenStreetMap) and real-world trajectory data from the Shenzhou Taxi Company (Beijing UCAR Inc.). The dataset included 1,354 track points with sampling intervals of 1.5 to 2 minutes.

  • High Accuracy: The algorithm achieved a matching accuracy of above 80%, a significant improvement over traditional methods which often hover around 50% for sparse data.
  • Efficiency: The system processed the entire dataset of 1,354 points across 112 road sections in just 3.2 minutes.

Conclusion and Future Work

The proposed algorithm demonstrates that incorporating temporal and speed-based constraints can effectively bridge the gap in low-sampling-rate map-matching. While successful, the authors noted that approximately 20% of errors still occur at complex turning points. Future research will focus on optimizing pathfinding using algorithms like A* or ATL to further reduce processing time and improving logic for erratic vehicle behavior at intersections.

Summary updated

Abstract

Map-matching is the process of matching the GPS locus to the road network on the digital map. However, due to the most existing map-matching algorithms that are based on high sampling rate, when the sampling interval is increased, the correct rate of the algorithm will be greatly reduced. Based on this, this paper proposed a new algorithm of map-matching for low sampling rate GPS trajectories. The algorithm gave full consideration to the road network of the geometric structure and topological structure and the mutual influence between adjacent points (time, speed information) by calculating the probability of each trajectory point of candidate points to determine matching results. At the end of this paper, we use the data of Beijing UCAR Inc.’s car in a case study. This case demonstrates: For low sampling rate matching track points in the complex road, the algorithm has a good uptime, and an exact match was found.
BibTeX
@inproceedings{liu2017novel,
  author = {Yankai Liu and Zhuo Li},
  title = {{A novel algorithm of low sampling rate GPS trajectories on map-matching}},
  booktitle = {EURASIP},
  year = {2017},
  doi = {10.1186/s13638-017-0814-6},
}
Figure