{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T13:02:16Z","timestamp":1777986136303,"version":"3.51.4"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"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. Algorithms"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road network that is the most spatially similar to the trajectory, where spatial similarity is measured using the Fr\u00e9chet distance. A shortcoming of existing map matching algorithms under the Fr\u00e9chet distance is that every time a trajectory is matched, the entire road network needs to be reprocessed from scratch. An open problem is whether one can preprocess the road network into a data structure, so that map matching queries can be answered in sublinear time.<\/jats:p>\n          <jats:p>\n            In this article, we investigate map matching queries under the Fr\u00e9chet distance. We provide a negative result for geometric planar graphs. We show that, unless SETH fails, there is no data structure that can be constructed in polynomial time that answers map matching queries in\n            <jats:italic>O((pq)<\/jats:italic>\n            <jats:sup>1-\u03b4<\/jats:sup>\n            ) query time for any \u03b4 &gt; 0, where\u00a0\n            <jats:italic>p<\/jats:italic>\n            and\u00a0\n            <jats:italic>q<\/jats:italic>\n            are the complexities of the geometric planar graph and the query trajectory, respectively. We provide a positive result for realistic input graphs, which we regard as the main result of this article. We show that for\n            <jats:italic>c<\/jats:italic>\n            -packed graphs, one can construct a data structure of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(cp)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            size that can answer (1+\u03b5)-approximate map matching queries in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(c^4 q \\log ^4 p)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time, where\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(\\cdot)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            hides lower-order factors and dependence on\u00a0\u03b5.\n          <\/jats:p>","DOI":"10.1145\/3643683","type":"journal-article","created":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T12:15:30Z","timestamp":1706616930000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Map Matching Queries on Realistic Input Graphs Under the Fr\u00e9chet Distance"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6778-7990","authenticated-orcid":false,"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[{"name":"University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6901-3035","authenticated-orcid":false,"given":"Martin P.","family":"Seybold","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3803-3804","authenticated-orcid":false,"given":"Sampson","family":"Wong","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9137-7"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811001"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.58"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424426"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00085-3"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140062"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083691"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.25"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195917600056"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9878-7"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140064"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.179"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2022.29"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3368617"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39469-1_10"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972917.8"},{"key":"e_1_3_1_20_2","article-title":"A faster algorithm for matching planar maps under the weak Fr\u00e9chet distance","author":"Chen Daniel","year":"2008","unstructured":"Daniel Chen, Leonidas J. Guibas, Qixing Huang, and Jian Sun. 2008. A faster algorithm for matching planar maps under the weak Fr\u00e9chet distance. Unpublished, December (2008).","journal-title":"Unpublished, December"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.ATMOS.2021.10"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7537"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140023"},{"key":"e_1_3_1_24_2","first-page":"214","volume-title":"Proceedings of the 29th Canadian Conference on Computational Geometry","author":"Berg Mark de","year":"2017","unstructured":"Mark de Berg, Ali D. Mehrabi, and Tim Ophelders. 2017. Data structures for fr\u00e9chet queries in trajectory data. In Proceedings of the 29th Canadian Conference on Computational Geometry. 214\u2013219."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/120865112"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-83508-8_23"},{"key":"e_1_3_1_29_2","unstructured":"Anne Driemel Ioannis Psarros and Melanie Schmidt. 2019. Sublinear data structures for short Fr\u00e9chet queries. arXiv:1907.04420. Retrieved from http:\/\/arxiv.org\/abs\/1907.04420"},{"key":"e_1_3_1_30_2","first-page":"36:1\u201336:18","volume-title":"Proceedings of the 38th Symposium on Computational Geometry.","volume":"224","author":"Driemel Anne","year":"2022","unstructured":"Anne Driemel, Ivor van der Hoog, and Eva Rotenberg. 2022. On the discrete Fr\u00e9chet distance in a graph. In Proceedings of the 38th Symposium on Computational Geometry. Vol. 224, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 36:1\u201336:18."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1135"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140063"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.71"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.48"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.10.002"},{"key":"e_1_3_1_36_2","first-page":"218","volume-title":"Proceedings of the 31st Canadian Conference on Computational Geometry","author":"Fu Bin","year":"2019","unstructured":"Bin Fu, Robert T. Schweller, and Tim Wylie. 2019. Discrete planar map matching. In Proceedings of the 31st Canadian Conference on Computational Geometry. 218\u2013224."},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460121"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2020.9"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.02.003"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00865-0"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2014.07.009"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513414"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/MITS.2018.2806630"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2007.05.002"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00154-8"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974973.91"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2835185.2835186"},{"key":"e_1_3_1_51_2","unstructured":"Ivor van der Hoog Eva Rotenberg and Sampson Wong. 2022. Data structures for Approximate Discrete Fr\u00e9chet distance. arXiv:2212.07124. Retrieved from https:\/\/arxiv.org\/abs\/2212.07124"},{"key":"e_1_3_1_52_2","first-page":"19","article-title":"Map matching by Fr\u00e9chet distance and global weight optimization","author":"Wei Hong","year":"2013","unstructured":"Hong Wei, Yin Wang, George Forman, and Yanmin Zhu. 2013. Map matching by Fr\u00e9chet distance and global weight optimization. Technical Paper, Departement of Computer Science and Engineering (2013), 19.","journal-title":"Technical Paper, Departement of Computer Science and Engineering"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525456"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2006.11"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_1_56_2","unstructured":"Tim Wylie and Binhai Zhu. 2014. Intermittent map matching with the discrete fr\u00e9chet distance. arXiv:1409.2456. Retrieved from https:\/\/arxiv.org\/abs\/1409.2456"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1629-6"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643683","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3643683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:33Z","timestamp":1750291533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3643683"],"URL":"https:\/\/doi.org\/10.1145\/3643683","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"2022-12-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}