{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:50:43Z","timestamp":1762876243672,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T00:00:00Z","timestamp":1610668800000},"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 Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>The amount of GPS data that can be collected is increasing tremendously, thanks to the increased popularity of Global Position System (GPS) devices (e.g., smartphones). This article aims to develop novel methods of converting crowd-sourced GPS traces into road topology maps. We explore map inference using a three-stage approach, which incorporates a novel Multi-source Variable Rate (MSVR) signal reconstruction mechanism. Unlike conventional map inference methods based on map graph theory, our approach, to the best of our knowledge, is the first use of estimation theory for map inference. In particular, our approach addresses the unique challenges of vehicular GPS data. This data is plentiful but suffers from noise in location and variable coverage of regions. This makes it difficult to differentiate between noise and sparsely covered regions when increasing coverage and reducing noise. Due to the asynchronous, variable sampling rate, and often under-sampled nature of the data, our MSVR approach can better handle inherent GPS errors, reconstruct road shapes more accurately, and better deal with variable GPS data density in empirical environments.<\/jats:p>\n          <jats:p>We evaluated our method for map inference by comparing to Open Street Map maps as ground truth. We use the F-Measure, Precision, and Recall metrics to evaluate our method on Tsinghua University\u2019s Beijing Taxi Dataset and Shanghai Jiao Tong University\u2019s SUVnet Dataset. On these datasets, we obtained a mean&lt;?brk?&gt; F-Measure, Precision, and Recall of 0.7212, 0.9165, and 0.6021, respectively, outperforming a well-known method based on Kernel Density Estimation in terms of these evaluation metrics.<\/jats:p>","DOI":"10.1145\/3431785","type":"journal-article","created":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T17:04:53Z","timestamp":1610730293000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Map Inference Approach Using Signal Processing from Crowd-sourced GPS Data"],"prefix":"10.1145","volume":"7","author":[{"given":"Eric","family":"He","sequence":"first","affiliation":[{"name":"PNC, Pittsburgh, Pennsylvania"}]},{"given":"Fan","family":"Bai","sequence":"additional","affiliation":[{"name":"General Motors, Warren, Michigan"}]},{"given":"Curtis","family":"Hay","sequence":"additional","affiliation":[{"name":"General Motors, Warren, Michigan"}]},{"given":"Jinzhu","family":"Chen","sequence":"additional","affiliation":[{"name":"General Motors, Warren, Michigan"}]},{"given":"Vijayakumar","family":"Bhagavatula","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University - Africa, Kigali, Rwanda"}]}],"member":"320","published-online":{"date-parts":[[2021,1,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912600072"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2010.2069097"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0222-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0222-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_7"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Minimization of functions having Lipschitz continuous first partial derivatives.Pacific J","volume":"16","author":"Armijo Larry","year":"1966","journal-title":"Math."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3141\/2291-08"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424333"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.297"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.2161-4296.1990.tb01562.x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653776"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ETTandGRS.2008.70"},{"key":"e_1_2_1_13_1","unstructured":"Steve Coast. 2010. Microsoft Imagery details. Retrieved from https:\/\/blog.openstreetmap.org\/2010\/11\/30\/microsoft-imagery-details\/.  Steve Coast. 2010. Microsoft Imagery details. Retrieved from https:\/\/blog.openstreetmap.org\/2010\/11\/30\/microsoft-imagery-details\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.2161-4296.2011.tb01789.x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.2161-4296.1993.tb02308.x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2006.83"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140031"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/361237.361242"},{"volume-title":"Silveira","year":"2020","author":"Duran David","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/865449.865460"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887961.1887966"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524435"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986553"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGARSS.2007.4422884"},{"volume-title":"Proceedings of the 23rd International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS\u201910)","year":"2010","author":"Heng Liang","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the 2011 International Technical Meeting of the Institute of Navigation (ION ITM\u201911)","year":"2011","author":"Heng Liang","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(88)80033-1"},{"volume-title":"Understanding GPS: Principles and Applications","author":"Kaplan Elliott","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424334"},{"key":"e_1_2_1_32_1","unstructured":"Gur Kimchi. 2010. Bing engages open maps community. Retrieved from https:\/\/blogs.bing.com\/maps\/2010\/11\/23\/bing-engages-open-maps-community.  Gur Kimchi. 2010. Bing engages open maps community. Retrieved from https:\/\/blogs.bing.com\/maps\/2010\/11\/23\/bing-engages-open-maps-community."},{"volume-title":"Langley","year":"1990","author":"Kleusberg Alfred","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339637"},{"key":"e_1_2_1_35_1","unstructured":"Martin Loetzsch. [n.d.]. Google Earth Map Overlays. Retrieved from http:\/\/ge-map-overlays.appspot.com\/.  Martin Loetzsch. [n.d.]. Google Earth Map Overlays. Retrieved from http:\/\/ge-map-overlays.appspot.com\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.393"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1590964.1591648"},{"key":"e_1_2_1_38_1","unstructured":"NovAtel. 2016. Receivers Brochure. Retrieved from https:\/\/www.novatel.com\/assets\/Documents\/Papers\/ReceiversBrochure.pdf.  NovAtel. 2016. Receivers Brochure. Retrieved from https:\/\/www.novatel.com\/assets\/Documents\/Papers\/ReceiversBrochure.pdf."},{"key":"e_1_2_1_39_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump. Retrieved from https:\/\/planet.osm.org; https:\/\/www.openstreetmap.org.  OpenStreetMap contributors. 2017. Planet dump. Retrieved from https:\/\/planet.osm.org; https:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_40_1","first-page":"3","article-title":"Differential gps","volume":"2","author":"Parkinson Bradford W.","year":"1996","journal-title":"Global Position. Syst.: Theory Appl."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/PLANS.1994.303322"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2012.2220151"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:DAMI.0000026904.74892.89"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10291-008-0089-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424336"},{"key":"e_1_2_1_46_1","unstructured":"Shanghai Jiaotong University Wireless and Sensor Networks Lab. [n.d.]. SUVnet-trace data. Retrieved from http:\/\/wirelesslab.sjtu.edu.cn.  Shanghai Jiaotong University Wireless and Sensor Networks Lab. [n.d.]. SUVnet-trace data. Retrieved from http:\/\/wirelesslab.sjtu.edu.cn."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2009.5309871"},{"volume-title":"Global Positioning System: Theory and Applications","author":"Spilker James J.","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","unstructured":"Tsinghua University. [n.d.]. Beijing Taxis Dataset. Retrieved from http:\/\/sensor.ee.tsinghua.edu.cn\/datasets.html.  Tsinghua University. [n.d.]. Beijing Taxis Dataset. Retrieved from http:\/\/sensor.ee.tsinghua.edu.cn\/datasets.html."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1137750"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.884094"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.2161-4296.2010.tb01770.x"},{"volume-title":"Young Jin Lee, Tajul Musa, Chris Rizos, et\u00a0al.","year":"2005","author":"Wang Jinling","key":"e_1_2_1_53_1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820833"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462456.2464441"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/19.39042"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the Australasian Conference on Robotics and Automation","volume":"6","author":"Worrall Stewart","year":"2007"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3431785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:46Z","timestamp":1750195486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,15]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3431785"],"URL":"https:\/\/doi.org\/10.1145\/3431785","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2021,1,15]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}