Map Construction Algorithms...

... tools and data for benchmarking performance!

Overview

Enabled by the ubiquitous generation of geo-referenced tracking data, there has been a recent surge of algorithms that construct street maps from tracking data.

However, visual inspection is still the most common approach to evaluate the quality of the algorithms, and cross-comparison of different algorithms is very rare, since algorithms and constructed maps are generally not publicly available. There is a lack of benchmark data, and quantitative evaluation with suitable distance measures has just recently begun.

This site will provide access to

  • a set of map generation algorithms,
  • data sets including tracking data as well as respective map datasets, and
  • various distance measures to assess the quality of the constructed maps.

As they become available, we encourage interested scientists and developers to make their source code available.

41lwT7YWqfL

Our new book is available. See Amazon or Springer pages for details!

 

Feel free to contact us! We are looking forward to your suggestions and feedback!

 

Algorithms

Survey – Benchmarking Paper

Should you use source code and/or data from this site, please cite the following paper:

M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. A Comparison and Evaluation of Map Construction Algorithms. GeoInformatica, 19(3):601-632, 2015.

DOI: 10.1007/s10707-014-0222-6

Evaluated Algorithms

M. Ahmed and C. Wenk. Constructing street networks from GPS trajectories. In Proc. European Symp. on Algorithms, pages 60–71, 2012.

J. Biagioni and J. Eriksson. Map inference in the face of noise and disparity. In Proc. 20th ACM SIGSPATIAL, pages 79–88, 2012.

L. Cao and J. Krumm. From GPS traces to a routable road map. In Proc. 17th ACM SIGSPATIAL, pages 3–12, 2009.

J. J. Davies, A. R. Beresford, and A. Hopper. Scalable, distributed, real-time map generation. IEEE Pervasive Computing, 5(4):47–54, Oct. 2006.

  • paper
  • presentation
  • code – re-implementation available; download here

S. Karagiorgou and D. Pfoser. On vehicle tracking data-based road network generation. In Proc. 20th ACM SIGSPATIAL, pages 89–98, 2012.

  • paper
  • presentation
  • code – available, download below

S. Karagiorgou and D. Pfoser. Segmentation-Based Road Network Construction. In Proc. 21th ACM SIGSPATIAL GIS Conference, pp. 470-473, 2013.

  • paper
  • presentation
  • code

Additional Algorithms

M. Aanjaneya, F. Chazal, D. Chen, Guibas, and D. Morozov. Metric graph reconstruction from noisy data. In Proc. 27th ACM Symp. on Comp. Geometry, pages 37–46, 2011.

G. Agamennoni, J. I. Nieto, and E. M. Nebot. Robust inference of principal road paths for intelligent transportation systems. Trans. Intell. Transport. Sys., 12(1):298–308, Mar. 2011.

R. Bruntrup, S. Edelkamp, S. Jabbar, and B. Scholz. Incremental map generation with GPS traces. In Proc. IEEE Intelligent Transp. Sys., pages 574 – 579, 2005.

C. Chen and Y. Cheng. Roads digital map generation with multi-track GPS data. In Proc. Workshops on Education Technology and Training, and on Geoscience and Remote Sensing, pages 508–511. IEEE, 2008.

D. Chen, L. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 1309–1320, 2010.

S. Edelkamp and S. Schrödl. Route planning and map inference with global positioning traces. In Computer Science in Perspective, pages 128–151. Springer, 2003.

A. Fathi and J. Krumm. Detecting road intersections from GPS traces. In Proc. 6th Int. Conf. on Geographic Information Science, pages 56–69, 2010.

X. Ge, I. Safa, M. Belkin, and Y. Wang. Data skeletonization via Reeb graphs. In 25th Annual Conf. on Neural Info. Proc. Sys., pages 837–845, 2011.

T. Guo, K. Iwamura, and M. Koga. Towards high accuracy road maps generation from massive GPS traces data. In IEEE Int. Geoscience and Remote Sensing Symp., pages 667–670, 2007.

