ACM Trans. Spatial Algorithms and Systems 3(1): 3:1-3:21 (2017)
Abstract. Nowadays, large amounts of tracking data are generated via GPS-enabled devices and other advanced tracking technologies. These constitute a rich source for inferring the structure of transportation networks. In this work, we present a novel methodology for revealing a road network map from vehicle trajectories. Specifically, we propose an enhanced and robust map construction algorithm that is based on segmenting the original tracking data according to different types of movement and then constructing the topology of the road network hierarchically. The segmentation produces separate road network layers, which are then fused into a single network. This provides a more efficient way to addresses the challenges imposed by noisy and low sampling rate trajectories. It also allows for a mechanism to accommodate automatic map maintenance on updates. Thus, the proposed approach overcomes the limitations of existing methods and introduces a map construction algorithm that is robust against heterogeneous and sparse data and capable to incorporate changes and improvements. An experimental evaluation extensively assesses the quality of the proposed methodology by constructing large parts of the road networks of four major cities, namely Athens, Berlin, Vienna, and Chicago, using as input GPS tracking data of utility vehicles and taxi fleets. Our results show significant improvements concerning the spatial accuracy and the quality of the constructed road network over the current state of the art.