Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories#

Aftab Ahmed CHANDIO; Nikos TZIRITAS; Fan ZHANG; Ling YIN; Cheng-Zhong XU

doi:10.1631/FITEE.1600027

Your Location：

Home >

Browse articles >

Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories#

Regular Papers | Updated：2022-05-19

- Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories#
- 基于云计算的自适应可调节GPS轨迹地图匹配策略
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 12, Pages: 1305-1319(2016)
- Affiliations：
  
  1Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China
  2Institute of Mathematics and Computer Science, University of Sindh, Jamshoro 70680, Pakistan
  3Department of Electrical and Computer Engineering, Wayne State University, Detroit 48202, USA
- Author bio：
  
  E-mail:chandio.aftab@usindh.edu.pk
  E-mail:zhangfan@siat.ac.cn
- Funds：
- DOI：10.1631/FITEE.1600027
  CLC： TP399;U495
- Received：19 January 2016，
  
  Accepted：11 April 2016，
  
  Published：2016-12
- Accepted：
Scan QR Code
Aftab Ahmed CHANDIO, Nikos TZIRITAS, Fan ZHANG, et al. Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories#[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(12): 1305-1319.
DOI：

Aftab Ahmed CHANDIO, Nikos TZIRITAS, Fan ZHANG, et al. Towards adaptable and tunable cloud-based map-matching strategy for GPS trajectories#[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(12): 1305-1319. DOI： 10.1631/FITEE.1600027.

摘要

智慧城市为智能交通管理和交通网络智能应用的发展提供了巨大推动力。近来，智能交通系统（Intelligent transportation systems

ITSs）和移动位置服务（Location-based services

LBSs）也成为了研究领域的热点。交通领域数据量在快速不断增长，云计算在巨量数据的存储、接入、管理和处理方面有着巨大作用。交通领域相当比例的数据为GPS数据，此类数据具有非频繁、含噪声等特性，这使得维护基于GPS的实时交通软件的服务质量较为困难。在诸多智能交通系统应用中，地图匹配处理起着将GPS观测点准确排列于路网中的关键作用。考虑到准确性时，地图匹配策略的性能由两个连续的GPS观测点间的最短路径决定；另一方面，处理最短路径查询（Processing shortest path queries

SPQs）耗费着较高计算量。现有的地图匹配技术采用固定参数（固定的候选点数量，固定的误差圆半径）的办法，这可能导致确认线路分段时产生不确定性，也可导致低精度结果（或需进行大量SPQ处理以保证精度）。此外，由于采样错误的存在，较高采样时间（大于10 s）内的GPS数据常含有冗余数据，这也导致需要额外的SPQ处理。由于SPQ处理导致的高运算量问题，现有的地图匹配策略并不能实现实时应用。在本文中，我们提出一种实时地图匹配方法（Real-time map-matching

RT-MM）。该方法以云计算为基础，是一种全自适应地图匹配策略，能够应对实时GPS轨迹地图匹配中SPQ处理的关键问题。本研究还通过基于虚拟数据和实际数据的仿真，对所述方法与现有方法的性能进行了比较。

Abstract

Smart cities have given a significant impetus to manage traffic and use transport networks in an intelligent way. For the above reason

intelligent transportation systems (ITSs) and location-based services (LBSs) have become an interesting research area over the last years. Due to the rapid increase of data volume within the transportation domain

cloud environment is of paramount importance for storing

accessing

handling

and processing such huge amounts of data. A large part of data within the transportation domain is produced in the form of Global Positioning System (GPS) data. Such a kind of data is usually infrequent and noisy and achieving the quality of real-time transport applications based on GPS is a difficult task. The map-matching process

which is responsible for the accurate alignment of observed GPS positions onto a road network

plays a pivotal role in many ITS applications. Regarding accuracy

the performance of a map-matching strategy is based on the shortest path between two consecutive observed GPS positions. On the other extreme

processing shortest path queries (SPQs) incurs high computational cost. Current map-matching techniques are approached with a fixed number of parameters

i.e.

the number of candidate points (

) and error circle radius (ECR)

which may lead to uncertainty when identifying road segments and either low-accurate results or a large number of SPQs. Moreover

due to the sampling error

GPS data with a high-sampling period (i.e.

less than 10 s) typically contains extraneous datum

which also incurs an extra number of SPQs. Due to the high computation cost incurred by SPQs

current map-matching strategies are not suitable for real-time processing. In this paper

we propose real-time map-matching (called RT-MM)

