The widespread availability of GPS information in everyday devices such as
cars, smartphones and smart watches make it possible to collect large amount of
geospatial trajectory information. A particularly important, yet technically
challenging, application of this data is to identify the underlying road
network and keep it updated under various changes. In this paper, we propose
efficient algorithms that can generate accurate maps in both batch and online
settings. Our algorithms utilize techniques from graph spanners so that they
produce maps can effectively handle a wide variety of road and intersection
shapes. We conduct a rigorous evaluation of our algorithms over two real-world
datasets and under a wide variety of performance metrics. Our experiments show
a significant improvement over prior work. In particular, we observe an
increase in Biagioni f-score of up to 20% when compared to the state of the art
while reducing the execution time by an order of magnitude. We also make our
source code open source for reproducibility and enable other researchers to
build on our work.

利用 GPS 信息收集了大量的地理轨迹信息，本文提出了高效的算法从中生成准确的地图，严格评估表明与现有工作相比，增加了 Biagioni f-score 并将执行时间减少了一个数量级，并开放源代码以便其他研究人员借鉴。