{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:56Z","timestamp":1740109316336,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T00:00:00Z","timestamp":1670976000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T00:00:00Z","timestamp":1670976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1042\/22","IP-2019-04-6268"],"award-info":[{"award-number":["1042\/22","IP-2019-04-6268"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s00453-022-01080-1","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T15:02:52Z","timestamp":1671030172000},"page":"1490-1519","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic"],"prefix":"10.1007","volume":"85","author":[{"given":"Arnold","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3978-1428","authenticated-orcid":false,"given":"Omrit","family":"Filtser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,14]]},"reference":[{"key":"1080_CR1","doi-asserted-by":"publisher","unstructured":"Afshani, P., Driemel, A.: On the complexity of range searching among curves. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pp 898\u2013917, (2018), https:\/\/doi.org\/10.1137\/1.9781611975031.58","DOI":"10.1137\/1.9781611975031.58"},{"key":"1080_CR2","doi-asserted-by":"publisher","unstructured":"Aronov, B., Filtser, O., Horton, M., Katz, M.J., Sheikhan, K.: Efficient nearest-neighbor query and clustering of planar curves. In: Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5\u20137, 2019, Proceedings, pp 28\u201342 (2019), https:\/\/doi.org\/10.1007\/978-3-030-24766-9_3","DOI":"10.1007\/978-3-030-24766-9_3"},{"key":"1080_CR3","doi-asserted-by":"publisher","unstructured":"Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., L\u00f6ffler, M., Struijs, M.: Approximating (k, l)-center clustering for curves. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp 2922\u20132938, (2019), https:\/\/doi.org\/10.1137\/1.9781611975482.181","DOI":"10.1137\/1.9781611975482.181"},{"key":"1080_CR4","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Driemel, A., Nusser, A., Psarros, I.: Tight bounds for approximate near neighbor searching for time series under the Fr\u00e9chet distance. In: Symposium on Discrete Algorithms, SODA (2022)","DOI":"10.1137\/1.9781611977073.25"},{"key":"1080_CR5","doi-asserted-by":"publisher","unstructured":"Buchin, M., Driemel, A., van Greevenbroek, K., Psarros, I., Rohde, D.: Approximating length-restricted means under dynamic time warping. In: Approximation and Online Algorithms\u201420th International Workshop, WAOA, volume 13538, pp 225\u2013253, (2022), https:\/\/doi.org\/10.1007\/978-3-031-18367-6_12","DOI":"10.1007\/978-3-031-18367-6_12"},{"key":"1080_CR6","doi-asserted-by":"publisher","unstructured":"Bereg, S., Jiang, M., Wang, W., Yang, B., Zhu, B.: Simplifying 3D polygonal chains under the discrete Fr\u00e9chet distance. In LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, B\u00fazios, Brazil, April 7-11, 2008, Proceedings, pp 630\u2013641, (2008), https:\/\/doi.org\/10.1007\/978-3-540-78773-0_54","DOI":"10.1007\/978-3-540-78773-0_54"},{"key":"1080_CR7","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: Why walking the dog takes time: Fr\u00e9chet distance has no strongly subquadratic algorithms unless SETH fails. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp 661\u2013670, 2014, https:\/\/doi.org\/10.1109\/FOCS.2014.76","DOI":"10.1109\/FOCS.2014.76"},{"issue":"6","key":"1080_CR8","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.comgeo.2012.11.006","volume":"46","author":"M de Berg","year":"2013","unstructured":"de Berg, M., Cook, A.F., IV., Gudmundsson, J.: Fast Fr\u00e9chet queries. Comput. Geom. 46(6), 747\u2013755 (2013). https:\/\/doi.org\/10.1016\/j.comgeo.2012.11.006","journal-title":"Comput. Geom."},{"key":"1080_CR9","doi-asserted-by":"publisher","unstructured":"de Berg, M., Gudmundsson, J., Mehrabi, A. D.: 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 2017, Redondo Beach, CA, USA, November 7\u201310, 2017, pp 48:1\u201348:4, (2017), https:\/\/doi.org\/10.1145\/3139958.3140023","DOI":"10.1145\/3139958.3140023"},{"issue":"5","key":"1080_CR10","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1137\/120865112","volume":"42","author":"A Driemel","year":"2013","unstructured":"Driemel, A., Har-Peled, S.: Jaywalking your dog: Computing the Fr\u00e9chet distance with shortcuts. SIAM J. Comput. 42(5), 1830\u20131866 (2013). https:\/\/doi.org\/10.1137\/120865112","journal-title":"SIAM J. Comput."},{"key":"1080_CR11","doi-asserted-by":"publisher","unstructured":"Driemel, A., Psarros, I.: ANN for time series under the Fr\u00e9chet distance. In: A. Lubiw and M. R. Salavatipour, editors, Algorithms and Data Structures\u201417th International Symposium, WADS 2021, Virtual Event, August 9-11, 2021, Proceedings, volume 12808 of Lecture Notes in Computer Science, pp 315\u2013328. Springer, (2021), https:\/\/doi.org\/10.1007\/978-3-030-83508-8_23","DOI":"10.1007\/978-3-030-83508-8_23"},{"key":"1080_CR12","unstructured":"Driemel, A., Psarros, I., Schmidt, M.: Sublinear data structures for short Fr\u00e9chet queries. CoRR, abs\/1907.04420, 2019, arXiv:1907.04420"},{"key":"1080_CR13","doi-asserted-by":"publisher","unstructured":"Driemel, A., Silvestri, F.: Locality-sensitive hashing of curves. In Proceedings of the 33rd International Symposium on Computational Geometry, volume 77, pp 37:1\u201337:16, Brisbane, Australia, July 2017. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.37","DOI":"10.4230\/LIPIcs.SoCG.2017.37"},{"issue":"4","key":"1080_CR14","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/3397518","volume":"6","author":"IZ Emiris","year":"2020","unstructured":"Emiris, I.Z., Psarros, I.: Products of Euclidean metrics, applied to proximity problems among curves: unified treatment of discrete Fr\u00e9chet and dynamic time warping distances. ACM Trans. Spatial Algorithms Syst. 6(4), 27:1-27:20 (2020). https:\/\/doi.org\/10.1145\/3397518","journal-title":"ACM Trans. Spatial Algorithms Syst."},{"key":"1080_CR15","doi-asserted-by":"publisher","unstructured":"Filtser, A., Filtser, O., Katz, M. J.: Approximate nearest neighbor for curves\u2014simple, efficient, and deterministic. In: A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 48:1\u201348:19. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2020, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.48","DOI":"10.4230\/LIPIcs.ICALP.2020.48"},{"issue":"1","key":"1080_CR16","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012). https:\/\/doi.org\/10.4086\/toc.2012.v008a014","journal-title":"Theory Comput."},{"key":"1080_CR17","doi-asserted-by":"publisher","unstructured":"Har-Peled, S., Kumar, N.: Approximate nearest neighbor search for low dimensional queries. In: D. Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23\u201325, 2011, pp 854\u2013867. SIAM, 2011, https:\/\/doi.org\/10.1137\/1.9781611973082.67","DOI":"10.1137\/1.9781611973082.67"},{"key":"1080_CR18","unstructured":"Indyk, P.: High-dimensional computational geometry. PhD thesis, Stanford University, 2000"},{"key":"1080_CR19","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Approximate nearest neighbor algorithms for Fr\u00e9chet distance via product metrics. In: Proceedings of the 8th Symposium on Computational Geometry, pp 102\u2013106, Barcelona, Spain, June 2002. ACM Press, https:\/\/doi.org\/10.1145\/513400.513414","DOI":"10.1145\/513400.513414"},{"key":"1080_CR20","doi-asserted-by":"publisher","unstructured":"Kumar, P., Mitchell, J. S. B., Yildirim, E. A.: Comuting core-sets and approximate smallest enclosing hyperspheres in high dimensions. In: Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003, pp 45\u201355, (2003), https:\/\/doi.org\/10.1145\/996546.996548","DOI":"10.1145\/996546.996548"},{"issue":"9","key":"1080_CR21","doi-asserted-by":"publisher","first-page":"2169","DOI":"10.1016\/j.patcog.2008.11.030","volume":"42","author":"D Lemire","year":"2009","unstructured":"Lemire, D.: Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recogn. 42(9), 2169\u20132180 (2009). https:\/\/doi.org\/10.1016\/j.patcog.2008.11.030","journal-title":"Pattern Recogn."},{"issue":"1","key":"1080_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984). https:\/\/doi.org\/10.1145\/2422.322418","journal-title":"J. ACM"},{"issue":"2","key":"1080_CR23","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004). https:\/\/doi.org\/10.1016\/j.jalgor.2003.12.002","journal-title":"J. Algorithms"},{"key":"1080_CR24","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4908.001.0001","volume-title":"Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (neural Information Processing)","author":"G Shakhnarovich","year":"2006","unstructured":"Shakhnarovich, G., Darrell, T., Indyk, P.: Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (neural Information Processing). The MIT press, Cambridge (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01080-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01080-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01080-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T00:03:43Z","timestamp":1682381023000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01080-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,14]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1080"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01080-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,12,14]]},"assertion":[{"value":"20 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}