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},
}

Improved Map Construction using Subtrajectory Clustering

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Jorren Hendriks, Erfan Hosseini Sereshgi, Vera Sacristan, Rodrigo I. Silveira, Jorrick Sleijster, Frank Staals, Carola Wenk

Abstr. 4th ACM SIGSPATIAL Workshop on Location-based Recommendations, Geosocial Networks and Geoadvertising (LocalRec), 2020

@article{improved_bundles2020,
  author = {Buchin, Kevin and Buchin, Maike and  Gudmundsson, Joachim and
                 Hendriks, Jorren and Hosseini Sereshgi, Erfan and
                 Sacristan, Vera and I. Silveira, Rodrigo and Sleijster, Jorrick and
                 Staals, Frank and Wenk, Carola },
  title = {Improved Map Construction using Subtrajectory Clustering},
  journal = {Abstr. 4th ACM SIGSPATIAL Workshop on Location-based Recommendations,
                 Geosocial Networks and Geoadvertising (LocalRec)},
  year = {2020},
  location = {Seattle, Washington, USA},
  numpages = {4},
  category = {trajectories},
  project = {bundles2017},
  doi = {10.1145/3423334.3431451},
  url = {https://dl.acm.org/doi/10.1145/3423334.3431451?cid=81493660306},
}