{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:13Z","timestamp":1779174793527,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,9,29]],"date-time":"2017-09-29T00:00:00Z","timestamp":1506643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Nokia Scholarship grant"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>\n            Grids are commonly used as histograms to process spatial data in order to detect frequent patterns, predict destinations, or to infer popular places. However, they have not been previously used for GPS trajectory similarity searches or retrieval in general. Instead, slower and more complicated algorithms based on individual point-pair comparison have been used. We demonstrate how a grid representation can be used to compute four different route measures: novelty, noteworthiness, similarity, and inclusion. The measures may be used in several applications such as identifying taxi fraud, automatically updating GPS navigation software, optimizing traffic, and identifying commuting patterns. We compare our proposed route similarity measure, C-SIM, to eight popular alternatives including Edit Distance on Real sequence (EDR) and Frechet distance. The proposed measure is simple to implement and we give a fast, linear time algorithm for the task. It works well under noise, changes in sampling rate, and point shifting. We demonstrate that by using the grid, a route similarity ranking can be computed in real-time on the Mopsi2014\n            <jats:sup>1<\/jats:sup>\n            route dataset, which consists of over 6,000 routes. This ranking is an extension of the most similar route search and contains an ordered list of all similar routes from the database. The real-time search is due to indexing the cell database and comes at the cost of spending 80% more memory space for the index. The methods are implemented inside the Mopsi\n            <jats:sup>2<\/jats:sup>\n            route module.\n          <\/jats:p>","DOI":"10.1145\/3125634","type":"journal-article","created":{"date-parts":[[2017,9,29]],"date-time":"2017-09-29T12:44:38Z","timestamp":1506689078000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Grid-Based Method for GPS Route Analysis for Retrieval"],"prefix":"10.1145","volume":"3","author":[{"given":"Radu","family":"Mariescu-Istodor","sequence":"first","affiliation":[{"name":"University of Eastern Finland, Joensuu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasi","family":"Fr\u00e4nti","sequence":"additional","affiliation":[{"name":"University of Eastern Finland, Joensuu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57301-1_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2012.36"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653776"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICECC.2011.6066483"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50070-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2012.2186146"},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen . 2009. Introduction to Algorithms . MIT Press . Thomas H. Cormen. 2009. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505821.2505835"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15300-6_5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-006-0007-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367927"},{"key":"e_1_2_1_14_1","volume-title":"Tables of Integrals, Series, and Products","author":"Gradshteyn Izrail Solomonovich","unstructured":"Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik . 2000. Tables of Integrals, Series, and Products , 6 th ed. Academic Press , San Diego, CA , 1114--1125. Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik. 2000. Tables of Integrals, Series, and Products, 6th ed. Academic Press, San Diego, CA, 1114--1125.","edition":"6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0185-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_17_1","series-title":"Vol. 2","volume-title":"Time Series Analysis","author":"Hamilton James D.","unstructured":"James D. Hamilton . 1994. Time Series Analysis ( Vol. 2 ) . Princeton University Press , Princeton, NJ . James D. Hamilton. 1994. Time Series Analysis (Vol. 2). Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11853565_15"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th International Conference on Web Information Systems and Technologies (WEBIST\u201914)","author":"Mariescu-Istodor Radu","year":"2014","unstructured":"Radu Mariescu-Istodor , Andrei Tabarcea , Rahim Saeidim , and Pasi Fr\u00e4nti . 2014 . Low complexity spatial similarity measure of GPS trajectories . In Proceedings of the 10th International Conference on Web Information Systems and Technologies (WEBIST\u201914) . 62--69. Radu Mariescu-Istodor, Andrei Tabarcea, Rahim Saeidim, and Pasi Fr\u00e4nti. 2014. Low complexity spatial similarity measure of GPS trajectories. In Proceedings of the 10th International Conference on Web Information Systems and Technologies (WEBIST\u201914). 62--69."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2013.05.002"},{"key":"e_1_2_1_21_1","volume-title":"-B. Wets","author":"Rockafellar Tyrrell R.","year":"2009","unstructured":"Tyrrell R. Rockafellar and Roger J . -B. Wets . 2009 . Variational Analysis (Vol. 317). Springer Science 8 Business Media. Tyrrell R. Rockafellar and Roger J.-B. Wets. 2009. Variational Analysis (Vol. 317). Springer Science 8 Business Media."},{"key":"e_1_2_1_22_1","volume-title":"Prcoeedings of the 10th ACM International Conference on Knowledge Discovery and Data Mining Workshop on Mining Temporal and Sequential Data (SIGKDD\u201904)","author":"Salvador Stan","year":"2004","unstructured":"Stan Salvador and Philip Chan . 2004 . FastDTW: Toward accurate dynamic time warping in linear time and space . In Prcoeedings of the 10th ACM International Conference on Knowledge Discovery and Data Mining Workshop on Mining Temporal and Sequential Data (SIGKDD\u201904) (Seattle, WA), 70--80. Stan Salvador and Philip Chan. 2004. FastDTW: Toward accurate dynamic time warping in linear time and space. In Prcoeedings of the 10th ACM International Conference on Knowledge Discovery and Data Mining Workshop on Mining Temporal and Sequential Data (SIGKDD\u201904) (Seattle, WA), 70--80."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247616"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/DEXA.2002.1045983"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994784"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2012.250450"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 9th International Conference on Web Information Systems and Technologies (WEBIST\u201913)","author":"Waga Karol","year":"2013","unstructured":"Karol Waga , Andrei Tabarcea , Radu Mariescu-Istodor , and Pasi Fr\u00e4nti . 2013 . Real time access to multiple GPS tracks . In Proceedings of the 9th International Conference on Web Information Systems and Technologies (WEBIST\u201913) (Aachen, Germany), 293--299. Karol Waga, Andrei Tabarcea, Radu Mariescu-Istodor, and Pasi Fr\u00e4nti. 2013. Real time access to multiple GPS tracks. In Proceedings of the 9th International Conference on Web Information Systems and Technologies (WEBIST\u201913) (Aachen, Germany), 293--299."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2346496.2346513"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 24th Australasian Database Conference (ADC\u201913)","author":"Wang Haozhou","year":"2013","unstructured":"Haozhou Wang , Han Su , Kai Zheng , Shazia Sadiq , and Xiaofang Zhou . 2013 . An effectiveness study on trajectory similarity measures . In Proceedings of the 24th Australasian Database Conference (ADC\u201913) . 13--22. Haozhou Wang, Han Su, Kai Zheng, Shazia Sadiq, and Xiaofang Zhou. 2013. An effectiveness study on trajectory similarity measures. In Proceedings of the 24th Australasian Database Conference (ADC\u201913). 13--22."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339562"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36389-0_5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1867699.1867703"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSKD.2009.504"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2030112.2030127"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772795"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526816"},{"key":"e_1_2_1_37_1","volume-title":"Computing with Spatial Trajectories","author":"Zheng Yu","unstructured":"Yu Zheng and Xiaofang Zhou . 2011. Computing with Spatial Trajectories . Springer Science 8 Business Media. Yu Zheng and Xiaofang Zhou. 2011. Computing with Spatial Trajectories. Springer Science 8 Business Media."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3125634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:06Z","timestamp":1750217406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,29]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3125634"],"URL":"https:\/\/doi.org\/10.1145\/3125634","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,29]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}