Xuemei Liu
Yanmin Zhu
ABSTRACT
We address the problem of inferring road maps from large-scale GPS traces that have relatively low resolution and sampling frequency. Unlike past published work that requires high-resolution traces with dense sampling, we focus on situations with coarse granularity data, such as that obtained from thousands of taxis in Shanghai, which transmit their location as seldom as once per minute. Such data sources can be made available inexpensively as byproducts of existing processes, rather than having to drive every road with high-quality GPS instrumentation just for map building - and having to re-drive roads for periodic updates. Although the challenges in using opportunistic probe data are significant, successful mining algorithms could potentially enable the creation of continuously updated maps at very low cost.
In this paper, we compare representative algorithms from two approaches: working with individual reported locations vs. segments between consecutive locations. We assess their trade-offs and effectiveness in both qualitative and quantitative comparisons for regions of Shanghai and Chicago.
Supplemental Material
- BITS lab trace data. http://www.cs.uic.edu/Bits/Software.Google Scholar
- Open StreetMap. http://www.openstreetmap.org.Google Scholar
- SUVnet-trace data. http:/wirelesslab.sjtu.edu.cn.Google Scholar
- More than 50 crashes on Bay Bridge curve. http://www.usatoday.com/news/nation/2009-11-18-bay-bridge_N.htm, 2009. USA Today.Google Scholar
- G. Agamennoni, J. I. Nieto, and E. M. Nebot. Robust inference of principal road paths for intelligent transportation systems. IEEE Trans. on Intelligent Transportation Systems, 12(1):298--308, 2011. Google ScholarDigital Library
- R. K. Balan, K. X. Nguyen, and L. Jiang. Real-time trip information service for a large taxi fleet. In MobiSys, 2011. Google ScholarDigital Library
- J. Biagioni and J. Eriksson. Inferring road maps from GPS traces: Survey and comparative evaluation. In Transportation Research Board, 91st Annual, 2012.Google Scholar
- A. Biem, E. Bouillet, H. Feng, A. Ranganathan, A. Riabov, O. Verscheure, H. N. Koutsopoulos, and C. Moran. IBM infosphere streams for scalable, real-time, intelligent transportation services. In ACM SIGMOD, 2010. Google ScholarDigital Library
- L. Cao and J. Krumm. From GPS traces to a routable road map. In ACM SIGSPATIAL GIS, 2009. Google ScholarDigital Library
- C. Chen and Y. Cheng. Roads digital map generation with multi-track GPS data. In Int'l. Workshop on Geoscience and Remote Sensing, 2008. Google ScholarDigital Library
- D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. In SODA, 2010. Google ScholarDigital Library
- J. J. Davies, A. R. Beresford, and A. Hopper. Scalable, distributed, real-time map generation. IEEE Pervasive Computing, 5(4):47--54, 2006. Google ScholarDigital Library
- S. Edelkamp and S. Schrödl. Route planning and map inference with global positioning traces. In Computer Science in Perspective, pages 128--151, 2003. Google ScholarDigital Library
- J. Eriksson, L. Girod, B. Hull, R. Newton, S. Madden, and H. Balakrishnan. The pothole patrol: using a mobile sensor network for road surface monitoring. In MobiSys, 2008. Google ScholarDigital Library
- Z. Liao. Real-time taxi dispatching using global positioning systems. Comm. ACM, 46(5):81--83, 2003. Google ScholarDigital Library
- K. Liu, T. Yamamoto, and T. Morikawa. Feasibility of using taxi dispatch system as probes for collecting traffic information. J. Intel. Trans. Sys.: Technology, Planning, and Operations, 13(1):16--27, 2009.Google Scholar
- X. Liu, Y. Zhu, Y. Wang, G. Forman, L. M. Ni, Y. Fang, and M. Li. Road recognition using coarse-grained vehicular footprints. Technical Report HPL-2012-26, HP Labs, 2012.Google Scholar
- Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate GPS trajectories. In ACM SIGSPATIAL GIS, 2009. Google ScholarDigital Library
- P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In ACM SIGSPATIAL GIS, 2009. Google ScholarDigital Library
- B. Niehoefer, R. Burda, C. Wietfeld, F. Bauer, and O. Lueert. GPS community map generation for enhanced routing methods based on trace-collection by mobile phones. In 1st Int'l. Conf. on Advances in Satellite and Space Communications, 2009. Google ScholarDigital Library
- S. Schrödl, K. Wagstaff, S. Rogers, P. Langley, and C. Wilson. Mining GPS traces for map refinement. Data Min. Knowl. Discov., 9(1):59--87, 2004. Google ScholarDigital Library
- W. Shi, S. Shen, and Y. Liu. Automatic generation of road network map from massive GPS, vehicle trajectories. In Intelligent Transportation Systems, International IEEE Conference on, 2009.Google Scholar
- A. Steiner and A. Leonhardt. A map generation algorithm using low frequency vehicle position data. In Transportation Research Board, 90th Annual, 2011.Google Scholar
- Y. Wang, Y. Zhu, Z. He, Y. Yue, and Q. Li. Challenges and opportunities in exploiting large-scale GPS probe data. Technical Report HPL-2011-109, HP Labs, 2011.Google Scholar
- S. Worrall and E. Nebot. Automated process for generating digitised maps through GPS data compression. In Australasian Conference on Robotics and Automation, 2007.Google Scholar
- L. Zhang, F. Thiemann, and M. Sester. Integration of GPS traces with road map. In 2nd Int'l. Workshop on Computational Transportation Science, 2010. Google ScholarDigital Library
Index Terms
- Mining large-scale, sparse GPS traces for map inference: comparison of approaches
Recommendations
CrowdAtlas: self-updating maps for cloud and personal use
MobiSys '13: Proceeding of the 11th annual international conference on Mobile systems, applications, and servicesThe inaccuracy of manually created digital road maps is a persistent problem, despite their high economic value. We present CrowdAtlas, which automates map update based on people's travels, either individually or crowdsourced. Its mobile navigation app ...
Mining large-scale gps streams for connectivity refinement of road maps
SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsAs people increasingly rely on road maps in the digital age, manually maintained maps cannot keep up with the demand for accuracy and freshness, evidenced by the recent iOS map incident and the bidding war for Waze. There are many research works on ...
CrowdAtlas: self-updating maps for cloud and personal use
MobiSys '13: Proceeding of the 11th annual international conference on Mobile systems, applications, and servicesDigital road maps have become essential to many aspects of our lives. Unfortunately, they have persistent quality issues, both in developing countries as well as in developed countries, evidenced by the recent Apple-Google map war. A survey of British ...
Comments