ROADSTER: Improved algorithms for subtrajectory clustering and map construction

The challenge of map construction involves creating a representation of a travel network using data from the paths traveled by entities within the network. Although numerous algorithms for constructing maps can effectively piece together the overall layout of a network, accurately capturing smaller details like the positions of intersections and turns tends to be more difficult. This difficulty is especially pronounced when the data is noisy or collected at irregular intervals. In this paper we present ROADSTER, a map construction system that combines efficient cluster computation and a sophisticated method to construct a map from a set of such clusters. First, edges are extracted by producing a number of subtrajectory clusters, of varying widths, which naturally correspond to paths in the network. Second, representative paths are extracted from the candidate clusters. The geometry of each representative path is improved in a process involving several stages, that leads to map edges. The rich information obtained from the clustering process is also used to compute map vertices, and to finally connect them using map edges. An experimental evaluation of ROADSTER, using vehicle and hiking GPS data, shows that the system can produce maps of higher quality than previous methods.