Yin Wang
Yanmin Zhu
ABSTRACT
The 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 detects significant portions of GPS traces that do not conform to the existing map, as determined by state-of-the-art Viterbi map matching. When there is sufficient evidence collected, map inference algorithms can automatically update the map. The CrowdAtlas server aggregates exceptional traces from users with the navigation app as well as from other, large-scale data sources. From these it automatically generates high quality map updates, which can be propagated to its navigation app and other interested applications. Using CrowdAtlas app, we mapped out a 4.5 km^2 street block in Shanghai in less than half an hour and built a walking/cycling map of the SJTU campus. Using taxi traces collected from Beijing, we contributed completely computer-generated roads for this large, 61 km of missing roads to OpenStreetMap, the first set of open-source map community.
- GPS dataset. grid.sjtu.edu.cn/mapupdate/.Google Scholar
- NAVTEQ. navteq.com/company_history.htm.Google Scholar
- OsmAnd: OSM Automated Navigation Directions Android app. www.osmand.net.Google Scholar
- Storm: Distributed and fault-tolerant realtime computation. storm-project.net/.Google Scholar
- TomTom Map Update Service. www.tomtom.com/en_gb/maps/map-update-service/.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
- M. Ali, T. Rautman, J. Krumm, and A. Teredesai. ACM SIGSPATIAL Cup 2012. In GIS, 2012. Google ScholarDigital Library
- H. Alt, A. Efrat, G. Rote, and C. Wenk. Matching planar maps. Journal of Algorithms, 49(2):262--283, 2003. Google ScholarDigital Library
- J. Angwin and J. V.-Devries. Apple, Google collect user data. Wall Street Journal, April 2011.Google Scholar
- 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, 2012.Google Scholar
- J. Biagioni and J. Eriksson. Map inference in the face of noise and disparity. In ACM GIS, 2012. Google ScholarDigital Library
- 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 SIGMOD, 2010. Google ScholarDigital Library
- S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle tracking data. In VLDB, 2005. Google ScholarDigital Library
- L. Cao and J. Krumm. From GPS traces to a routable road map. In ACM GIS, 2009. Google ScholarDigital Library
- C. Chen and Y. Cheng. Roads digital map generation with multi-track GPS data. In International Workshop on Geoscience and Remote Sensing, 2008. Google ScholarDigital Library
- D. Chen, D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. In SODA, 2010. Google ScholarDigital Library
- Y. Chen and J. Krumm. Probabilistic modeling of traffic lanes from GPS traces. In ACM GIS, 2010. Google ScholarDigital Library
- T. Cook. A letter from Tim Cook on maps, 2012. apple.com/letter-from-tim-cook-on-maps.Google Scholar
- 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
- D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica, 10(2):112--122, Oct. 1973.Google ScholarCross Ref
- B. Dudley. Google Maps gets bike routes, built in Fremont. The Seattle Times, March 2011.Google Scholar
- S. Edelkamp and S. Schrödl. Route planning and map inference with global positioning traces. In Computer Science in Perspective, p.128--151, 2003. Google ScholarDigital Library
- J. Eriksson et al. The pothole patrol: using a mobile sensor network for road surface monitoring. In MobiSys, 2008. Google ScholarDigital Library
- R. Gordon and J. Tucker. Ruling paves way for San Francisco bike lanes. San Francisco Chronicle, August 2010.Google Scholar
- M. Haridasan, I. Mohomed, D. Terry, C. A. Thekkath, and L. Zhang. Startrack next generation: A scalable infrastructure for track-based applications. In OSDI, 2010. Google ScholarDigital Library
- B. Hoh, M. Gruteser, R. Herring, J. Ban, D. B. Work, J. C. Herrera, A. M. Bayen, M. Annavaram, and Q. Jacobson. Virtual trip lines for distributed privacy-preserving traffic monitoring. In MobiSys, 2008. Google ScholarDigital Library
- J. Hu, A. Razdan, J. Femiani, M. Cui, and P. Wonka. Road network extraction and intersection detection from aerial images by tracking road footprints. IEEE T. Geoscience and Remote Sensing, 45(12--2):4144--4157, 2007.Google Scholar
- C. Johnson, C. Shea, and C. Holloway. The role of trust and interaction in GPS related accidents. In Int'l Conference on Systems Safety, 2008.Google Scholar
- S. Karagiorgou and D. Pfoser. On vehicle tracking data-based road network generation. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL '12, pages 89--98, 2012. Google ScholarDigital Library
- B. Kégl, A. Krzyzak, T. Linder, and K. Zeger. Learning and design of principal curves. IEEE Trans. Pattern Anal. Mach. Intell., 22(3):281--297, 2000. Google ScholarDigital Library
- 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 KDD, 2012. Google ScholarDigital Library
- N. Lomas. GPS driving British motorists to distraction. Bloomberg Businessweek, July 2008.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 GIS, 2009. Google ScholarDigital Library
- S. Madden. Keynote: Going big on spatial data. In ACM GIS, 2012.Google Scholar
- A. C. Madrigal. How Google builds its maps. The Atlantic, Sept 2012.Google Scholar
- S. Mathur, T. Jin, N. Kasturirangan, J. Chandrasekaran, W. Xue, M. Gruteser, and W. Trappe. Parknet: drive-by sensing of road-side parking statistics. In MobiSys, 2010. Google ScholarDigital Library
- O. Mazhelis. Using recursive Bayesian estimation for matching GPS measurements to imperfect road network data. In IEEE Conference on Intelligent Transportation Systems, 2010.Google ScholarCross Ref
- B. McClendon (Google VP). Keynote: The path from paper to product: How spatial research reaches users. In ACM GIS, 2012.Google Scholar
- P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In ACM 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 Advances in Satellite and Space Communications, 2009. Google ScholarDigital Library
- J. Paek, J. Kim, and R. Govindan. Energy-efficient rate-adaptive GPS-based positioning for smartphones. In MobiSys, 2010. Google ScholarDigital Library
- S. Reddy, M. Mun, J. Burke, D. Estrin, M. H. Hansen, and M. B. Srivastava. Using mobile phones to determine transportation modes. TOSN, 6(2), 2010. Google ScholarDigital Library
- S. Rogers, P. Langley, and C. Wilson. Mining gps data to augment road models. In KDD, 1999. Google ScholarDigital Library
- S. Schrödl, 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
- Y.-W. Seo, C. Urmson, and D. Wettergreen. Exploiting publicly available cartographic resources for aerial image analysis. In GIS, 2012. Google ScholarDigital Library
- W. Shi, S. Shen, and Y. Liu. Automatic generation of road network map from massive GPS, vehicle trajectories. In IEEE Conf. on Intelligent Transportation Systems, 2009.Google ScholarCross Ref
- R. Sibson. Slink: An optimally efficient algorithm for the single-link cluster method. The Computer Journal, 16(1):30--34, 1973.Google ScholarCross Ref
- A. Skabardonis, T. Chira-Chavala, and D. Rydzewski. The I-880 field experiment: Effectiveness of incident detection using cellular phones. Technical Report UCB-ITS-PRR-98--1, University of California, Berkeley, 1998.Google Scholar
- A. Steiner and A. Leonhardt. A map generation algorithm using low frequency vehicle position data. In Transportation Research Board, 2011.Google Scholar
- A. Thiagarajan et al. Accurate, low-energy trajectory mapping for mobile devices. In NSDI, 2011. Google ScholarDigital Library
- T. Vanderbilt. It wasn't me, officer! It was my GPS. Slate, June 2010. www.slate.com.Google Scholar
- N. R. Velaga, N. R. Velaga, M. A. Quddus, and A. L. Bristow. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems. Transportation Research Part C: Emerging Technologies, 17(6):672--683, 2009.Google ScholarCross Ref
- R. Wabash. 9 car accidents caused by Google Maps & GPS. Ranker, April 2012. ranker.com.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
- H. Wei, Y. Wang, G. Forman, Y. Zhu, and H. Guan. Fast Viterbi map matching with tunable weight functions. In GIS, 2012. (SIGSPATIAL Cup). Google ScholarDigital Library
- C. E. White, D. Bernstein, and A. L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research Part C, 8(1--6):91--108, 2000.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
- J. Yoon, B. Noble, and M. Liu. Surface street traffic estimation. In MobiSys, 2007. Google ScholarDigital Library
- J. Yuan, Y. Zheng, X. Xie, and G. Sun. T-Drive: Enhancing driving directions with taxi drivers' intelligence. IEEE Trans. Knowl. Data Eng., 25(1):220--232, 2013. Google ScholarDigital Library
- Y. Zheng, L. Liu, L. Wang, and X. Xie. Learning transportation mode from raw GPS data for geographic applications on the web. In WWW, 2008. Google ScholarDigital Library
Index Terms
- CrowdAtlas: self-updating maps for cloud and personal use
Recommendations
COBWEB: a robust map update system using GPS trajectories
UbiComp '15: Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous ComputingThe accuracy and completeness of a digital map plays a critical role in determining the quality of most location-based services. Unfortunately, road networks change frequently. Consequently, we study the issue of automatic map update in this paper. We ...
Mining large-scale, sparse GPS traces for map inference: comparison of approaches
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data miningWe 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 ...
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