A Survey and Quantitative Study on Map Inference Algorithms from GPS Trajectories

Map inference algorithm aims to construct a digital map from other data sources automatically. Due to the labour intensity of traditional map creation and the frequent road change nowadays, map inference is deemed to be a promising solution to automatic map construction and update. However, existing map inference from GPS trajectories suffers from low GPS data quality, which makes the quality of the constructed map unsatisfactory. In this paper, we study the existing map inference algorithms using GPS trajectories. Different from previous surveys, we (1) include the most recent solutions and propose a new categorisation of method; (2) study how different types of GPS errors affect the quality of inference results; (3) evaluate the existing map inference quality measures regarding their ability to identify map quality issues. To achieve these goals, we conduct a comprehensive experimental study on several representative algorithms using both real-world datasets and synthetic datasets, which are generated from our proposed synthetic trajectory generator and artificial map generator. Overall, our study provides insightful observations regarding (1) which inference method performs better in each working scenario, (2) the general data quality requirements for map inference, (3) the direction of future works for quantitative map quality measures.