Robust road map inference through network alignment of trajectories

In this paper we address the challenge of inferring the road network of a city from crowd-sourced GPS traces. While the problem has been addressed before, our solution has the following unique characteristics: (i) we formulate the road network inference problem as a network alignment optimization problem where both the nodes and edges of the network have to be inferred, (ii) we propose both an offline (Kharita) and an online (Kharita∗) algorithm which are intuitive and capture the key aspects of the optimization formulation but are scalable and accurate. The Kharita∗ in particular is, to the best of our knowledge, the first known online algorithm for map inference, (iii) we test our approach on two real data sets and both our code and data sets have been made available for research reproducibility.