[https://www.cs.uic.edu/~jakob/papers/biagioni-trr12.pdf](https://www.cs.uic.edu/~jakob/papers/biagioni-trr12.pdf) is a super nice survey where I almost feel bad to summarize it. Almost.

It is about road map inference in the presence of traces of geo coordinates. So you have many vehicles which log their positions while driving. From this data, you want to infer the latest map.

Problems:
* The map changes: What was a valid map a week ago, might not be anymore (due to construction work, breaking roads, new roads)
* Sensor errors: GPS is not very accurate

## Contributions

* overview over the literature up to 2012 on map generation
* method for the automatic evaluation of generated maps
* an evaluation of three reference algorithms including code
* a [118-h trace data set](https://www.cs.uic.edu/bin/view/Bits/Software) and ground truth map

## How Map Inference Works

* **Preprocess Geo-Traces**: check for unreasonable speed, too extreme acceleration, too abrupt changes
* Inference:
    * k-Means: Reduce candidates to centroid. Works on 3D - 2 coordinates and direction
    * trace merging: Merge edges directly, without reduction
    * kernel density estimation

## Quantitative Evaluation

1. Start at one location in both, the ground truth map and the generated map
2. Follow streets from both and sample points in a fixed range (e.g. each 50cm). Only go in directions that go away from the start
3. Try to match both, ground truth and generated map points. Only match if points are close enough (e.g. a distance of 10cm if this is an acceptable uncertainty). Then use a classification score (e.g. F1)