X. Liu, J. Biagioni, J. Eriksson, Y. Wang, G. Forman, and Y. Zhu. Mining large-scale, sparse GPS traces for map inference: comparison of approaches. In Proc. 18th ACM SIGKDD, pages 669–677, 2012.

COPYRIGHT STATEMENT

All Source Code is made available under the Apache License, Version 2.0 http://www.apache.org/licenses/.

Source Code © by respective contributors as indicated in the NOTICE.txt file that is included with the source code files.

When publishing using the respective software, we ask you to cite the publication as indicated in the NOTICE.txt file.

download button

Data

Athens Large

  • Size: 

athens_large_tracking_data

Athens Small

  • Size:

athens_small_tracking_data

Berlin

  • Size:

berlin_large_tracking_data

Chicago

  • Size:

chicago_tracking_data

 

This material is Open Data COPYRIGHT STATEMENT

All Data (Map and Tracking Data) is made available under the Open Database License: http://opendatacommons.org/licenses/odbl/1.0/.
Any rights in individual contents of the database are licensed under the Database Contents License: http://opendatacommons.org/licenses/dbcl/1.0/ – See more at: http://opendatacommons.org/licenses/odbl/1.0
Map Data © OpenStreetMap contributors.
Tracking Data © Mapconstruction.org Contributors.

download button

Evaluation Methods

Methods and algorithms to evaluate map construction results.

M. Ahmed, B.T. Fasy, K.S. Hickmann, C. Wenk. Path-Based Distance for Street Map Comparison. In ArXiv: 1309.6131, 2013.

S. Karagiorgou and D. Pfoser. On vehicle tracking data-based road network generation. In Proc. 20th ACM SIGSPATIAL, pages 89–98, 2012.

  • paper
  • code for shortest-path map evaluation algorithm – available, download below

COPYRIGHT STATEMENT

All Source Code is made available under the Apache License, Version 2.0 http://www.apache.org/licenses/.

Source Code © by respective contributors as indicated in the NOTICE.txt file that is included with the source code files.

When publishing using the respective software, we ask you to cite the publication as indicated in the NOTICE.txt file.

download button

Examples

Some map generation examples produced by respective algorithms:

Athens Large

Tracking data vs. road network

athens_large_tracking_data_vs_ground_truth

Mahmuda

mahmuda_vs_rn_athens_large

Sophia

sophia_vs_rn_athens_large

Berlin

Tracking data vs. road network

berlin_large_tracking_data_vs_ground_truth

Mahmuda

mahmuda_vs_rn_berlin_large

Sophia

sophia_vs_rn_berlin_large

Chicago

Tracking data vs. road network

chicago_tracking_data_vs_ground_truth

Mahmuda

mahmuda_vs_rn_chicago

Sophia

sophia_vs_rn_chicago

James

james_vs_rn_chicago

Edelkamp

edelkamp_vs_rn_chicago

Davies

davies_vs_rn_chicago

Cao

cao_vs_rn_chicago

Contributors

Mahmuda Ahmed
University of Texas at San Antonio
San Antonio, TX, USA
mahmuda

Sophia Karagiorgou
Institute for the Management of Information Systems
Research Center “ATHENA”
Athens, Greece
sophia

Dieter Pfoser
George Mason University
Department of Geography and Geoinformation Science
4400 University Drive
Fairfax, VA 22032
dieter

Carola Wenk
Department of Computer Science
Tulane University
carola

 

Contact

Please send your questions, suggestions, requests, etc. to contact [at] mapconstruction.org!

Thank you for your interest in this site!

Carola & Dieter

 

Dieter Pfoser

Associate Professor
George Mason University
Department of Geography and Geoinformation Science
4400 University Drive
Fairfax, VA 22032

ggs.gmu.edu
www.dieter.pfoser.org

Carola Wenk

Associate Professor
Tulane University
Department of Computer Science

www.cs.tulane.edu/~carola