{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T09:41:41Z","timestamp":1773567701320,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"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":[[2023,10,31]]},"abstract":"<jats:p>\n            Given a curve\n            <jats:italic>P<\/jats:italic>\n            with points in \u211d\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            in a streaming fashion, and parameters \u025b &gt; 0 and\n            <jats:italic>k<\/jats:italic>\n            , we construct a distance oracle that uses\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\frac{1}{\\varepsilon })^{kd}\\log \\varepsilon ^{-1}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            space, and given a query curve\n            <jats:italic>Q<\/jats:italic>\n            with\n            <jats:italic>k<\/jats:italic>\n            points in \u211d\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            returns in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(kd)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time a 1+\u025b approximation of the discrete Fr\u00e9chet distance between\n            <jats:italic>Q<\/jats:italic>\n            and\n            <jats:italic>P<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension\n            <jats:italic>d<\/jats:italic>\n            , and therefore we generalize some useful tools and algorithms for curves under the discrete Fr\u00e9chet distance to work efficiently in high dimensions.\n          <\/jats:p>","DOI":"10.1145\/3610227","type":"journal-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T12:40:29Z","timestamp":1690202429000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Static and Streaming Data Structures for Fr\u00e9chet Distance Queries"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":false,"given":"Arnold","family":"Filtser","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3978-1428","authenticated-orcid":false,"given":"Omrit","family":"Filtser","sequence":"additional","affiliation":[{"name":"The Open University of Israel, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,25]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9132-4"},{"key":"e_1_3_3_3_2","first-page":"898","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Afshani Peyman","year":"2018","unstructured":"Peyman Afshani and Anne Driemel. 2018. On the complexity of range searching among curves. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 898\u2013917. DOI:10.1137\/1.9781611975031.58"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/130920526"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9846-4"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","unstructured":"Boris Aronov Sariel Har-Peled Christian Knauer Yusu Wang and Carola Wenk. 2006. Fr\u00e9chet distance for curves revisited. In Algorithms\u2014ESA 2006 . Lecture Notes in Computer Science Vol. 4168. Springer 52\u201363. DOI:10.1007\/11841036_8","DOI":"10.1007\/11841036_8"},{"key":"e_1_3_3_7_2","volume-title":"Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201918)","author":"Astefanoaei Maria Sinziana","year":"2018","unstructured":"Maria Sinziana Astefanoaei, Paul Cesaretti, Panagiota Katsikouli, Mayank Goswami, and Rik Sarkar. 2018. Multi-resolution sketches and locality sensitive hashing for fast trajectory processing. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201918). ACM, New York, NY, 279\u2013288. DOI:10.1145\/3274895.3274943"},{"key":"e_1_3_3_8_2","volume-title":"Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917)","author":"Baldus Julian","year":"2017","unstructured":"Julian Baldus and Karl Bringmann. 2017. A fast implementation of near neighbors queries for Fr\u00e9chet distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917). ACM, New York, NY, Article 99, 4 pages. DOI:10.1145\/3139958.3140062"},{"key":"e_1_3_3_9_2","first-page":"630","volume-title":"Proceedings of the 8th Latin American Symposiumon Theoretical Informatics (LATIN\u201908)","author":"Bereg Sergey","year":"2008","unstructured":"Sergey Bereg, Minghui Jiang, Wencheng Wang, Boting Yang, and Binhai Zhu. 2008. Simplifying 3D polygonal chains under the discrete Fr\u00e9chet distance. In Proceedings of the 8th Latin American Symposiumon Theoretical Informatics (LATIN\u201908). 630\u2013641. DOI:10.1007\/978-3-540-78773-0_54"},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1109\/FOCS.2014.76","volume-title":"Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201914)","author":"Bringmann Karl","year":"2014","unstructured":"Karl Bringmann. 2014. Why walking the dog takes time: Fr\u00e9chet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201914). 661\u2013670. DOI:10.1109\/FOCS.2014.76"},{"key":"e_1_3_3_11_2","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201922)","author":"Bringmann Karl","year":"2022","unstructured":"Karl Bringmann, Anne Driemel, Andr\u00e9 Nusser, and Ioannis Psarros. 2022. Tight bounds for approximate near neighbor searching for time series under the Fr\u00e9chet distance. In Proceedings of the Symposium on Discrete Algorithms (SODA\u201922)."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i2a4"},{"key":"e_1_3_3_13_2","volume-title":"Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917)","author":"Buchin Kevin","year":"2017","unstructured":"Kevin Buchin, Yago Diez, Tom van Diggelen, and Wouter Meulemans. 2017. Efficient trajectory queries under the Fr\u00e9chet distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917). ACM, New York, NY, Article 101, 4 pages. DOI:10.1145\/3139958.3140064"},{"key":"e_1_3_3_14_2","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Buchin Kevin","year":"2019","unstructured":"Kevin Buchin, Tim Ophelders, and Bettina Speckmann. 2019. SETH says: Weak Fr\u00e9chet distance is faster, but only if it is continuous and in one dimension. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 2887\u20132901. DOI:10.1137\/1.9781611975482.179"},{"key":"e_1_3_3_15_2","volume-title":"Proceedings of the 36th European Workshop on Computational Geometry (EuroCG\u201920)","author":"Buchin Maike","year":"2020","unstructured":"Maike Buchin, Ivor van der Hoog, Tim Ophelders, Rodrigo I. Silveira, Lena Schlipf, and Frank Staals. 2020. Improved space bounds for Fr\u00e9chet distance queries. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG\u201920)."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.002"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.05.007"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.06.011"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.11.006"},{"key":"e_1_3_3_20_2","first-page":"Article 48, 4 p","volume-title":"Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917)","author":"de Berg Mark","year":"2017","unstructured":"Mark de Berg, Joachim Gudmundsson, and Ali D. Mehrabi. 2017. A dynamic data structure for approximate proximity queries in trajectory data. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917). Article 48, 4 pages. DOI:10.1145\/3139958.3140023"},{"key":"e_1_3_3_21_2","volume-title":"Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG\u201917)","author":"de Berg Mark","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 (CCCG\u201917). 214\u2013219."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/120865112"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","unstructured":"Anne Driemel and Ioannis Psarros. 2021. ANN for time series under the Fr\u00e9chet distance. In Algorithms and Data Structures . Lecture Notes in Computer Science Vol. 12808. Springer 315\u2013328. DOI:10.1007\/978-3-030-83508-8_23","DOI":"10.1007\/978-3-030-83508-8_23"},{"key":"e_1_3_3_25_2","article-title":"Sublinear data structures for short Fr\u00e9chet queries","volume":"1907","author":"Driemel Anne","year":"2019","unstructured":"Anne Driemel, Ioannis Psarros, and Melanie Schmidt. 2019. Sublinear data structures for short Fr\u00e9chet queries. CoRR abs\/1907.04420 (2019). http:\/\/arxiv.org\/abs\/1907.04420","journal-title":"CoRR"},{"key":"e_1_3_3_26_2","first-page":"Article 37, 16","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry","volume":"77","author":"Driemel Anne","year":"2017","unstructured":"Anne Driemel and Francesco Silvestri. 2017. Locality-sensitive hashing of curves. In Proceedings of the 33rd International Symposium on Computational Geometry. Leibniz International Proceedings in Informatics, Vol. 77. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 37, 16 pages. DOI:10.4230\/LIPIcs.SoCG.2017.37"},{"key":"e_1_3_3_27_2","volume-title":"Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917)","author":"D\u00fctsch Fabian","year":"2017","unstructured":"Fabian D\u00fctsch and Jan Vahrenhold. 2017. A filter-and-refinement-algorithm for range queries based on the Fr\u00e9chet distance (GIS Cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS\u201917). ACM, New York, NY, Article 100, 4 pages. DOI:10.1145\/3139958.3140063"},{"key":"e_1_3_3_28_2","volume-title":"Computing Discrete Fr\u00e9chet Distance","author":"Eiter Thomas","year":"1994","unstructured":"Thomas Eiter and Heikki Mannila. 1994. Computing Discrete Fr\u00e9chet Distance. Technical Report. Technische Universitat Wien."},{"key":"e_1_3_3_29_2","first-page":"Article 37, 13","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918)","author":"Emiris Ioannis Z.","year":"2018","unstructured":"Ioannis Z. Emiris and Ioannis Psarros. 2018. Products of Euclidean metrics and applications to proximity questions among curves. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918). Article 37, 13 pages. DOI:10.4230\/LIPIcs.SoCG.2018.37"},{"key":"e_1_3_3_30_2","first-page":"Article 48, 19","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","author":"Filtser Arnold","year":"2020","unstructured":"Arnold Filtser, Omrit Filtser, and Matthew J. Katz. 2020. Approximate nearest neighbor for curves\u2014Simple, efficient, and deterministic. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920). Article 48, 19 pages. DOI:10.4230\/LIPIcs.ICALP.2020.48"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.10.002"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195919500043"},{"key":"e_1_3_3_33_2","volume-title":"Proceedings of the 10th Australasian Conference on Mathematics and Computers in Sport","author":"Gudmundsson Joachim","year":"2010","unstructured":"Joachim Gudmundsson and Thomas Wolle. 2010. Towards automated football analysis: Algorithms and data structures. In Proceedings of the 10th Australasian Conference on Mathematics and Computers in Sport."},{"key":"e_1_3_3_34_2","volume-title":"Geometric Approximation Algorithms","author":"Har-Peled Sariel","year":"2011","unstructured":"Sariel Har-Peled. 2011. Geometric Approximation Algorithms. American Mathematical Society, Washington, DC."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_3_36_2","first-page":"102","volume-title":"Proceedings of the 8th Symposium on Computational Geometry","author":"Indyk Piotr","year":"2002","unstructured":"Piotr Indyk. 2002. Approximate nearest neighbor algorithms for Fr\u00e9chet distance via product metrics. In Proceedings of the 8th Symposium on Computational Geometry. ACM, New York, NY, 102\u2013106. DOI:10.1145\/513400.513414"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003278"},{"key":"e_1_3_3_38_2","article-title":"Can\u2019t see the forest for the trees: Navigating metric spaces by bounded hop-diameter spanners","volume":"2107","author":"Kahalon Omri","year":"2021","unstructured":"Omri Kahalon, Hung Le, Lazar Milenkovic, and Shay Solomon. 2021. Can\u2019t see the forest for the trees: Navigating metric spaces by bounded hop-diameter spanners. CoRR abs\/2107.14221 (2021). https:\/\/arxiv.org\/abs\/2107.14221","journal-title":"CoRR"},{"key":"e_1_3_3_39_2","first-page":"45","volume-title":"Proceedings of the 5th Workshop on Algorithm Engineering and Experiments","author":"Kumar Piyush","year":"2003","unstructured":"Piyush Kumar, Joseph S. B. Mitchell, and E. Alper Yildirim. 2003. Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions. In Proceedings of the 5th Workshop on Algorithm Engineering and Experiments. 45\u201355. DOI:10.1145\/996546.996548"},{"key":"e_1_3_3_40_2","doi-asserted-by":"crossref","unstructured":"Ariane Mascret Thomas Devogele Iwan Le Berre and Alain H\u00e9naff. 2006. Coastline matching process based on the discrete Fr\u00e9chet distance. In Progress in Spatial Data Handling . Springer 383\u2013400. DOI:10.1007\/3-540-35589-8_25","DOI":"10.1007\/3-540-35589-8_25"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483708"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3231541.3231549"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.17"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9392-2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3610227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:01Z","timestamp":1750182541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3610227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,25]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3610227"],"URL":"https:\/\/doi.org\/10.1145\/3610227","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,25]]},"assertion":[{"value":"2022-02-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}