which is a fully adaptive map-matching strategy based on cloud to address the key challenge of SPQs in a map-matching process for real-time GPS trajectories. The evaluation of our approach against state-of-the-art approaches is performed through simulations based on both synthetic and real-world datasets.

关键词

Keywords

references

S Brakatsoulas , , , D Pfoser , , , R Salas , , , 等 . . On map-matching vehicle tracking data . . 2005 . . Proc. 31st Int. Conf. on Very Large Data Bases . . 853 - - 864 . . . .

AA Chandio , , , F Zhang , , , TD Memon . . Study on LBS for characterization and analysis of big data benchmarks . . Mehran Univ. Res. J. Eng. Technol. , , 2014 . . 33 ( ( 4 ): ): 432 - - 440 . . . .

AA Chandio , , , N Tziritas , , , CZ Xu . . Big-data processing techniques and their challenges in transport domain . . ZTE Commun. , , 2015a . . 13 ( ( 1 ): ): 50 - - 59 . . . .

AA Chandio , , , N Tziritas , , , F Zhang , , , 等 . . An approach for map-matching strategy of gps-trajectories based on the locality of road networks . . 2015b . . 2nd Int. Conf. on Internet of Vehicles . . 234 - - 246 . . DOI: 10.1007/978-3-319-27293-1_21 http://doi.org/10.1007/978-3-319-27293-1_21 . .

BY Chen , , , H Yuan , , , Q Li , , , 等 . . Map-matching algorithm for large-scale low-frequency floating car data . . Int. J. Geograph. Inform. Sci. , , 2014 . . 28 ( ( 1 ): ): 22 - - 38 . . DOI: 10.1080/13658816.2013.816427 http://doi.org/10.1080/13658816.2013.816427 . .

C Chen , , , Z Liu , , , WH Lin , , , 等 . . Distributed modeling in a MapReduce framework for data-driven traffic flow forecasting . . IEEE Trans. Intell. Transp. Syst. , , 2013 . . 14 ( ( 1 ): ): 22 - - 33 . . DOI: 10.1109/TITS.2012.2205144 http://doi.org/10.1109/TITS.2012.2205144 . .

J Dean , , , S Ghemawat . . MapReduce: simplified data processing on large clusters . . Commun. ACM , , 2008 . . 51 ( ( 1 ): ): 107 - - 113 . . DOI: 10.1145/1327452.1327492 http://doi.org/10.1145/1327452.1327492 . .

EW Dijkstra . . A note on two problems in connexion with graphs . . Numer. Math. , , 1959 . . 1 ( ( 1 ): ): 269 - - 271 . . DOI: 10.1007/BF01386390 http://doi.org/10.1007/BF01386390 . .

SK Fang , , , R Zimmermann . . EnAcq: energy-efficient GPS trajectory data acquisition based on improved map matching . . 2011 . . Proc. 19th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems . . 221 - - 230 . . DOI: 10.1145/2093973.2094004 http://doi.org/10.1145/2093973.2094004 . .

CY Goh , , , J Dauwels , , , N Mitrovic , , , 等 . . Online map-matching based on hidden Markov model for real-time traffic sensing applications . . 2012 . . 15th Int. IEEE Conf. on Intelligent Transportation Systems . . 776 - - 781 . . DOI: 10.1109/ITSC.2012.6338627 http://doi.org/10.1109/ITSC.2012.6338627 . .

H Gonzalez , , , J Han , , , X Li , , , 等 . . Adaptive fastest path computation on a road network: a traffic mining approach . . 2007 . . 33rd Int. Conf. on Very Large Data Bases . . 794 - - 805 . . . .

JS Greenfeld . . Matching GPS observations to locations on a digital map . . 2002 . . Proc. 81st Annual Meeting of the Transportation Research Board . . 1 - - 13 . . . .

ZC He , , , XW She , , , LJ Zhuang , , , 等 . . On-line map-matching framework for floating car data with low sampling rate in urban road networks . . IET Intell. Transp. Syst. , , 2013 . . 7 ( ( 4 ): ): 404 - - 414 . . DOI: 10.1049/iet-its.2011.0226 http://doi.org/10.1049/iet-its.2011.0226 . .

H Hu , , , DL Lee , , , V Lee . . Distance indexing on road networks . . 2006 . . Proc. 32nd Int. Conf. on Very Large Data Bases . . 894 - - 905 . . . .

B Hummel , , , K Tischler . . Robust, GPS-only map matching: exploiting vehicle position history, driving restriction information and road network topology in a statistical framework . . 2005 . . GIS Research UK Conf. . . 68 - - 77 . . . .

