Source-linked AI summary
A Comparison and Evaluation of Map Construction Algorithms
Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, Carola Wenk
TL;DR
Map-construction algorithms are difficult to compare because public implementations, benchmark data, and standardized quality measures are scarce. This paper benchmarks seven algorithms on four datasets with four distance measures and releases supporting resources publicly. The evaluation finds a recurring trade-off between map accuracy and coverage, with Karagiorgou offering a reported compromise.
Problem
Map-construction research lacks standardized evidence for comparing algorithms because implementations, benchmark data, and quantitative quality measures are limited.
Method
The paper benchmarks seven map-construction algorithms using four tracking datasets and four distance measures, while making datasets and implementation resources publicly available.
Results
Map-construction algorithms generally produce either accurate maps or good coverage, while Karagiorgou appears to provide a compromise between both.
Takeaways & Limitations
The released platform supports standardized assessment and comparison of road-network construction algorithms and invites expansion with additional algorithms and source code.
Takeaways & Limitations
Quality assessment is constrained because unbiased ground-truth maps matching the tracking-data coverage are difficult to obtain.
Abstract
from arXiv · showhide
Map construction methods automatically produce and/or update road network datasets using vehicle tracking data. Enabled by the ubiquitous generation of georeferenced tracking data, there has been a recent surge in map construction algorithms coming from different computer science domains. A cross-comparison of the various algorithms is still very rare, since (i) algorithms and constructed maps are generally not publicly available and (ii) there is no standard approach to assess the result quality, given the lack of benchmark data and quantitative evaluation methods. This work represents a first comprehensive attempt to benchmark map construction algorithms. We provide an evaluation and comparison of seven algorithms using four datasets and four different evaluation measures. In addition to this comprehensive comparison, we make our datasets, source code of map construction algorithms and evaluation measures publicly available on mapconstruction.org. This site has been established as a repository for map con- struction data and algorithms and we invite other researchers to contribute by uploading code and benchmark data supporting their contributions to map construction algorithms.
1 Introduction
Map construction research lacks standardized quantitative comparison because algorithms, outputs, benchmark data, and suitable evaluation methods are rarely publicly available. This work expands benchmarking by comparing seven algorithms across diverse datasets and quality measures.
- Visual inspection remains the dominant evaluation approach, while only a few studies use quantitative distance measures.
- Cross-comparison remains rare because algorithms and constructed maps are generally unavailable, benchmark data are lacking, and quantitative evaluation is still developing.
- The study evaluates seven state-of-the-art map construction algorithms representing different algorithm classes.
- The benchmark uses four tracking datasets and four distance measures to compare constructed-map quality.
Ge et al.
The paper establishes a shared benchmarking platform with public datasets, algorithms, outputs, and distance-measure implementations. It emphasizes that map-quality judgments depend on the chosen measure, input data, and intended application.
- The compared algorithms include representatives from prior map-construction work, using public implementations where available and author implementations for others.
- The evaluation uses Directed Hausdorff, path-based, shortest-path, and graph-sampling-based distance measures.
- The benchmark combines Chicago, Athens, and Berlin tracking datasets with unmodified OpenStreetMap ground-truth maps covering varied roads, sampling rates, and scales.
- The authors publicly release new benchmark datasets, selected algorithm outputs, and code for three distance measures through mapconstruction.org.
- Different distance measures capture different map features, so algorithm choice depends on input quality and the intended map application rather than a single overall ranking.
2 Map Construction Algorithms
The paper models map construction as transforming vehicle tracks into a street map, focusing on an undirected geometric graph representation. Tracks are sequences of georeferenced, time-stamped measurements, optionally containing vehicle attributes.
- The input consists of tracks, each represented as a sequence of measurements.
- Each measurement contains geographic coordinates and a timestamp, with optional vehicle heading or speed information.
- The desired output is a street map whose representation depends on the application and required granularity.
- The evaluation focuses on an undirected geometric graph with planar vertices and polygonal-curve edges connecting them.
2.1 Related Work
Prior map-construction methods fall into point clustering, incremental track insertion, and intersection linking. These approaches differ in how they transform tracking points or trajectories into street segments and graph structures.
- Point clustering: Point-clustering methods group raw measurements or dense trajectory samples to obtain street segments.
- Point clustering: The k-means approach can use distance and vehicle-heading conditions to seed clusters and incorporates road segmentation, map matching, and lane clustering.
- Point clustering: KDE methods convert point sets into density-based discretized images and work best with frequent sampling or substantial data redundancy.
- Point clustering: Computational-geometry approaches use neighborhood structures such as Voronoi diagrams, Delaunay triangulations, or Vietoris-Rips complexes, assuming densely sampled inputs and offering theoretical guarantees under conditions.
- Incremental track insertion: Incremental track-insertion methods add tracks to an initially empty map, often using map matching, distance measures, and vehicle headings to control additions and deletions.
- Intersection linking: Intersection-linking methods detect intersection vertices first and then connect them by identifying suitable street segments.
2.2 Compared Algorithms
The compared algorithms span incremental track insertion, point clustering, and intersection-linking approaches, using distinct procedures to derive road-network structure from tracking data.
- Incremental track insertion: Ahmed and Wenk’s incremental algorithm partially map-matches each track, inserts unmatched portions, and updates covered edges.Its implementation omits the final minimum-link step used to guarantee an output-complexity bound.
- Incremental track insertion: The physical-attraction incremental approach first groups similar track portions, then inserts edges or vertices using local distance and direction decisions.Nodes are merged when distances are small and trace directions match; otherwise new nodes and edges are created.
- Point clustering: The KDE-based approach computes track density per grid cell, extracts its contour, derives a centerline from a Voronoi diagram, and applies cleanup.A related KDE method constructs successive skeleton maps using high-to-low density thresholds and then map-matches input tracks to the skeleton.
- Point clustering: The k-means point-clustering approach creates road segments with fitted splines and finds lanes by clustering tracks according to distance from the road centerline.
- Topological point clustering: The Reeb-graph approach decomposes densely sampled input points into branches and uses geodesic distances on a proximity graph to extract graph structure.It assumes a densely sampled point set and requires a distance matrix or proximity graph as input.
- Intersection linking: The TraceBundle intersection-linking algorithm detects turn indicators, clusters similar turns, and connects resulting intersection nodes with compacted trajectories.Turn clusters are formed using spatial proximity and turn type; their centroids represent intersection nodes.
3 Quality Measures for Map Comparison
Map quality is evaluated by comparing constructed maps with ground-truth maps using complementary geometric, path-based, and graph-sampling measures. The measures differ in what they capture, including spatial displacement, connectivity, topology, and local similarity.
- Quality evaluation requires both an adequate ground-truth map G and a measure comparing constructed map C with G.
- Unmodified OpenStreetMap maps are used as ground truth, although they generally form a superset of the streets covered by the tracking data.This avoids pruning-related bias but means constructed maps may be only partially matched to the reference.
- Four measures compare the maps: Directed Hausdorff, Ahmed et al.’s path-based distance, shortest-path distance, and graph-sampling distance.The Directed Hausdorff and path-based measures had not previously been used for comparative road-network evaluations.
- The path-based measure represents maps as path sets, compares those sets in the Hausdorff setting, and uses Fréchet distance between individual paths.Fréchet distance accounts for monotonicity and continuity while comparing curves.
- Graph sampling quantifies spurious and missing locations through unmatched marbles and empty holes, combining them with an F-score whose higher value indicates closer agreement.Local sampling also captures detailed geometric and topological similarity.
- Graph-sampling distance can miss a broken connection when a detour exists, whereas the path-based measure checks every adjacency transition around a vertex.Thus, the measures expose different aspects of map similarity rather than a single universal notion of quality.
4 Datasets
The benchmark combines vehicle-tracking datasets from multiple cities with corresponding OpenStreetMap excerpts as ground truth. The selected data vary in vehicle type, sampling rate, trajectory scale, and network size.
- The benchmark datasets contain vehicle trajectories and corresponding ground-truth maps in projected coordinate systems including UTM and GGRS87.Dataset statistics and visualizations are provided for the benchmark collection.
- Datasets span different cities, vehicle types, sampling rates, and network sizes to represent varied tracking conditions.The selection includes datasets beyond other public GPS sources such as GeoLife and OpenStreetMap GPX tracks.
- The Athens large dataset contains 511 school-bus trajectories totaling 6,781 km across a 12 km × 14 km area.Tracks contain 32–80 position samples and use sampling rates from 20 to 30 seconds.
- The Athens small dataset contains 129 tracks totaling 443 km.Its tracks have an average length of 3.82 km and sampling rates ranging from 1 to 29 seconds.
- OpenStreetMap excerpts serve as the ground-truth map for all datasets.
5 Experiments
The experiments compare seven map-construction algorithms across datasets using varied parameter settings and map-complexity summaries. Large datasets support fewer algorithms because some implementations cannot handle their input size.
- 5 Experiments: Seven algorithms were tested, with six experiments conducted by the authors and implementations made available online.The seventh algorithm was run by its authors because its implementation was unavailable to the study authors.
- 5 Experiments: Runtime ranges from 10 minutes to 20 hours on Chicago and from 2 hours to 4 days on Berlin, while some algorithms crash on large inputs.Consequently, results for all algorithms are available only for Athens small and Chicago.
- 5.1 Constructed Maps: The experiments cover small Chicago data and larger Athens and Berlin data, with constructed maps visually compared against ground truth.Figures 11 and 12 show overlays for small Chicago and large Berlin, respectively.
- 5 Experiments: Algorithm parameters differ by dataset and method, including clustering thresholds, proximity values, bearings, and intersection-extraction settings.For example, Ahmed and Wenk’s subtrajectory-clustering values range from 80 to 180 meters across the four datasets.
- 5.1 Constructed Maps: Point-clustering algorithms based on kernel density estimation are among the methods compared in the generated-map complexity analysis.
Davies et al.
The evaluation reveals a persistent trade-off between map accuracy and coverage. Davies’s KDE-based method often produces spatially accurate, compact maps, but may omit infrequently traversed streets and therefore provide limited coverage.
- Coverage: Davies’s maps are unusually small in some datasets, which can prevent quantitative evaluation or reduce the number of computable shortest paths.For Athens small, the map was too small for quantitative evaluation; for Chicago, only 92.6% of sampled paths were computed.
- Evaluation: Shortest-path sampling evaluates both path similarity and map coverage, exposing cases where distance measures alone suggest good quality despite missing paths.Davies for Chicago and Cao for Athens small had favorable distances but computed only 92.6% and 7.0% of 500 sampled paths, respectively.
- Evaluation: Point-based F-score behavior can be misleading as matching thresholds increase, because recall declines for compact maps with missing streets.For Biagioni, Davies and Karagiorgou, precision increased while recall declined, so the authors emphasized precision instead.
- Coverage: KDE-based methods produce fewer vertices and edges but often fail to reconstruct streets that input tracks traverse infrequently.This improves compactness while limiting coverage of less frequently observed roads.
- Accuracy: Davies’s KDE-based maps generally achieve small path-based and Directed Hausdorff distances, indicating strong spatial accuracy.Across the evaluation, Davies is grouped with Biagioni and Karagiorgou as producing comparatively accurate maps.
- Overall comparison: The paper’s broader comparison finds that algorithms commonly favor either accuracy or coverage, while Karagiorgou provides the strongest compromise.Karagiorgou is reported to achieve both good coverage and high path similarity.
6 Conclusions
The paper establishes a standardized basis for comparing road-network construction algorithms by releasing benchmark data, algorithms, and evaluation measures. It presents mapconstruction.org as a repository intended to support broader participation and future automation.
- Contributions: The paper’s benchmark datasets, construction algorithms, and evaluation measures enable standardized assessment and comparison of road-network construction methods.The authors describe this as addressing the prior lack of benchmark data and quantitative evaluation methods.
- Reproducibility: All data, algorithms, and evaluation procedures are made available with detailed execution instructions on mapconstruction.org.The repository is intended to make comparative evaluation reproducible.
- Future work: Future work will expand the repository with more algorithms and source code toward an easy-to-use benchmark suite and automated quality measurements.The stated final goal is broader algorithm coverage and automated evaluation of generated maps.