research-article

Choosing thresholds for density-based map construction algorithms

Authors:

Brittany Terese Fasy,

Carola WenkAuthors Info & Claims

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

Article No.: 24, Pages 1 - 10

https://doi.org/10.1145/2820783.2820810

Published: 03 November 2015 Publication History

Abstract

Due to the ubiquitous use of various positioning technologies in smart phones and other devices, geospatial tracking data has become a routine data source. One of its uses that has gained recent popularity is the construction of street maps from vehicular tracking data. Due to the inherent noise in the data, many map construction algorithms are based on thresholding a density function. While kernel density estimation provides a firm theoretical foundation for computing the density from the measurements, the thresholds are generally picked in a heuristic, and often brute-force way, which results in slow algorithms with no guarantees on the map construction quality.

In this paper, we formalize the selection of thresholds in a density-based street map construction algorithm. We propose a new thresholding technique that uses persistent homology combined with statistical analysis to determine a small set of thresholds that captures all relevant topological features. We formally prove that when the samples are drawn uniformly from the street map, a constant number of thresholds suffices to recover the street map. We also provide algorithms to compute the thresholds for different sampling assumptions. Finally, we show the effectiveness of our algorithms in several experiments on artificially generated data and on real GPS trajectory data.

References

[1]

Aanjaneya, M., Chazal, F., Chen, D., Glisse, M., Guibas, L. J., and Morozov, D. Metric graph reconstruction from noisy data. In Proc. SoCG (2011), pp. 37--46.

Digital Library

[2]

Ahmed, M., Fasy, B. T., and Wenk, C. Local persistent homology based distance between maps. In ACM SIGSPATIAL (2014), pp. 43--52.

Digital Library

[3]

Ahmed, M., Karagiorgou, S., Pfoser, D., and Wenk, C. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 19, 3 (2015), 601--632.

Digital Library

[4]

Ahmed, M., and Wenk, C. Constructing street networks from GPS trajectories. In Proc. European Symp. Alg. (2012), pp. 60--71.

Digital Library

[5]

Alexeev, V., Bogaevskaya, V., Preobrazhenskaya, M., Ukhalov, A., Edelsbrunner, H., and Yakimova, O. An algorithm for cartographic generalization that preserves global topology. J Math. Sci. 203, 6 (2014), 754--760.

[6]

Alt, H., Efrat, A., Rote, G., and Wenk, C. Matching planar maps. J. Alg. (2003), 262--283.

Digital Library

[7]

Biagioni, J., and Eriksson, J. Inferring road maps from global positioning system traces: Survey and comparative evaluation. J. Trans. Research Board 2291 (2012), 61--71.

[8]

Biagioni, J., and Eriksson, J. Map inference in the face of noise and disparity. In ACM SIGSPATIAL (2012), pp. 79--88.

Digital Library

[9]

Brakatsoulas, S., Pfoser, D., Salas, R., and Wenk, C. On map-matching vehicle tracking data. In Proc. VLDB Conf. (2005), pp. 853--864.

Digital Library

[10]

Cao, L., and Krumm, J. From GPS traces to a routable road map. In Proc. ACM SIGSPATIAL (2009), pp. 3--12.

Digital Library

[11]

Chen, C., and Cheng, Y. Roads digital map generation with multi-track GPS data. In Proc. Workshops Edu. Tech. Training Geoscience Remote Sensing (2008), IEEE, pp. 508--511.

Digital Library

[12]

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

Digital Library

[13]

Dirnberger, M., Neumann, A., and Kehl, T. NEFI: Network Extraction From Images. arXiv 1502.05241, 2015.

[14]

Edelkamp, S., and Schrödl, S. Route planning and map inference with global positioning traces. In Comput. Sci. Persp. Springer, 2003, pp. 128--151.

Digital Library

[15]

Efentakis, A., Brakatsoulas, S., Grivas, N., Lamprianidis, G., Patroumpas, K., and Pfoser, D. Towards a flexible and scalable fleet management service. In ACM SIGSPATIAL (2013), pp. 79--84.

Digital Library

[16]

Fasy, B. T., Kim, J., Lecci, F., and Maria, C. Introduction to the R package TDA. arXiv 1411.1830, 2014.

[17]

Fasy, B. T., Lecci, F., Rinaldo, A., Wasserman, L., Balakrishnan, S., and Singh, A. Confidence sets for persistence diagrams. Ann. Statistics 42, 6 (2014), 2301--2339.

[18]

Ge, X., Safa, I., Belkin, M., and Wang, Y. Data skeletonization via Reeb graphs. In Proc. Ann. Conf. Neural Inf. Proc. Syst. (2011), pp. 837--845.

[19]

Karagiorgou, S., and Pfoser, D. On vehicle tracking data-based road network generation. In ACM SIGSPATIAL GIS (2012), pp. 89--98.

Digital Library

[20]

Letscher, D., and Fritts, J. Image segmentation using topological persistence. Computer Analysis of Images and Patterns 4673 (2007), 587--595.

Digital Library