T Kajdanowicz , , , P Kazienko , , , W Indyk . . Parallel processing of large graphs . . Fut. Gener. Comput. Syst. , , 2014 . . 32 324 - - 337 . . DOI: 10.1016/j.future.2013.08.007 http://doi.org/10.1016/j.future.2013.08.007 . .

M Kolahdouzan , , , C Shahabi . . Voronoi-based K nearest neighbor search for spatial network databases . . 2004 . . Proc. 30th Int. Conf. on Very Large Data Bases . . 840 - - 851 . . . .

R Kühne , , , R Sch fer , , , J Mikat , , , 等 . . New approaches for traffic management in metropolitan areas . . 2003 . . Proc. IFAC CTS Symp . . . .

Q Li , , , T Zhang , , , Y Yu . . Using cloud computing to process intensive floating car data for urban traffic surveillance . . Int. J. Geograph. Inform. Sci. , , 2011a . . 25 ( ( 8 ): ): 1303 - - 1322 . . DOI: 10.1080/13658816.2011.577746 http://doi.org/10.1080/13658816.2011.577746 . .

X Li , , , J Han , , , JG Lee , , , 等 . . Traffic density-based discovery of hot routes in road networks . . 2007 . . Int. Symp. on Spatial and Temporal Databases . . 441 - - 459 . . DOI: 10.1007/978-3-540-73540-3_25 http://doi.org/10.1007/978-3-540-73540-3_25 . .

ZJ Li , , , C Chen , , , K Wang . . Cloud computing for agent-based urban transportation systems . . IEEE Intell. Syst. , , 2011b . . 26 ( ( 1 ): ): 73 - - 79 . . DOI: 10.1109/MIS.2011.10 http://doi.org/10.1109/MIS.2011.10 . .

K Liu , , , Y Li , , , F He , , , 等 . . Effective map-matching on the most simplified road network . . 2012 . . Proc. 20th Int. Conf. on Advances in Geographic Information Systems . . 609 - - 612 . . DOI: 10.1145/2424321.2424429 http://doi.org/10.1145/2424321.2424429 . .

Y Lou , , , C Zhang , , , Y Zheng , , , 等 . . Map-matching for low-sampling-rate GPS trajectories . . 2009 . . Proc. 17th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems . . 352 - - 361 . . DOI: 10.1145/1653771.1653820 http://doi.org/10.1145/1653771.1653820 . .

G Malewicz , , , MH Austern , , , AJ Bik , , , 等 . . Pregel: a system for large-scale graph processing . . 2010 . . Proc. ACM SIGMOD Int. Conf. on Management of Data . . 135 - - 146 . . DOI: 10.1145/1807167.1807184 http://doi.org/10.1145/1807167.1807184 . .

P Newson , , , J Krumm . . Hidden Markov map matching through noise and sparseness . . 2009 . . Proc. 17th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems . . 336 - - 343 . . DOI: 10.1145/1653771.1653818 http://doi.org/10.1145/1653771.1653818 . .

O Pink , , , B Hummel . . A statistical approach to map matching using road network geometry, topology and vehicular motion constraints . . 2008 . . Proc. 11th Int. IEEE Conf. on Intelligent Transprotation Systems . . 862 - - 867 . . DOI: 10.1109/ITSC.2008.4732697 http://doi.org/10.1109/ITSC.2008.4732697 . .

MA Quddus , , , WY Ochieng , , , RB Noland . . Current map-matching algorithms for transport applications: state-of-the art and future research directions . . Transp. Res. Part C , , 2007 . . 15 ( ( 5 ): ): 312 - - 328 . . DOI: 10.1016/j.trc.2007.05.002 http://doi.org/10.1016/j.trc.2007.05.002 . .

S Seo , , , EJ Yoon , , , J Kim , , , 等 . . HAMA: an efficient matrix computation with the MapReduce framework . . 2010 . . IEEE 2nd Int. Conf. on Cloud Computing Technology and Science . . 721 - - 726 . . DOI: 10.1109/CloudCom.2010.17 http://doi.org/10.1109/CloudCom.2010.17 . .

W Tang , , , D Ren , , , Z Lan , , , 等 . . Toward balanced and sustainable job scheduling for production supercomputers . . Parall. Comput. , , 2013 . . 39 ( ( 12 ): ): 753 - - 768 . . DOI: 10.1016/j.parco.2013.08.007 http://doi.org/10.1016/j.parco.2013.08.007 . .

JR Thomsen , , , ML Yiu , , , CS Jensen . . Effective caching of shortest paths for location-based services . . 2012 . . Proc. ACM SIGMOD Int. Conf. on Management of Data . . 313 - - 324 . . DOI: 10.1145/2213836.2213872 http://doi.org/10.1145/2213836.2213872 . .

S Tiwari , , , S Kaushik . . Scalable method for k optimal meeting points (k-omp) computation in the road network databases . . 2013 . . Int. Workshop on Databases in Networked Information Systems . . 277 - - 292 . . DOI: 10.1007/978-3-642-37134-9_21 http://doi.org/10.1007/978-3-642-37134-9_21 . .

JZ Wang , , , ZJ Wang . . Architecture design of urban intelligent transportation using cloud computing . . Adv. Mater. Res. , , 2013 . . 605-607 2549 - - 2552 . . DOI: 10.4028/www.scientific.net/AMR.605-607.2549 http://doi.org/10.4028/www.scientific.net/AMR.605-607.2549 . .

S Wang . . A cyberGIS framework for the synthesis of cyberinfrastructure, GIS, and spatial analysis . . Ann. Assoc. Am. Geograph. , , 2010 . . 100 ( ( 3 ): ): 535 - - 557 . . DOI: 10.1080/00045601003791243 http://doi.org/10.1080/00045601003791243 . .

S Wang , , , Y Liu . . TeraGrid GIScience gateway: bridging cyberinfrastructure and GIScience . . Int. J. Geograph. Inform. Sci. , , 2009 . . 23 ( ( 5 ): ): 631 - - 656 . . DOI: 10.1080/13658810902754977 http://doi.org/10.1080/13658810902754977 . .

ZY Wang , , , Y Du , , , G Wang , , , 等 . . A quick map-matching algorithm by using grid-based selecting . . 2008 . . Int. Workshop on Education Technology and Training and Geoscience and Remote Sensing . . 306 - - 311 . . DOI: 10.1109/ETTandGRS.2008.217 http://doi.org/10.1109/ETTandGRS.2008.217 . .

C Wenk , , , R Salas , , , D Pfoser . . Addressing the need for map-matching speed: localizing global curve-matching algorithms . . 2006 . . 18th Int. Conf. on Scientific and Statistical Database Management . . 379 - - 388 . . DOI: 10.1109/SSDBM.2006.11 http://doi.org/10.1109/SSDBM.2006.11 . .

GG Yin , , , CZ Xu , , , LY Wang . . Optimal remapping in dynamic bulk synchronous computations via a stochastic control approach . . IEEE Trans. Parall. Distr. Syst. , , 2003 . . 14 ( ( 1 ): ): 51 - - 62 . . DOI: 10.1109/TPDS.2003.1167370 http://doi.org/10.1109/TPDS.2003.1167370 . .

J Yuan , , , Y Zheng , , , C Zhang , , , 等 . . An interactive-voting based map matching algorithm . . 2010 . . 11th Int. Conf. on Mobile Data Management . . 43 - - 52 . . DOI: 10.1109/MDM.2010.14 http://doi.org/10.1109/MDM.2010.14 . .

Y Zheng , , , L Wang , , , R Zhang , , , 等 . . GeoLife: managing and understanding your past life over maps . . 2008 . . 9th Int. Conf. on Mobile Data Management . . 211 - - 212 . . DOI: 10.1109/MDM.2008.20 http://doi.org/10.1109/MDM.2008.20 . .

Y Zheng , , , L Capra , , , O Wolfson , , , 等 . . Urban computing: concepts, methodologies, and applications . . ACM Trans. Intell. Syst. Technol. , , 2014 . . 5 ( ( 3 ): ): 38 DOI: 10.1145/2629592 http://doi.org/10.1145/2629592 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Technology trends in large-scale high-efficiency network computing

MEACC: an energy-efficient framework for smart devices using cloud computing systems

Driftor: mitigating cloud-based side-channel attacks by switching and migrating multi-executor virtual machines

Data center network architecture in cloud computing:review, taxonomy, and open research issues

Related Author

Yusheng XIA

Yujing LIU

Congxi SONG

Na ZHAO

Ziling WEI

Jijun CAO

Yi DAI

Baokang ZHAO

Related Institution

School of Computer, National University of Defense Technology

Academy of Military Science

Department of Computer Science, King Abdulaziz University, Saudi Arabia

Department of Computer Science, University of Sialkot, Sialkot

Department of Computer Science, University of Management and Technology, Sialkot

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