research-article

GLUE: a Parameter-Tuning-Free Map Updating System

Authors:

Wei WangAuthors Info & Claims

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

Pages 683 - 692

https://doi.org/10.1145/2806416.2806425

Published: 17 October 2015 Publication History

Abstract

Map data are widely used in mobile services, but most maps might not be complete. Updating the map automatically is an important problem because road networks are frequently changed with the development of the city. This paper studies the problem of recovering missing road segments via GPS trajectories, especially low sampled data. Our approach takes the GPS noise into consideration and proposes an effective self-adaptive algorithm. Besides, we propose theoretical models behind all the important parameters to enable self-adaptive parameter setting. To the best of our knowledge, this is the first work that addresses the parameter setting issue successfully to make sure our approach is free of parameter-tuning. In addition, we also propose a quantitative evaluation method for map updating problem. The result shows our algorithm has a much better performance than the existing approaches.

References

[1]

R. K. Balan, K. X. Nguyen, and L. Jiang. Real-time trip information service for a large taxi fleet. In MobiSys'11, pages 99--112, 2011.

Digital Library

[2]

L. Cao and J. Krumm. From gps traces to a routable road map. In GIS'09, pages 3--12, 2009.

Digital Library

[3]

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

Digital Library

[4]

F. V. Diggelen. System design & test-gnss accuracy-lies, damn lies, and statistics. GPS World, 18(1):26--33, 2007.

[5]

S. Edelkamp and S. Schrödl. Route planning and map inference with global positioning traces. In Computer Science in Perspective, pages 128--151. 2003.

[6]

J. Han and M. Kamber. Data mining: concepts and techniques. 2001.

Digital Library

[7]

B. Kégl, A. Krzyzak, T. Linder, and K. Zeger. Learning and design of principal curves. TPAMI, 22(3):281--297, 2000.

Digital Library

[8]

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'12, pages 669--677, 2012.

Digital Library

[9]

X. Liu, Y. Zhu, Y. Wang, G. Forman, L. M. Ni, Y. Fang, and M. Li. Road recognition using coarse-grained vehicular traces. HP Labs2012, 2012.

[10]

Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate gps trajectories. In GIS'09, pages 352--361, 2009.

Digital Library

[11]

M. Mokhtarzade and M. Zoej. Road detection from high-resolution satellite images using artificial neural networks. JAG, 9(1):32--40, 2007.

[12]

P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In GIS'09, pages 336--343, 2009.

Digital Library

[13]

W. Y. Ochieng, M. Quddus, and R. B. Noland. Map-matching in complex urban road networks. Revista Brasileira de Cartografia, 2(55), 2009.

[14]

B. P. Phuyal. Method and use of aggregated dead reckoning sensor and gps data for map matching. In GNSS'01, pages 430--437, 2001.

[15]

S. Schroedl, K. Wagstaff, S. Rogers, P. Langley, and C. Wilson. Mining gps traces for map refinement. DMKD, 9(1):59--87, 2004.

Digital Library

[16]

R. Song, W. Lu, W. Sun, Y. Huang, and C. Chen. Quick map matching using multi-core cpus. In GIS'12, pages 605--608, 2012.

Digital Library

[17]

P.-N. Tan, M. Steinbach, V. Kumar, et al. Introduction to data mining, volume 1. 2006.

Digital Library

[18]

Y. Wang, X. Liu, H. Wei, G. Forman, C. Chen, and Y. Zhu. Crowdatlas: Self-updating maps for cloud and personal use. In Mobisys'13, pages 27--40, 2013.

Digital Library

[19]

H. Wei, Y. Wang, G. Forman, Y. Zhu, and H. Guan. Fast viterbi map matching with tunable weight functions. In GIS'12, pages 613--616, 2012.

Digital Library

[20]

C. E. White, D. Bernstein, and A. L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies, 8(1):91--108, 2000.

[21]

J. Yuan, Y. Zheng, C. Zhang, X. Xie, and G.-Z. Sun. An interactive-voting based map matching algorithm. In MDM'10, pages 43--52, 2010.

Digital Library

[22]

Y. Zheng, Q. Li, Y. Chen, X. Xie, and W. Ma. Understanding mobility based on GPS data. In UbiComp'08, pages 312--321, 2008.

