{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:44:17Z","timestamp":1765547057379,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T00:00:00Z","timestamp":1682985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Australian Research Council Discovery Projects funding scheme","award":["DP180102870"],"award-info":[{"award-number":["DP180102870"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>\n            We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fr\u00e9chet distance. Given an\n            <jats:italic>n<\/jats:italic>\n            vertex trajectory\n            <jats:italic>P<\/jats:italic>\n            and an\n            <jats:italic>m<\/jats:italic>\n            vertex query trajectory\n            <jats:italic>Q<\/jats:italic>\n            , we seek to\n            <jats:italic>report<\/jats:italic>\n            a vertex-aligned sub-trajectory\n            <jats:italic>P<\/jats:italic>\n            \u2032 of\n            <jats:italic>P<\/jats:italic>\n            that is closest to\n            <jats:italic>Q<\/jats:italic>\n            , i.e.,\n            <jats:italic>P\u2032<\/jats:italic>\n            must start and end on contiguous vertices of\n            <jats:italic>P<\/jats:italic>\n            . Since in real data\n            <jats:italic>P<\/jats:italic>\n            typically contains a\n            <jats:italic>very large<\/jats:italic>\n            number of vertices, we focus on answering queries, without restrictions on\n            <jats:italic>P<\/jats:italic>\n            or\n            <jats:italic>Q<\/jats:italic>\n            , using only precomputed structures of\n            <jats:italic>\ud835\udcaa(n)<\/jats:italic>\n            size.\n          <\/jats:p>\n          <jats:p>\n            We use three baseline algorithms from straightforward extensions of known work; however, they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree (HST) data structure and an adaptive clustering-based query algorithm that efficiently explores relevant parts of\n            <jats:italic>P<\/jats:italic>\n            . The core of our query methods is a novel greedy-backtracking algorithm that solves the Fr\u00e9chet decision problem using\n            <jats:italic>\ud835\udcaa(n+m)<\/jats:italic>\n            space and\n            <jats:italic>\ud835\udcaaO(nm)<\/jats:italic>\n            time in the worst case.\n          <\/jats:p>\n          <jats:p>Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches.<\/jats:p>","DOI":"10.1145\/3587426","type":"journal-article","created":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T10:34:59Z","timestamp":1683023699000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On Practical Nearest Sub-Trajectory Queries under the Fr\u00e9chet Distance"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6778-7990","authenticated-orcid":false,"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Sydney, Darlington, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5286-2604","authenticated-orcid":false,"given":"John","family":"Pfeifer","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Darlington, NSW, 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":"School of Computer Science, University of Sydney, Darlington, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,2]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140062"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.25"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2019.17"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195911003652"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9878-7"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140064"},{"key":"e_1_3_2_10_2","first-page":"426","volume-title":"Proceedings of the VLDB","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the VLDB. 426\u2013435. Retrieved from http:\/\/www.vldb.org\/conf\/1997\/P426.PDF."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.11.006"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140023"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/120865112"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.37"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140063"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1242\/jeb.140889"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460121"},{"key":"e_1_3_2_19_2","article-title":"Approximate subtrajectory range counting queries","author":"Gudmundsson Joachim","year":"2020","unstructured":"Joachim Gudmundsson and Natalie Tridgell. 2020. Approximate subtrajectory range counting queries. Unpublished (2020).","journal-title":"Unpublished"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_3_2_22_2","unstructured":"STATS. 2015. STATS LLC - Data Science. Retrieved October 2021 from http:\/\/www.stats.com\/data-science\/."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3587426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3587426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:16Z","timestamp":1750182556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3587426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,2]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3587426"],"URL":"https:\/\/doi.org\/10.1145\/3587426","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2023,5,2]]},"assertion":[{"value":"2021-10-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}