Clustering Trajectories for Map Construction

Abstract

We propose a new approach for constructing the underlying map from trajectory data. Our algorithm is based on the idea that road segments can be identified as stable subtrajectory clusters in the data. For this, we consider how subtrajectory clusters evolve for varying distance values, and choose stable values for these. In doing so we avoid a global proximity parameter. Within trajectory clusters, we choose representatives, which are combined to form the map. We experimentally evaluate our algorithm on vehicle and hiking tracking data. These experiments demonstrate that our approach can naturally separate roads that run close to each other and can deal with outliers in the data, two issues that are notoriously difficult in road network reconstruction.

Corresponding Publications

  • Clustering Trajectories for Map Construction

    Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I. Silveira, Frank Staals, Carola Wenk

    Proc. 25th International Conference on Advances in Geographic Information Systems, 2017
    @inproceedings{bundles2017,
      author = {Buchin, Kevin and Buchin, Maike and Duran, David and
                      Terese Fasy, Brittany and Jacobs, Roel and
                      Sacristan, Vera and I. Silveira, Rodrigo and Staals, Frank and
                      Wenk, Carola},
      title = {Clustering Trajectories for Map Construction},
      booktitle = {Proc. 25th International Conference on Advances in Geographic
                       Information Systems},
      series = {SIGSPATIAL '17},
      year = {2017},
      location = {Redondo Beach, California},
      numpages = {10},
      publisher = {ACM},
      url = {https://dl.acm.org/authorize?N42692},
      doi = {10.1145/3139958.3139964},
      keywords = {trajectory, moving entity, hotspot, geometric algorithms},
      category = {trajectories},
    }