Digital Library

Cited By

Wang SWang ZRuan SHan HXiong KYuan HYuan ZLi GBao JZheng Y(2024)DelvMap: Completing Residential Roads in Maps Based on Couriers’ Trajectories and Satellite ImageryIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.336583362(1-14)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3365833
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
Zhao LMao JPu MLiu GJin CQian WZhou AWen XHu RChai H(2020)Automatic Calibration of Road Intersection Topology using Trajectories2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00145(1633-1644)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00145
Show More Cited By

Index Terms

GLUE: a Parameter-Tuning-Free Map Updating System
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

COBWEB: a robust map update system using GPS trajectories
UbiComp '15: Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing

The 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 ...
CrowdAtlas: self-updating maps for cloud and personal use
MobiSys '13: Proceeding of the 11th annual international conference on Mobile systems, applications, and services

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 ...
Network-oriented road map generation for unknown roads using visual images and GPS-based location information

Car navigation systems (CNS) have become an interesting research and industrial topic due to their wide deployment. However, updating and distribution of the road map database is a complex and high cost process. In this paper, we propose a real-time map ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

October 2015

1998 pages

ISBN:9781450337946

DOI:10.1145/2806416

General Chairs:
James Bailey
The University of Melbourne
,
Alistair Moffat
The University of Melbourne
,
Program Chairs:
Charu C. Aggarwal
IBM
,
Maarten de Rijke
University of Amsterdam
,
Ravi Kumar
Google
,
Vanessa Murdock
Microsoft
,
Timos Sellis
RMIT University
,
Jeffrey Xu Yu
Chinese University of Hong Kong

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 ACM 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Shanghai Science and Technology Development Funds
National Natural Science Foundation of China
Shanghai Natural Science Foundation

Conference

CIKM'15

Sponsor:

CIKM'15: 24th ACM International Conference on Information and Knowledge Management

October 18 - 23, 2015

Melbourne, Australia

Acceptance Rates

CIKM '15 Paper Acceptance Rate 165 of 646 submissions, 26%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
285
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang SWang ZRuan SHan HXiong KYuan HYuan ZLi GBao JZheng Y(2024)DelvMap: Completing Residential Roads in Maps Based on Couriers’ Trajectories and Satellite ImageryIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.336583362(1-14)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3365833
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
Zhao LMao JPu MLiu GJin CQian WZhou AWen XHu RChai H(2020)Automatic Calibration of Road Intersection Topology using Trajectories2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00145(1633-1644)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00145
Pu MMao JDu YShen YJin C(2019)Road Intersection Detection Based on Direction Ratio Statistics Analysis2019 20th IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM.2019.00-46(288-297)Online publication date: Jun-2019
https://doi.org/10.1109/MDM.2019.00-46
Chao PHua WZhou X(2019)Trajectories know where map is wrong: an iterative framework for map-trajectory co-optimisationWorld Wide Web10.1007/s11280-019-00721-w23:1(47-73)Online publication date: 14-Aug-2019
https://doi.org/10.1007/s11280-019-00721-w
Cao CLiu ZLi MWang WQin ZMottola LGao JZhang P(2018)Walkway discovery from large scale crowdsensingProceedings of the 17th ACM/IEEE International Conference on Information Processing in Sensor Networks10.1109/IPSN.2018.00009(13-24)Online publication date: 11-Apr-2018
https://dl.acm.org/doi/10.1109/IPSN.2018.00009
Mao JSong QJin CZhang ZZhou A(2018)Online clustering of streaming trajectoriesFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-017-6325-012:2(245-263)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11704-017-6325-0
Wu HSun WZheng BYang LZhou W(2017)CLSTERSProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/31309811:3(1-28)Online publication date: 11-Sep-2017
https://dl.acm.org/doi/10.1145/3130981
Han YSun WZheng B(2017)COMPRESSACM Transactions on Database Systems10.1145/301545742:2(1-49)Online publication date: 10-May-2017
https://dl.acm.org/doi/10.1145/3015457
Mao JWang TJin CZhou A(2017)Feature Grouping-Based Outlier Detection Upon Streaming TrajectoriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.274461929:12(2696-2709)Online publication date: 1-Dec-2017
https://doi.org/10.1109/TKDE.2017.2744619
Show More Cited By

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