Inferring Road Maps from Global Positioning System Traces Survey and Comparative Evaluation

As a result of the availability of Global Positioning System (GPS) sensors in a variety of everyday devices, GPS trace data are becoming increasingly abundant. One potential use of this wealth of data is to infer and update the geometry and connectivity of road maps through the use of what are known as map generation or map inference algorithms. These algorithms offer a tremendous advantage when no existing road map data are present. Instead of the expense of a complete road survey, GPS trace data can be used to generate entirely new sections of the road map at a fraction of the cost. In cases of existing maps, road map inference may not only help to increase the accuracy of available road maps but may also help to detect new road construction and to make dynamic adaptions to road closures-useful features for in-car navigation with digital road maps. In past research, proposed algorithms had been evaluated qualitatively with little or no comparison with prior work. This lack of quantitative and comparative evaluation is addressed in this paper with the following contributions: (a) a comprehensive survey of the current literature on map generation; (b) a description of the first method for the automatic evaluation of generated maps; (c) a qualitative, quantitative, and comparative evaluation of three reference algorithms; and (d) an open source implementation of each of the three algorithms, with a 118-h trace data set and ground truth map for unrestricted use by the automatic map generation community.