{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:51:03Z","timestamp":1776351063543,"version":"3.51.2"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T00:00:00Z","timestamp":1598832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>We develop GeoMatch as a novel, scalable, and efficient big-data pipeline for large-scale map matching on Apache Spark. GeoMatch improves existing spatial big-data solutions by utilizing a novel spatial partitioning scheme inspired by Hilbert space-filling curves. Thanks to its partitioning scheme, GeoMatch can effectively balance operations across different processing units and achieve significant performance gains. GeoMatch also incorporates a dynamically adjustable error-correction technique that provides robustness against positioning errors. We demonstrate the effectiveness of GeoMatch through rigorous and extensive empirical benchmarks that consider large-scale urban spatial datasets ranging from 166,253 to 3.78B location measurements. We separately assess execution performance and accuracy of map matching and develop a benchmark framework for evaluating large-scale map matching. Results of our evaluation show up to 27.25-fold performance improvements compared to previous works while achieving better processing accuracy than current solutions. We also showcase the practical potential of GeoMatch with two urban management applications. GeoMatch and our benchmark framework are open-source.<\/jats:p>","DOI":"10.1145\/3402904","type":"journal-article","created":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T06:52:46Z","timestamp":1600066366000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["GeoMatch"],"prefix":"10.1145","volume":"1","author":[{"given":"Ayman","family":"Zeidan","sequence":"first","affiliation":[{"name":"Department of Computer Science, CUNY Graduate Center, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eemil","family":"Lagerspetz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Zhao","sequence":"additional","affiliation":[{"name":"Robinson College of Business, Georgia State University, Atlanta Georgia, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Nurmi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasu","family":"Tarkoma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huy T.","family":"Vo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, CUNY City College, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Mark Abkowitz et al. 1978. Transit Service Reliability. Technical Report. Cambridge MA."},{"key":"e_1_2_1_2_1","volume-title":"Predicting Unmet Trip Demand. Technical Report. In 2016 IEEE International Conference on Big Data (Big Data). 833--842","author":"Ahmed Anita","year":"2017","unstructured":"Anita Ahmed, Alexey Kalinin, Pooneh Famili, Xin Tang, Ziman Zhou, Kaan Ozbay, and Huy Vo. 2017. Predicting Unmet Trip Demand. Technical Report. In 2016 IEEE International Conference on Big Data (Big Data). 833--842."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536227"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE 19th International Conference on Intelligent Transportation Systems (ITSC\u201916)","author":"Almeida A. M. R.","unstructured":"A. M. R. Almeida, M. I. V. Lima, J. A. F. Macedo, and J. C. Machado. 2016. DMM: A distributed map-matching algorithm using the MapReduce paradigm. In Proceedings of the IEEE 19th International Conference on Intelligent Transportation Systems (ITSC\u201916). 1706--1711."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996916"},{"key":"e_1_2_1_6_1","volume-title":"An Improved Procedure for Generation of Half-tone Computer Graphics Presentations. Coordinated Science Laboratory Report no. R-432","author":"Bouknight W. J.","year":"1969","unstructured":"W. J. Bouknight. 1969. An Improved Procedure for Generation of Half-tone Computer Graphics Presentations. Coordinated Science Laboratory Report no. R-432 (1969)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.41.0025"},{"key":"e_1_2_1_8_1","unstructured":"Hongting Chen Francis Ko Shay Lehmann Nurvita Monarizqa Ian Wright Kaan Ozbay and Huy Vo. 2017. Performance Analysis and Tracking for NYC\u2019s Transit System. Technical Report. In Center for Urban Science and Progress (CUSP) New York University."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the SIGMOD PhD Symposium (SIGMOD\u201914 PhD Symposium). ACM","author":"Eldawy Ahmed","year":"2014","unstructured":"Ahmed Eldawy. 2014. SpatialHadoop: Towards flexible and scalable spatial processing using MapReduce. In Proceedings of the SIGMOD PhD Symposium (SIGMOD\u201914 PhD Symposium). ACM, New York, NY, 46--50."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000054"},{"key":"e_1_2_1_11_1","unstructured":"Stefan Hagedorn Philipp G\u00f6tze and Kai-Uwe Sattler. 2017. The STARK framework for spatio-temporal data analytics on Spark. In Datenbanksysteme f\u00fcr Business Technologie und Web (BTW\u201917). 123--142."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-013-3158-3"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201912)","author":"Huang Yan","unstructured":"Yan Huang and Jason W. Powell. 2012. Detecting regions of disequilibrium in taxi services under uncertainty. In Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201912). ACM, New York, NY, 139--148."},{"key":"e_1_2_1_14_1","unstructured":"Environmental Systems Research Institute. 2018. GIS Tools for Hadoop by Esri. Retrieved from http:\/\/esri.github.io\/gis-tools-for-hadoop\/."},{"key":"e_1_2_1_15_1","volume-title":"IDC Forecasts Revenues for Big Data and Business Analytics Solutions Will Reach $189.1 Billion This Year with Double-Digit Annual Growth through","author":"International Data Corporation (IDC). 2019.","year":"2022","unstructured":"International Data Corporation (IDC). 2019. IDC Forecasts Revenues for Big Data and Business Analytics Solutions Will Reach $189.1 Billion This Year with Double-Digit Annual Growth through 2022. Retrieved from https:\/\/www.idc.com\/getdoc.jsp?containerId&equals;prUS44998419."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994)","author":"Kamel Ibrahim","year":"1994","unstructured":"Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An improved R-tree using fractals. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994). Morgan Kaufmann Publishers Inc., San Francisco, CA, 500--509."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 13th International Conference on Data Engineering. IEEE, 497--506","author":"Leutenegger Scott T.","year":"1997","unstructured":"Scott T. Leutenegger, Mario A. Lopez, and Jeffrey Edgington. 1997. STR: A simple and efficient algorithm for R-tree packing. In Proceedings of the 13th International Conference on Data Engineering. IEEE, 497--506."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom","author":"Li Bin","year":"2011","unstructured":"Bin Li, Daqing Zhang, Lin Sun, Chao Chen, Shijian Li, Guande Qi, and Qiang Yang. 2011. Hunting or waiting? Discovering passenger-finding strategies from a large-scale real-world taxi dataset. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom 2011). IEEE, Los Alamitos, CA, 63--68."},{"key":"e_1_2_1_19_1","unstructured":"LocationTech. [n.d.]. LocationTech JTS Topology Suite. Retrieved from https:\/\/projects.eclipse.org\/projects\/locationtech.jts."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653820"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2013.2262376"},{"key":"e_1_2_1_22_1","unstructured":"New York City Taxi and Limousine Commission. 2020. TLC Mentors Students Using Big Data. Retrieved from https:\/\/medium.com\/@NYCTLC\/students-use-tlc-data-to-study-unmet-taxi-demand-and-find-ideal-spots-for-taxi-relief-stands-644e40ebe11a."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236213"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-018-7254-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623668"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE 34th International Conference on Data Engineering (ICDE\u201918)","author":"Ruan S.","unstructured":"S. Ruan, R. Li, J. Bao, T. He, and Y. Zheng. 2018. CloudTP: A cloud-based flexible trajectory preprocessing framework. In Proceedings of the IEEE 34th International Conference on Data Engineering (ICDE\u201918). 1601--1604."},{"key":"e_1_2_1_27_1","unstructured":"P. Shimonti. 2015. What Is Geospatial Industry\u2019s Value and Impact in World Economy? Retrieved from https:\/\/www.geospatialworld.net\/blogs\/geospatial-industrys-value-world-economy\/."},{"key":"e_1_2_1_28_1","volume-title":"Magellan: Geospatial Analytics Using Spark.","author":"Sriharsha Ram","year":"2018","unstructured":"Ram Sriharsha. 2018. Magellan: Geospatial Analytics Using Spark. Retrieved from https:\/\/github.com\/harsha2010\/magellan."},{"key":"e_1_2_1_29_1","first-page":"13","article-title":"LocationSpark: A distributed in-memory data management system for big spatial data","volume":"9","author":"Tang Mingjie","year":"2016","unstructured":"Mingjie Tang, Yongyang Yu, Qutaibah M. Malluhi, Mourad Ouzzani, and Walid G. Aref. 2016. LocationSpark: A distributed in-memory data management system for big spatial data. VLDB Endow. 9, 13 (Sept. 2016), 1565--1568.","journal-title":"VLDB Endow."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3141\/2216-04"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201914)","author":"Vo Hoang","year":"2014","unstructured":"Hoang Vo, Ablimit Aji, and Fusheng Wang. 2014. SATO: A spatial data partitioning framework for scalable query processing. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201914). ACM, New York, NY, 545--548."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference on Management of Data. ACM","author":"Xie Dong","year":"2016","unstructured":"Dong Xie, Feifei Li, Bin Yao, Gefei Li, Liang Zhou, and Minyi Guo. 2016. Simba: Efficient in-memory spatial analytics. In Proceedings of the International Conference on Management of Data. ACM, New York, NY, 1071--1085."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 31st IEEE International Conference on Data Engineering Workshops (ICDEW\u201915)","author":"You Simin","year":"2015","unstructured":"Simin You, Jianting Zhang, and Le Gruenwald. 2015. Large-scale spatial join query processing in cloud. In Proceedings of the 31st IEEE International Conference on Data Engineering Workshops (ICDEW\u201915). IEEE, 34--41."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201915)","author":"Yu Jia","year":"2015","unstructured":"Jia Yu, Jinxuan Wu, and Mohamed Sarwat. 2015. GeoSpark: A cluster computing framework for processing large-scale spatial data. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201915). ACM, New York, NY."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS\u201910)","author":"Yuan Jing","year":"2010","unstructured":"Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. 2010. T-drive: Driving directions based on taxi trajectories. In Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS\u201910). ACM, New York, NY, 99--108."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 11th International Conference on Mobile Data Management. IEEE Computer Society, 43--52","author":"Yuan Jing","year":"2010","unstructured":"Jing Yuan, Yu Zheng, Chengyang Zhang, Xing Xie, and Guang-Zhong Sun. 2010. An interactive-voting based map matching algorithm. In Proceedings of the 11th International Conference on Mobile Data Management. IEEE Computer Society, 43--52."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IEEE International Conference on Big Data (BigData\u201918)","author":"Zeidan Ayman","unstructured":"Ayman Zeidan, Eemil Lagerspetz, Kai Zhao, Petteri Nurmi, Sasu Tarkoma, and Huy T. Vo. 2018. GeoMatch: Efficient large-scale map matching on Apache Spark. In Proceedings of the IEEE International Conference on Big Data (BigData\u201918). IEEE, 384--391."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2030112.2030127"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2030112.2030126"}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3402904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3402904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:57:22Z","timestamp":1776347842000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3402904"}},"subtitle":["Efficient Large-scale Map Matching on Apache Spark"],"short-title":[],"issued":{"date-parts":[[2020,8,31]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3402904"],"URL":"https:\/\/doi.org\/10.1145\/3402904","relation":{},"ISSN":["2691-1922"],"issn-type":[{"value":"2691-1922","type":"print"}],"subject":[],"published":{"date-parts":[[2020,8,31]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}