{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:43Z","timestamp":1750220443039,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003447","name":"State Scholarships Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003447","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union's H2020 research and innovation programme","award":["734242"],"award-info":[{"award-number":["734242"]}]},{"name":"State Scholarships Foundation of Greece"},{"name":"Greece and the European Union"},{"name":"LAMBDA"},{"name":"Operational Programme \u201cHuman Resources Development, Education and Lifelong Learning\u201d"},{"name":"\u201cStrengthening Human Resources Research Potential via Doctorate Research\u201d","award":["MIS-5000432"],"award-info":[{"award-number":["MIS-5000432"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Approximate Nearest Neighbor (ANN) search is a fundamental computational problem that has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets, whereas complex shapes have not been sufficiently addressed. Here, we focus on distance functions between discretized curves in Euclidean space: They appear in a wide range of applications, from road segments and molecular backbones to time-series in general dimension. For \u2113\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sub>\n            -products of Euclidean metrics, for any constant\n            <jats:italic>p<\/jats:italic>\n            , we propose simple and efficient data structures for ANN based on randomized projections: These data structures are of independent interest. Furthermore, they serve to solve proximity questions under a notion of distance between discretized curves, which generalizes both discrete Fr\u00e9chet and Dynamic Time Warping distance functions. These are two very popular and practical approaches to comparing such curves. We offer, for both approaches, the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our methods; our algorithm is especially efficient when the length of the curves is bounded. Finally, we focus on discrete Fr\u00e9chet distance when the ambient space is high dimensional and derive complexity bounds in terms of doubling dimension as well as an improved approximate near neighbor search.\n          <\/jats:p>","DOI":"10.1145\/3397518","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:46:01Z","timestamp":1592793961000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Products of Euclidean Metrics, Applied to Proximity Problems among Curves"],"prefix":"10.1145","volume":"6","author":[{"given":"Ioannis Z.","family":"Emiris","sequence":"first","affiliation":[{"name":"Department of Informatics 8 Telecommunications, National 8 Kapodistrian University of Athens, and ATHENA Research 8 Innovation Center, Maroussi, Greece"}]},{"given":"Ioannis","family":"Psarros","sequence":"additional","affiliation":[{"name":"Department of Informatics 8 Telecommunications, National 8 Kapodistrian University of Athens, Panepistimiopolis, Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Afshani P.","year":"1975","unstructured":"P. Afshani and A. Driemel . 2018. On the complexity of range searching among curves . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . 898--917. DOI:https:\/\/doi.org\/10.1137\/1.978161 1975 031.58 10.1137\/1.9781611975031.58 P. Afshani and A. Driemel. 2018. On the complexity of range searching among curves. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 898--917. DOI:https:\/\/doi.org\/10.1137\/1.9781611975031.58"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Alman J.","year":"2016","unstructured":"J. Alman , T. M. Chan , and R. R. Williams . 2016. Polynomial representations of threshold functions and algorithmic applications . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201916) . 467--476. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2016 .57 10.1109\/FOCS.2016.57 J. Alman, T. M. Chan, and R. R. Williams. 2016. Polynomial representations of threshold functions and algorithmic applications. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201916). 467--476. DOI:https:\/\/doi.org\/10.1109\/FOCS.2016.57"},{"key":"e_1_2_1_4_1","article-title":"Randomized embeddings with slack and high-dimensional approximate nearest neighbor","volume":"14","author":"Anagnostopoulos E.","year":"2018","unstructured":"E. Anagnostopoulos , I. Z. Emiris , and I. Psarros . 2018 . Randomized embeddings with slack and high-dimensional approximate nearest neighbor . ACM Trans. Algor. 14 , 2 (2018), 18:1--18:21. DOI:https:\/\/doi.org\/10.1145\/3178540 10.1145\/3178540 E. Anagnostopoulos, I. Z. Emiris, and I. Psarros. 2018. Randomized embeddings with slack and high-dimensional approximate nearest neighbor. ACM Trans. Algor. 14, 2 (2018), 18:1--18:21. DOI:https:\/\/doi.org\/10.1145\/3178540","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Andoni A.","year":"2008","unstructured":"A. Andoni , D. Croitoru , and M. Patrascu . 2008. Hardness of nearest neighbor under L-infinity . In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908) . 424--433. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2008 .89 10.1109\/FOCS.2008.89 A. Andoni, D. Croitoru, and M. Patrascu. 2008. Hardness of nearest neighbor under L-infinity. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908). 424--433. DOI:https:\/\/doi.org\/10.1109\/FOCS.2008.89"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906)","author":"Andoni A.","key":"e_1_2_1_7_1","unstructured":"A. Andoni and P. Indyk . 2006. Efficient algorithms for substring near neighbor problem . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906) . 1203--1212. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;1109557.1109690. A. Andoni and P. Indyk. 2006. Efficient algorithms for substring near neighbor problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906). 1203--1212. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;1109557.1109690."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Andoni A.","key":"e_1_2_1_8_1","unstructured":"A. Andoni , T. Laarhoven , I. Razenshteyn , and E. Waingarten . 2017. Optimal hashing-based time-space trade-offs for approximate near neighbors . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . arxiv.org\/abs\/1608.03580. A. Andoni, T. Laarhoven, I. Razenshteyn, and E. Waingarten. 2017. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). arxiv.org\/abs\/1608.03580."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing (STOC\u201911)","author":"Arya S.","year":"1993","unstructured":"S. Arya , G. D. da Fonseca , and D. M. Mount . 2011. Approximate polytope membership queries . In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing (STOC\u201911) . 579--586. DOI:https:\/\/doi.org\/10.1145\/ 1993 636.1993713 10.1145\/1993636.1993713 S. Arya, G. D. da Fonseca, and D. M. Mount. 2011. Approximate polytope membership queries. In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing (STOC\u201911). 579--586. DOI:https:\/\/doi.org\/10.1145\/1993636.1993713"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613677"},{"key":"e_1_2_1_11_1","unstructured":"G. Avarikioti I. Z. Emiris I. Psarros and G. Samaras. 2016. Practical linear-space approximate near neighbors in high dimension. CoRR abs\/1612.07405 (2016).  G. Avarikioti I. Z. Emiris I. Psarros and G. Samaras. 2016. Practical linear-space approximate near neighbors in high dimension. CoRR abs\/1612.07405 (2016)."},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"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 (SIGSPATIAL\u201917)","volume":"99","author":"Baldus J.","year":"2017","unstructured":"J. Baldus and K. 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 (SIGSPATIAL\u201917) . Article 99 , 99: 1 -- 99 :4. J. Baldus and K. 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 (SIGSPATIAL\u201917). Article 99, 99:1--99:4.","journal-title":"Article"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916)","author":"Bartal Y.","year":"2016","unstructured":"Y. Bartal and L.-A. Gottlieb . 2016 . Dimension reduction techniques for &ellp, (1&lt;p&lt;2), with applications . In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916) . 16:1--16:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.16 10.4230\/LIPIcs.SoCG.2016.16 Y. Bartal and L.-A. Gottlieb. 2016. Dimension reduction techniques for &ellp, (1&lt;p&lt;2), with applications. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG\u201916). 16:1--16:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.16"},{"volume-title":"Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906)","author":"Beygelzimer A.","key":"e_1_2_1_14_1","unstructured":"A. Beygelzimer , S. Kakade , and J. Langford . 2006. Cover trees for nearest neighbor . In Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906) . 97--104. DOI:https:\/\/doi.org\/10.1145\/1143844.1143857 10.1145\/1143844.1143857 A. Beygelzimer, S. Kakade, and J. Langford. 2006. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906). 97--104. DOI:https:\/\/doi.org\/10.1145\/1143844.1143857"},{"volume-title":"Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917)","author":"Buchin K.","key":"e_1_2_1_15_1","unstructured":"K. Buchin , Y. Diez , T. van Diggelen , and W. Meulemans . 2017. Efficient trajectory queries under the Fr\u00e9chet distance (GIS Cup) . In Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917) . 101:1--101:4. K. Buchin, Y. Diez, T. van Diggelen, and W. Meulemans. 2017. Efficient trajectory queries under the Fr\u00e9chet distance (GIS Cup). In Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917). 101:1--101:4."},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"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 (SIGSPATIAL\u201917). ACM, New York, NY","volume":"48","author":"de Berg M.","year":"2017","unstructured":"M. de Berg , J. Gudmundsson , and A. 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 (SIGSPATIAL\u201917). ACM, New York, NY , Article 48 , 48: 1 -- 48 :4. DOI:https:\/\/doi.org\/10.1145\/3139958.3140023 10.1145\/3139958.3140023 M. de Berg, J. Gudmundsson, and A. 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 (SIGSPATIAL\u201917). ACM, New York, NY, Article 48, 48:1--48:4. DOI:https:\/\/doi.org\/10.1145\/3139958.3140023","journal-title":"Article"},{"volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry. 37:1--37:16","author":"Driemel A.","key":"e_1_2_1_17_1","unstructured":"A. Driemel and F. Silvestri . 2017. Locality-sensitive hashing of curves . In Proceedings of the 33rd International Symposium on Computational Geometry. 37:1--37:16 . A. Driemel and F. Silvestri. 2017. Locality-sensitive hashing of curves. In Proceedings of the 33rd International Symposium on Computational Geometry. 37:1--37:16."},{"volume-title":"Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917)","author":"D\u00fctsch F.","key":"e_1_2_1_18_1","unstructured":"F. D\u00fctsch and J. Vahrenhold . 2017. A filter-and-refinement- algorithm for range queries based on the Fr\u00e9chet distance (GIS Cup) . In Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917) . 100:1--100:4. F. D\u00fctsch and J. Vahrenhold. 2017. A filter-and-refinement- algorithm for range queries based on the Fr\u00e9chet distance (GIS Cup). In Proceedings of the 25th International Conference on Advances in Geographic Information Systems (SIGSPATIAL\u201917). 100:1--100:4."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918)","author":"Emiris I. Z.","year":"2018","unstructured":"I. Z. Emiris and I. 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) . 37:1--37:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2018 .37 10.4230\/LIPIcs.SoCG.2018.37 I. Z. Emiris and I. 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). 37:1--37:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.37"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"volume-title":"Proceedings of the Symposium on Computational Geometry (SoCG\u201905)","author":"Har-Peled S.","key":"e_1_2_1_21_1","unstructured":"S. Har-Peled and M. Mendel . 2005. Fast construction of nets in low dimensional metrics, and their applications . In Proceedings of the Symposium on Computational Geometry (SoCG\u201905) . 150--158. DOI:https:\/\/doi.org\/10.1145\/1064092.1064117 10.1145\/1064092.1064117 S. Har-Peled and M. Mendel. 2005. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the Symposium on Computational Geometry (SoCG\u201905). 150--158. DOI:https:\/\/doi.org\/10.1145\/1064092.1064117"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE Canadian Conference on Electrical 8 Computer Engineering (No. 02CH37373)","volume":"2","author":"Huang B.","year":"2002","unstructured":"B. Huang and W. Kinsner . 2002. ECG frame classification using dynamic time warping . In Proceedings of the IEEE Canadian Conference on Electrical 8 Computer Engineering (No. 02CH37373) , Vol. 2 . 1105--1110. DOI:https:\/\/doi.org\/10.1109\/CCECE. 2002 .1013101 10.1109\/CCECE.2002.1013101 B. Huang and W. Kinsner. 2002. ECG frame classification using dynamic time warping. In Proceedings of the IEEE Canadian Conference on Electrical 8 Computer Engineering (No. 02CH37373), Vol. 2. 1105--1110. DOI:https:\/\/doi.org\/10.1109\/CCECE.2002.1013101"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513414"},{"key":"e_1_2_1_24_1","article-title":"Nearest-neighbor-preserving embeddings","volume":"3","author":"Indyk P.","year":"2007","unstructured":"P. Indyk and A. Naor . 2007 . Nearest-neighbor-preserving embeddings . ACM Trans. Algor. 3 , 3, Article 31 (2007). DOI:https:\/\/doi.org\/10.1145\/1273340.1273347 10.1145\/1273340.1273347 P. Indyk and A. Naor. 2007. Nearest-neighbor-preserving embeddings. ACM Trans. Algor. 3, 3, Article 31 (2007). DOI:https:\/\/doi.org\/10.1145\/1273340.1273347","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003278"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Conference on Modern Analysis and Probability (Contemporary Mathematics)","volume":"26","author":"Johnson W.","unstructured":"W. Johnson and J. Lindenstrauss . 1984. Extensions of Lipschitz mappings into a Hilbert space . In Proceedings of the Conference on Modern Analysis and Probability (Contemporary Mathematics) , Vol. 26 . American Mathematical Society, 189--206. W. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Proceedings of the Conference on Modern Analysis and Probability (Contemporary Mathematics), Vol. 26. American Mathematical Society, 189--206."},{"volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"Karger D. R.","key":"e_1_2_1_27_1","unstructured":"D. R. Karger and M. Ruhl . 2002. Finding nearest neighbors in growth-restricted metrics . In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902) . ACM, New York, 741--750. DOI:https:\/\/doi.org\/10.1145\/509907.510013 10.1145\/509907.510013 D. R. Karger and M. Ruhl. 2002. Finding nearest neighbors in growth-restricted metrics. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902). ACM, New York, 741--750. DOI:https:\/\/doi.org\/10.1145\/509907.510013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_29_1","first-page":"2","article-title":"On variants of the Johnson-Lindenstrauss lemma","volume":"33","author":"Matou\u0161ek J.","year":"2008","unstructured":"J. Matou\u0161ek . 2008 . On variants of the Johnson-Lindenstrauss lemma . Rand. Struct. Algor. 33 , 2 (Sept. 2008), 142--156. DOI:https:\/\/doi.org\/10.1002\/rsa.v33:2 10.1002\/rsa.v33:2 J. Matou\u0161ek. 2008. On variants of the Johnson-Lindenstrauss lemma. Rand. Struct. Algor. 33, 2 (Sept. 2008), 142--156. DOI:https:\/\/doi.org\/10.1002\/rsa.v33:2","journal-title":"Rand. Struct. Algor."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231541.3231549"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397518","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397518","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:33Z","timestamp":1750193253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397518"}},"subtitle":["Unified Treatment of Discrete Fr\u00e9chet and Dynamic Time Warping Distances"],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3397518"],"URL":"https:\/\/doi.org\/10.1145\/3397518","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}