Geometric Algorithms for Constructing Road Networks from Trajectories

This page describes the scope and results funded by the following grant:

9/1/12 - 8/31/16	"AF: Small: Geometric Algorithms for Constructing Road Networks from Trajectories", National Science Foundation, NSF CCF-1301911, $303,624. PI: Carola Wenk.
	Supplement: 12/13/13 - 8/31/16, $10,001.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Abstract

Vast amounts of geo-referenced trajectory data are being collected due to the ubiquitous availability of positioning technologies such as the Global Positioning System (GPS). This project will help address the very timely challenge of analyzing this data. It will also provide novel algorithms for construction and maintenance of digital street maps, which are among the most valuable digital data resource in today's society. The results of this project will benefit a wealth of applications ranging from a variety of location-based services on street maps to the analysis of tracking data for hiking trail map generation or for studying social behavior in animals. Students will be tightly integrated into research projects, providing them with collaborative research experience.

Collaborators:

• Hee-Kap Ahn, Pohang University of Science and Technology, South Korea
• Helmut Alt, Freie Universität Berlin, Germany
• Maike Buchin, Ruhr-Universität Bochum, Germany
• Brittany Fasy, Montana State University
• Matt Gibson, University of Texas at San Antonio
• Kyle Hickman, Tulane University
• Sophia Karagiorgou, Imis Athena and National Technical University of Athens, Greece
• Eunjin Oh, Pohang University of Science and Technology, South Korea
• Dieter Pfoser, George Mason University

Students:

• Parker Evans
• Selçuk Karakoç
• Sushovan Majhi
• Mahmuda Ahmed, graduated summer 2015, now at Uber.

Publications:

• "Map Construction Algorithms", (M. Ahmed, S. Karagiorgou, D. Pfoser, C. Wenk), Springer, 2015.
• "Path-Based Distance for Street Map Comparison", (M. Ahmed, B.T. Fasy, K.S. Hickmann, C. Wenk), ACM Transactions on Spatial Algorithms and Systems (TSAS) 1(1): article 3, 28 pages, 2015. (arXiv:1309.6131)
• "A Comparison and Evaluation of Map Construction Algorithms", (M. Ahmed, S. Karagiorgou, D. Pfoser, C. Wenk), Geoinformatica 19(3): 601-632, 2015. (arXiv:1402.5138)
• "A Middle Curve Based on Discrete Fréchet Distance", (H.-K. Ahn, H. Alt, M. Buchin, E. Oh, L. Scharf, C. Wenk), Proc. 12th Latin American Theoretical Informatics Symposium: 14-26, 2016.
• "Choosing Thresholds for Density-Based Map Construction Algorithms", (M. Ahmed, B.T. Fasy, M. Gibson, C. Wenk), International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), 2015.
• "Local Persistent Homology Based Distance Between Maps", (M. Ahmed, B.T. Fasy, C. Wenk), International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), 10 pages, 2014.
• "A Comparison and Evaluation of Map Construction Algorithms", (M. Ahmed, S. Karagiorgou, D. Pfoser, C. Wenk), ArXiv: 1402.5138, 2014.
• "Path-Based Distance for Street Map Comparison", (M. Ahmed, B.T. Fasy, K.S. Hickmann, C. Wenk), ArXiv: 1309.6131, 2013.
• Path-based distance measure code for map comparison, 2013. Available at mapconstruction.org.
• Map Construction Portal, mapconstruction.org, (M. Ahmed, S. Karagiourgou, D. Pfoser, C. Wenk), since 2013.
• "Probabilistic Street-Intersection Reconstruction from GPS Trajectories: Approaches and Challenges", (M. Ahmed and C. Wenk), ACM SIGSPATIAL International Workshop on Querying and Mining Uncertain Spatio-Temporal Data, Redondo Beach, CA, 2012.
• "Constructing Street Networks from GPS Trajectories", (M. Ahmed and C. Wenk), European Symposium on Algorithms (ESA): 60-71, Ljubljana, Slovenia, 2012. [slides]
• Fréchet-based map construction code, 2013. Based on: "Constructing Street Networks from GPS Trajectories", (M. Ahmed and C. Wenk), European Symposium on Algorithms (ESA): 60-71, Ljubljana, Slovenia, 2012. Available on mapconstruction.org; integrated into Google's codebase.
• "Constructing Street-Maps from GPS Trajectories", (M. Ahmed, C. Wenk), 21st Fall Workshop on Computational Geometry (2 pages), City College of New York, Manhattan, NY, 2011.
• "Constructing Street-Maps from GPS Trajectories", (M. Ahmed, C. Wenk), poster, Grace Hopper Celebration of Women in Computing, 2011.

Software:

• Homotopy visualizer: Runnable jar, Sources, README

Related Projects:

• Map-Matching and Routing