Abstract
Map construction methods automatically produce and/or update street map datasets using vehicle tracking data. Enabled by the ubiquitous generation of geo-referenced tracking data, there has been a recent surge in map construction algorithms coming from different computer science domains.This chapter gives a comprehensive overview and comparison of the various algorithms by identifying and focusing on three emerging categories of map construction algorithms. For each category, the general algorithmic idea and a high-level description of the respective algorithms are presented. The overview is complemented by a detailed discussion of several representative algorithms in the following chapters.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Aanjaneya, M., Chazal, F., Chen, D., Glisse, M., Guibas, L.J., Morozov, D.: Metric graph reconstruction from noisy data. In: Proceedings of 27th ACM Symposium on Computational Geometry, pp. 37–46 (2011)
Agamennoni, G., Nieto, J.I., Nebot, E.M.: Robust inference of principal road paths for intelligent transportation systems. IEEE Trans. Intell. Transp. Syst. 12(1), 298–308 (2011)
Ahmed, M., Wenk, C.: Constructing street networks from GPS trajectories. In: Proceedings of 20th Annual European Symposium on Algorithms, pp. 60–71 (2012)
Ahmed, M., Karagiorgou, S., Pfoser, D., Wenk, C.: A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 19(3), 601–632 (2015)
Biagioni, J., Eriksson, J.: Inferring road maps from global positioning system traces: survey and comparative evaluation. Transp. Res. Rec. J. Transp. Res. Board 2291, 61–71 (2012)
Biagioni, J., Eriksson, J.: Map inference in the face of noise and disparity. In: Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 79–88 (2012)
Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of 31st VLDB Conference, pp. 853–864 (2005)
Bruntrup, R., Edelkamp, S., Jabbar, S., Scholz, B.: Incremental map generation with GPS traces. In: Proceedings of IEEE Intelligent Transportation Systems, pp. 574–579 (2005)
Cao, L., Krumm, J.: From GPS traces to a routable road map. In: Proceedings of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 3–12 (2009)
Chazal, F., Huang, R., Sun, J.: Gromov-Hausdorff approximation of filament structure using Reeb-type graph. Discret. Comput. Geom. 53(3), 621–649 (2015)
Chen, C., Cheng, Y.: Roads digital map generation with multi-track GPS data. In: Proceedings of Workshops on Education Technology and Training, and on Geoscience and Remote Sensing, pp. 508–511. IEEE (2008)
Chen, D., Guibas, L.J., Hershberger, J.E., Sun, J.: Road network reconstruction for organizing paths. In: Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 1309–1320 (2010)
Davies, J.J., Beresford, A.R., Hopper, A.: Scalable, distributed, real-time map generation. IEEE Pervasive Comput. 5(4), 47–54 (2006)
Edelkamp, S., Schrödl, S.: Route planning and map inference with global positioning traces. In: Computer Science in Perspective, pp. 128–151. Springer, Berlin (2003)
Efentakis, A., Brakatsoulas, S., Grivas, N., Lamprianidis, G., Patroumpas, K., Pfoser, D.: Towards a flexible and scalable fleet management service. In: Proceedings of 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 79–84 (2013)
Fathi, A., Krumm, J.: Detecting road intersections from GPS traces. In: Proceedings of 6th International Conference on Geographic Information Science, pp. 56–69 (2010)
Ge, X., Safa, I., Belkin, M., Wang, Y.: Data skeletonization via Reeb graphs. In: Proceedings of 25th Annual Conference on Neural Information Processing Systems, pp. 837–845 (2011)
Goodchild, M.F.: Citizens as voluntary sensors: spatial data infrastructure in the world of web 2.0. Int. J. Spat. Data Infrastruct. Res. 2, 24–32 (2007)
Guo, T., Iwamura, K., Koga, M.: Towards high accuracy road maps generation from massive GPS traces data. In: Proceedings of IEEE International Geoscience and Remote Sensing Symposium, pp. 667–670 (2007)
Haklay, M., Weber, P.: OpenStreetMap: user-generated street maps. IEEE Pervasive Comput. 7(4), 12–18 (2008)
Jang, S., Kim, T., Lee, E.: Map generation system with lightweight GPS trace data. In: Proceedings of 12th International Conference on Advanced Communication Technology, pp. 1489–1493 (2010)
Karagiorgou, S., Pfoser, D.: On vehicle tracking data-based road network generation. In: Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 89–98 (2012)
Karagiorgou, S., Pfoser, D., Skoutas, D.: Segmentation-based road network construction. In: Proceedings of 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 450–453 (2013)
Kégl, B., Krzyzak, A., Linder, T., Zeger, K.: Learning and design of principal curves. IEEE Trans. Pattern Anal. Mach. Intell. 22(3), 281–297 (2000)
Liu, X., Biagioni, J., Eriksson, J., Wang, Y., Forman, G., Zhu, Y.: Mining large-scale, sparse GPS traces for map inference: comparison of approaches. In: Proceedings of 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 669–677 (2012)
Niehofer, B., Burda, R., Wietfeld, C., Bauer, F., Lueert, O.: GPS community map generation for enhanced routing methods based on trace-collection by mobile phones. In: Proceedings of 1st International Conference on Advances in Satellite and Space Communications, pp. 156–161 (2009)
OpenStreetMap (2015). http://www.openstreetmap.org/
OpenStreetMap Foundation: Bulk GPX track data (2013). http://www.blog.osmfoundation.org/2013/04/12/bulk-gpx-track-data/
Quddus, M., Ochieng, W., Noland, R.: Current map-matching algorithms for transport applications: state-of-the art and future research directions. Transp. Res. C Emerg. Technol. 15, 312–328 (2007)
Rogers, S., Langley, P., Wilson, C.: Mining GPS data to augment road models. In: Proceedings of 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 104–113 (1999)
Schroedl, S., Wagstaff, K., Rogers, S., Langley, P., Wilson, C.: Mining GPS traces for map refinement. Data Min. Knowl. Disc. 9, 59–87 (2004)
Shi, W., Shen, S., Liu, Y.: Automatic generation of road network map from massive GPS vehicle trajectories. In: Proceedings of 12th International IEEE Conference on Intelligent Transportation Systems, pp. 48–53 (2009)
Steiner, A., Leonhardt, A.: Map generation algorithm using low frequency vehicle position data. In: Proceedings of 90th Annual Meeting of the Transportation Research Board, pp. 1–17 (2011)
Wang, Y., Liu, X., Wei, H., Forman, G., Chen, C., Zhu, Y.: Crowdatlas: Self updating maps for cloud and personal use. In: Proceedings of 11th International Conference Mobile Systems, Applications and Services (2013)
Worrall, S., Nebot, E.: Automated process for generating digitised maps through GPS data compression. In: Proceedings of Australasian Conference on Robotics and Automation (2007)
Zhang, L., Thiemann, F., Sester, M.: Integration of GPS traces with road map. In: Proceedings of 3rd ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 17–22 (2010)
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Ahmed, M., Karagiorgou, S., Pfoser, D., Wenk, C. (2015). Map Construction Algorithms. In: Map Construction Algorithms. Springer, Cham. https://doi.org/10.1007/978-3-319-25166-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-25166-0_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25164-6
Online ISBN: 978-3-319-25166-0
eBook Packages: Computer ScienceComputer Science (R0)