How RoadRunner Boosts GPS‑Based Road Network Precision Without Losing Coverage

Introduction

Road network data is essential for many urban applications such as in‑vehicle navigation and route optimization. Traditional road data collection relies on survey vehicles, which consumes large amounts of manpower and resources. The widespread availability of GPS devices generates massive trajectory data, enabling road network inference, but existing methods often suffer from low precision, especially for overpasses, parallel roads, and other complex topologies. RoadRunner aims to increase inference precision in high‑density trajectory areas without sacrificing recall.

RoadRunner Overview

The paper "RoadRunner: Improving the Precision of Road Network Inference from GPS Trajectories" (ACM SIGSPATIAL 2018) proposes a two‑stage framework. First, RoadRunner infers a high‑precision map in regions with dense trajectories. Then, it merges this result with maps generated by traditional methods to satisfy recall requirements. The core idea is to use the connectivity of each trajectory to decide whether intersecting trajectories belong to the same road or to parallel roads.

Algorithm Details

Trace Operation

The Trace operation extracts the dominant outgoing directions of trajectories at an active vertex v. A path‑filtering operator selects sub‑trajectories that pass through a series of circles centered on v. The algorithm samples 72 angles around the vertex, builds small circles at each angle, counts the number of trajectories crossing each circle, smooths the 72‑dimensional count vector with a Gaussian kernel, and detects local peaks to determine main flow directions.

Merge Operation

After a short segment is generated, the Merge operation attempts to integrate it into the existing network. It compares the future trajectory distribution of the new segment’s endpoint with that of neighboring vertices. If the distributions are consistent, the segment is merged; otherwise, the endpoint is added to the active queue for further processing.

Path‑Filtering Operator

To reduce noise, the path‑filtering operator keeps only sub‑trajectories that sequentially pass through a series of circles whose radii approximate road width. For an active vertex, a path of length k is computed, circles are placed along the path, and only trajectories intersecting all circles are retained, effectively isolating the correct road in dense, parallel‑road scenarios.

Experimental Evaluation

The method was evaluated on four US cities (Los Angeles, Boston, Chicago, New York) using 4 km × 4 km study areas and about 60 000 GPS trajectories per city. OpenStreetMap served as the ground‑truth network. Results show that the combined RoadRunner + KDE approach (RR‑2 + BE‑2) reduces error rate by 33.6 % compared with KDE alone, and RoadRunner + k‑Means (RR‑2 + Kharita‑20) reduces error by 60.7 %.

Conclusion

RoadRunner provides a two‑stage road network inference framework that significantly improves precision without compromising recall. By exploiting trajectory connectivity and a selective filtering mechanism, it outperforms traditional KDE and k‑Means based methods, especially in dense urban environments.