[21]

Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., and Huang, Y. Map-matching for low-sampling-rate GPS trajectories. In ACM SIGSPATIAL GIS (2009), pp. 352--361.

Digital Library

[22]

Newson, P., and Krumm, J. Hidden markov map matching through noise and sparseness. In ACM SIGSPATIAL (2009), pp. 336--343.

Digital Library

[23]

Quddus, M., Ochieng, W., and Noland, R. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Trans. Research Part C: Emerging Tech. (2007), 312--328.

[24]

Silverman, B. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.

[25]

Skraba, P., Ovsjanikov, M., Chazal, F., and Guibas, L. Persistence-based segmentation of deformable shapes. In Proc. IEEE Comput. Vis. Pattern Recognition Workshops (June 2010), pp. 45--52.

[26]

Steiner, A., and Leonhardt, A. Map generation algorithm using low frequency vehicle position data. In Proc. Ann. Meeting Trans. Research Board (January 2011), pp. 1--17.

[27]

Thiagarajan, A., Ravindranath, L., LaCurts, K., Madden, S., Balakrishnan, H., Toledo, S., and Eriksson, J. Vtrack: Accurate, energy-aware road traffic delay estimation using mobile phones. In Proc. ACM Conf. Embed. Netw. Sens. Sys. (2009), pp. 85--98.

Digital Library

[28]

Wang, Y., Liu, X., Wei, H., Forman, G., Chen, C., and Zhu, Y. Crowdatlas: Self updating maps for cloud and personal use. In Proc. Int. Conf. Mobile Sys. App. Services (2013).

Digital Library

[29]

Wasserman, L. All of Statistics: A Concise Course in Statistical Inference. Springer Texts in Statistics. Springer, 2013.

Cited By

Majhi S(2023)Vietoris–Rips complexes of metric spaces near a metric graphJournal of Applied and Computational Topology10.1007/s41468-023-00122-z7:4(741-770)Online publication date: 15-May-2023
https://doi.org/10.1007/s41468-023-00122-z
Zhang CLi YXiang LJiao FWu CLi S(2021)Generating Road Networks for Old Downtown Areas Based on Crowd-Sourced Vehicle TrajectoriesSensors10.3390/s2101023521:1(235)Online publication date: 1-Jan-2021
https://doi.org/10.3390/s21010235
Chao PHua WMao RXu JZhou X(2020)A Survey and Quantitative Study on Map Inference Algorithms from GPS TrajectoriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.2977034(1-1)Online publication date: 2020
https://doi.org/10.1109/TKDE.2020.2977034
Show More Cited By

Index Terms

Choosing thresholds for density-based map construction algorithms
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Clustering Trajectories for Map Construction
SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

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 ...
A comparison and evaluation of map construction algorithms using vehicle tracking data

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 ...
Map construction algorithms: an evaluation through hiking data
MobiGIS '16: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems

We study five existing map construction algorithms, designed and tested with urban vehicle data in mind, and apply them to hiking trajectories with different terrain characteristics. Our main goal is to better understand the existing algorithms and to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2015

646 pages

ISBN:9781450339674

DOI:10.1145/2820783

General Chairs:
Mohamed Ali
University of Washington, Tacoma
,
Yan Huang
University of North Texas
,
Program Chairs:
Michael Gertz
Heidelberg University, Germany
,
Matthias Renz
LMU Munich, Germany
,
Jagan Sankaranarayanan
NEC Labs

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SIGSPATIAL'15

Sponsor:

SIGSPATIAL

SIGSPATIAL'15: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 3 - 6, 2015

Washington, Seattle

Acceptance Rates

SIGSPATIAL '15 Paper Acceptance Rate 38 of 212 submissions, 18%;

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Majhi S(2023)Vietoris–Rips complexes of metric spaces near a metric graphJournal of Applied and Computational Topology10.1007/s41468-023-00122-z7:4(741-770)Online publication date: 15-May-2023
https://doi.org/10.1007/s41468-023-00122-z
Zhang CLi YXiang LJiao FWu CLi S(2021)Generating Road Networks for Old Downtown Areas Based on Crowd-Sourced Vehicle TrajectoriesSensors10.3390/s2101023521:1(235)Online publication date: 1-Jan-2021
https://doi.org/10.3390/s21010235
Chao PHua WMao RXu JZhou X(2020)A Survey and Quantitative Study on Map Inference Algorithms from GPS TrajectoriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.2977034(1-1)Online publication date: 2020
https://doi.org/10.1109/TKDE.2020.2977034
Duran DSacristán VSilveira R(2020)Map construction algorithms: a local evaluation through hiking dataGeoInformatica10.1007/s10707-019-00386-7Online publication date: 26-Feb-2020
https://doi.org/10.1007/s10707-019-00386-7
Buchin KBuchin MDuran DFasy BJacobs RSacristan VSilveira RStaals FWenk C(2017)Clustering Trajectories for Map ConstructionProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139964(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139964
Li HKulik LRamamohanarao KMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Automatic Generation and Validation of Road Maps from GPS Trajectory Data SetsProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983797(1523-1532)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983797

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents