近年來，隨著GPS裝置廣泛的使用，在都市內產生了大量的車輛GPS軌跡。然而在都市環境下，其道路網路極為複雜，因此衍生出大量的議題，例如道路數量巨量化、道路功能多樣化、道路動態狀態高速變化等等。而這些議題在過去的相關研究中並未被探討。在此研究中，我們利用都市的車輛軌跡和模組性的理念提出了嶄新的地圖匹配演算法，稱為都市地圖匹配(Urban Map-Matching)。為了提升地圖匹配演算法的準確度，我們考慮了時空資訊，包含時空中介性核心性和臨界速度。並且為了增進其執行速度，我們利用時空資訊探勘的結果，將道路網路切割成許多子道路網路，藉此地圖匹配任務也能夠切分成許多較小的子任務，進而達到平行處理。我們方法使用真實資料，並與許多既有的地圖匹配演算法進行比較，實驗結果顯示我們的都市地圖匹配演算法在準確度上有所提升，並且在執行速度上更有顯著的提升。

In recent years, the widespread of GPS devices produces a huge amount of urban trajectories. Due to the complex structure of the road networks in the urban area, many issues arise without being addressed well yet, such as high volume of the road networks, diverse functionalities of roads, and high variance of road dynamics. In this work, we propose a novel modularity-based map-matching algorithm called Urban Map-Matching (UrbMatch) that utilizes urban GPS trajectories. UrbMatch considers the spatial-temporal betweenness and the marginal velocity of each road segment to improve the accuracy of map matching. Based on the results of spatial-temporal mining, a road network is decomposed into several sub-networks such that the map-matching task can be divided into several smaller sub-tasks and run in parallel. Accordingly, the running time can be reduced. We compare UrbMatch with many existing map-matching algorithms using real-world dataset. The results show that our UrbMatch algorithm significantly outperforms the prior works in terms of matching accuracy and execution time.

[1] Beta function: http://en.wikipedia.org/wiki/Beta_function
[2] Open Street Map: http://www.openstreetmap.org/
[3] P-norm: http://en.wikipedia.org/wiki/P-norm
[4] Student's t-test: http://en.wikipedia.org/wiki/Student's_t-test
[5] SUVnet-Trace data: http://wirelesslab.sjtu.edu.cn.
[6] H. Alt, A. Efrat, G. Rote and C. Wenk. Matching Planar Maps. Journal of Algorithms, Volume 49, Issue 2, pp. 262-283, November 2003.
[7] H. Alt and M. Godau. Computing The Fréchet Distance between Two Polygonal Curves. Int. J. Comput. Geom. Appl. Volume 5, pp. 75-91, 1995.
[8] M. Barthélemy. Betweenness Centrality in Large Complex Networks. The European Physical Journal B - Condensed Matter and Complex Systems, Volume 38, Issue 2 , pp. 163-168, 2004.
[9] J. Baus, A. Krüger, and W. Wahlster. A Resource-Adaptive Mobile Navigation System. In Proceedings of the 7th international conference on Intelligent user interfaces(IUI’02), 2002.
[10] A.R. Beresford, and J. Bacon. Intelligent Transportation Systems. Pervasive Computing, Volume 5, No. 4, pp. 63-67, Oct.-Dec. 2006.
[11] S. Brakatsoulas, D. Pfoser, R. Salas and C. Wenk, 2005. On Map-Matching Vehicle Tracking Data. In Proceedings of the 31st international Conference on Very Large Data Bases(VLDB’05), pp. 853-864, 2005.
[12] S.S. Chawathe. Segment-Based Map Matching. In Proceedings of IEEE Symposium on Intelligent Vehicles(IV’07), 2007.
[13] B. Y. Chen, H. Yuan, Q. Li, W. H.K. Lam, S.-L. Shaw, and K. Yan. Map-Matching Algorithm for Large-Scale Low-Frequency Floating Car Data. International Journal of Geographical Information Science, Volume 28, Issue 1, pp. 22-38, 2014.
[14] D. Chen, A. Driemel, L. J. Guibas, A. Nguyen, and C. Wenk. Approximate Map Matching with Respect to the Fréchet Distance. In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX’11), January 2011.
[15] T. Cheng, J. Haworth and J. Wang. Spatio-Temporal Autocorrelation of Road Network Data. Journal of Geographical Systems, Volume 14, Issue 4 , pp. 389-413, October 2012.
[16] A. Comber, C. Brunsdon and E. Green. Using a GIS-Based Network Analysis to Determine Urban Greenspace Accessibility for Different Ethnic and Religious Groups. Landscape and Urban Planning, Volume 86, Issue 1, pp. 103-114, May 2008.
[17] P. Crucitti, V. Latora, S. Porta. Centrality Measures in Spatial Networks of Urban Streets. Phys. Rev. E, Volume 73, Issue 3, March 2006.
[18] Y. Cui, S. S. Ge. Applications of GPS Technology in the Land Transportation System. European Journal of Operational Research, Volume 152, Issue 2, p.p. 399-409, January 2004.
[19] G. Dimitrakopoulos, and P. Demestichas. Intelligent Transportation Systems. Vehicular Technology Magazine, Volume 5, No. 1, pp. 77-84, March 2010.
[20] U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. February 1996.
[21] L. C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, Volume 40, No. 1, pp. 35-41, March 1977.
[22] I.A. Getting. Perspective/navigation-The Global Positioning System. Spectrum, Volume 30, Issue 12,pp. 36-38, December 1993.
[23] C.Y. Goh, J. Dauwels, N. Mitrovic, M. T. Asif, A. Oran, and P. Jaillet. Online Map-Matching Based on Hidden Markov Model for Real-Time Traffic Sensing Applications. In Proceedings of 15th International IEEE Conference on Intelligent Transportation Systems(ITS’12), September 2012.
[24] J. Greenfeld. Matching GPS Observations to Locations on a Digital Map. In Proceedings of 81th Annual Meeting of the Transportation Research Board(TRB’02), 2002.
[25] M.S. Grewal, L.R. Weill, and A.P. Andrews. Global Positioning Systems, Inertial Navigation, and Integration. John Wiley & Sons, 2007.
[26] J. Han, and M. Kamber. Data Mining, Southeast Asia Edition: Concepts and Techniques. Morgan kaufmann, 2006.
[27] J.-H. Haunert, and B. Budig. An Algorithm for Map Matching given Incomplete Road Data. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[28] B. Hillier, and S. Iida. Network Effects and Psychological Effects: A Theory of Urban Movement. In Proceedings of Fifth Space Syntax Symposium, pp. 553-564, 2005.
[29] J. Huang, S. Qiao, H. Yu, J. Qie, and C. Liu. Parallel Map Matching on Massive Vehicle GPS Data Using MapReduce. In Proceedings of 16th IEEE International Conference on High Performance Computing and Communications(HPCC’14), August 2014.
[30] B. Hummel, and K. Tischler. GPS-Only Map Matching: Exploiting Vehicle Position History, Driving Restriction Information and Road Network Topology in a Statistical Framework. In Proceedings of the GIS Research UK Conference(GISRUK’05), pp. 68-77, 2005.
[31] A. Javanmard, M. Haridasan and L. Zhang. Multi-Track Map Matching. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS’13), pp. 394-397, 2012.
[32] X. Kang, W. Wu. An Improved Map Matching Algorithm. Applied Mechanics and Materials, Volumes 256-259, pp. 2947-2952, 2012.
[33] S. Y. Kim, B. J. Park, and J. J. Jung .User Route Analysis of Using GPS on a Mobile Device and Moving Route Recommendation System. The Journal of the Korea Contents Association, Volume 11, Issue 2, pp. 135-141, 2011.
[34] J. Krumm, and E. Horvitz. The Microsoft Multiperson 
Location Survey. Technical Report MSR-TR-2005-103, Microsoft Research, Redmond, WA, USA, 2005.
[35] K.-C. Lan, and Chien-Ming Chou. Realistic Mobility Models for Vehicular Ad hoc Network (VANET) Simulations. In 8th International Conference on ITS Telecommunications(ITST’08), October 2008.
[36] R. Levin, E. Kravi, and Y. Kanza. Concurrent and Robust Topological Map Matching. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[37] N. Li, and G. Chen. Analysis of a Location-Based Social Network. In Proceedings of the 2009 International Conference on Computational Science and Engineering (CSE’09), 2009.
[38] X. Li, M.-L. Li, W. Shu, M. Wu. A Practical Map-Matching Algorithm for GPS-Based Vehicular Networks in Shanghai Urban Area. In Proceedings of Wireless, Mobile and Sensor Networks(CCWMSN07) , 2007.
[39] S. Liu, Z. Shi, M. Zhao, W. Xu, K. Zhang. An Urban Map Matching Algorithm Using Rough Sensor Data. In Proceedings of Workshop on Power Electronics and Intelligent Transportation System(PEITS'08), 2008.
[40] K. Liu, Y. Li, F. He, J. Xu, and Z. Ding. Effective Map-Matching on the Most Simplified Road Network. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[41] Y. Lou , C. Zhang , Y. Zheng , X. Xie , W. Wang , Y. Huang. Map-matching for Low-Sampling-Rate GPS Trajectories. In Proceedings of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’09), November 2009.
[42] E. L. Martelot and C. Hankin. Fast Multi-Scale Detection of Relevant Communities in Large Scale Networks. The Computer Journal, pp.1136-1150, 2013.
[43] R. Meier, A. Harrington, and V. Cahill. A Framework for Integrating Existing and Novel Intelligent Transportation Systems. In Proceedings of Intelligent Transportation Systems 2005(ITSC’05), September 2005.
[44] A. Mislove, M. Marcon, K. P. Gunnadi, P. Druschel, and B. Bhattacharjee. Measurement and Analysis of Online Social Networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (IMC '07), 2007.
[45] A. A. Nanavati, S. Gurumurthy, G. Das, D. Chakraborty, K. Dasgupta, S. Mukherjea, and A. Joshi. On the Structural Properties of Massive Telecom Call Graphs: Findings and Implications. In Proceedings of the 15th ACM International Conference on Information and Knowledge Management (CIKM '06), 2006.
[46] P. Newson, and J. Krumm. Hidden Markov Map Matching Through Noise and Sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’09), pp. 336-343, 2009.
[47] W.Y. Ochieng, M. Quddus, and R.B. Noland. Map-Matching In Complex Urban Road Networks. Brazilian Journal of Cartography, Volume 55 Issue 2, pp. 1-14, 2003.
[48] T. Opsahla, F. Agneessens, and J. Skvoretzc. Node Centrality in Weighted Networks: Generalizing Degree and Shortest Paths. Social Networks, Volume 32, pp. 245-251, July 2010.
[49] T. Osogami, and R. Raymond. Map Matching with Inverse Reinforcement Learning. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), 2013.
[50] A. Páez. Spatial Perspectives on Urban Systems: Developments and Directions. Journal of Geographical Systems, Volume 9, Issue 1, pp. 1-6, 2007.
[51] O. Pink, and B. Hummel. A Statistical Approach to Map Matching Using Road Network Geometry, Topology and Vehicular Motion Constraints. In the 11th International IEEE Conference on Intelligent Transportation Systems(ITS’08), 2008.
[52] M. A. Quddus, W. Y. Ochieng, L. Zhao, and R. B. Noland. A General Map Matching Algorithm for Transport Telematics Applications. GPS Solutions, Volume 7, Issue 3, pp. 157-167, December 2003.
[53] R. Raymond, T. Morimura, T. Osogami and N. Hirosue. Map Matching with Hidden Markov Model on Sampled Road Network. In Proceedings of 21st International Conference on Pattern Recognition (ICPR'12), 2012.
[54] S. Scellato, C. Mascolo, M. Musolesi, and V. Latora. Distance Matters: Geo-social Metrics for Online Social Networks. In Proceedings of the 3rd Wonference on Online social networks (WOSN’10), 2010.
[55] J. W. Sennott, and R. E. Taylor. Navigation System and Method. U.S. Patent No. 4,445, 118, April 1984.
[56] J. Shang, Y. Zheng, W. Tong, and E. Chang. Inferring Gas Consumption and Pollution Emission of Vehicles throughout a City. In the Proceeding of the 20th SIGKDD conference on Knowledge Discovery and Data Mining (KDD’14), 2014.
[57] S. Shekhar, J. Kang, and V. Gandhi. Spatial Data Mining. Springer US, pp. 2695-2698, 2009.
[58] Y. Tang, A. D. Zhu, and X. Xiao. An Efficient Algorithm for Mapping Vehicle Trajectories onto Road Networks. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[59] F. Torre, D. Pitchford, P. Brown, and L. Terveen. Matching GPS Traces to (Possibly) Incomplete Map Data: Bridging Map Building and Map Matching. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[60] D. Wang, Z. Wang, X. Li, and Z. Xiao. A Map Matching Algorithm to Eliminate Miscalculation Based on Low-Sample-Rate Data. In Proceedings of 2014 International Conference on Computer Science and Service System(CSSS’14), June 2014.
[61] H. Wei, Y. Wang, G. Forman, Y. Zhu, and H. Guan. Fast Viterbi Map Matching with Tunable Weight Functions. In Proceedings of 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems(GIS’12), 2012.
[62] C. Wenk, R. Salas and D. Pfoser. Addressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms. In Proceedings of the 18th International Conference on Scientific and Statistical Database Management (SSDBM’06), 2006.
[63] C. E. White, D. Bernstein,and A. L. Kornhauser. Some Map Matching Algorithms for Personal Navigation Assistants. Transportation Research Part C, Volume 8, pp. 91-108, 2000.
[64] X. Yan, H. Zhang, and C. Wu. Research and Development of Intelligent Transportation Systems. In Proceedings of 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science (DCABES’12), October 2012.
[65] H. Yin, and O. Wolfson. A Weight-Based Map Matching Method in Moving Objects Databases. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM’04), 2004.
[66] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie and Y. Huang. T-Drive: Driving Directions Based on Taxi Trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS’10), 2010.
[67] J. Yuan, Y. Zheng, C. Zhang, X. Xie, and G. Sun. An Interactive Voting-Based Map Matching Algorithm. In Proceedings of the 2010 Eleventh International Conference on Mobile Data Management (MDM’10), 2010.
[68] Y. Zheng, Y. Liu, J. Yuan, and X. Xie, Urban Computing with Taxicabs. In Proceedings of 13th ACM International Conference on Ubiquitous Computing (UbiComp 2011), Beijing, China, September 2011.