{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:32:03Z","timestamp":1760441523829,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046927"},{"type":"electronic","value":"9783030046934"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04693-4_14","type":"book-chapter","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T05:03:12Z","timestamp":1543381392000},"page":"218-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Probabilistic Embeddings of the Fr\u00e9chet Distance"],"prefix":"10.1007","author":[{"given":"Anne","family":"Driemel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amer","family":"Krivo\u0161ija","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,29]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Quadratic-time hardness of LCS and other sequence similarity measures. CoRR abs\/1501.07053 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1137\/1.9781611975031.58","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Peyman Afshani","year":"2018","unstructured":"Afshani, P., Driemel, A.: On the complexity of range searching among curves. In: Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 898\u2013917 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.58"},{"issue":"2","key":"14_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/130920526","volume":"43","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Ben Avraham, R., Kaplan, H., Sharir, M.: Computing the discrete Fr\u00e9chet distance in subquadratic time. SIAM J. Comput. 43(2), 429\u2013449 (2014). https:\/\/doi.org\/10.1137\/130920526","journal-title":"SIAM J. Comput."},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Fox, K., Pan, J., Ying, R.: Approximating dynamic time warping and edit distance for a pair of point sequences. In: Fekete, S., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry, SoCG. Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, pp. 6:1\u20136:16. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.6","DOI":"10.4230\/LIPIcs.SoCG.2016.6"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Backurs, A., Sidiropoulos, A.: Constant-distortion embeddings of Hausdorff metrics into constant-dimensional l$$\\_$$p spaces. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM, pp. 1:1\u20131:15 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.1","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.1"},{"key":"14_CR6","doi-asserted-by":"publisher","unstructured":"Badoiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC, pp. 225\u2013233 (2005). https:\/\/doi.org\/10.1145\/1060590.1060624","DOI":"10.1145\/1060590.1060624"},{"key":"14_CR7","unstructured":"Badoiu, M., et al.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 119\u2013128 (2005)"},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Bartal, Y., Gottlieb, L., Neiman, O.: On the impossibility of dimension reduction for doubling subsets of lp. In: ACM Symposium on Computational Geometry, SoCG, pp. 60\u201366 (2014). https:\/\/doi.org\/10.1145\/2582112.2582170","DOI":"10.1145\/2582112.2582170"},{"issue":"6","key":"14_CR9","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., 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":"14_CR10","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: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 661\u2013670 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.76","DOI":"10.1109\/FOCS.2014.76"},{"key":"14_CR11","doi-asserted-by":"publisher","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pp. 79\u201397 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.15","DOI":"10.1109\/FOCS.2015.15"},{"issue":"1\u20132","key":"14_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1142\/S0218195917600056","volume":"27","author":"K Bringmann","year":"2017","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Improved approximation for Fr\u00e9chet distance on $$c$$-packed curves matching conditional lower bounds. Int. J. Comput. Geom. Appl. 27(1\u20132), 85\u2013120 (2017). https:\/\/doi.org\/10.1142\/S0218195917600056","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"1399","DOI":"10.1137\/1.9781611973402.103","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kevin Buchin","year":"2013","unstructured":"Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four Soviets walk the dog-with an application to Alt\u2019s conjecture. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1399\u20131413 (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.103"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Buchin, K., et al.: Folding free-space diagrams: computing the Fr\u00e9chet distance between 1-dimensional curves (multimedia contribution). In: 33rd International Symposium on Computational Geometry, SoCG, pp. 64:1\u201364:5 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.64","DOI":"10.4230\/LIPIcs.SoCG.2017.64"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Driemel, A., Silvestri, F.: FRESH: Fr\u00e9chet similarity with hashing. CoRR abs\/1809.02350 (2018)","DOI":"10.1007\/978-3-030-24766-9_19"},{"issue":"2","key":"14_CR16","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.14778\/1454159.1454226","volume":"1","author":"H Ding","year":"2008","unstructured":"Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E.: Querying and mining of time series data: experimental comparison of representations and distance measures. Proc. VLDB Endow. 1(2), 1542\u20131552 (2008). https:\/\/doi.org\/10.14778\/1454159.1454226","journal-title":"Proc. VLDB Endow."},{"issue":"5","key":"14_CR17","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."},{"issue":"1","key":"14_CR18","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-012-9402-z","volume":"48","author":"A Driemel","year":"2012","unstructured":"Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fr\u00e9chet distance for realistic curves in near-linear time. Discrete Comput. Geom. 48(1), 94\u2013127 (2012). https:\/\/doi.org\/10.1007\/s00454-012-9402-z","journal-title":"Discrete Comput. Geom."},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"Driemel, A., Krivo\u0161ija, A., Sohler, C.: Clustering time series under the Fr\u00e9chet distance. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 766\u2013785 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch55","DOI":"10.1137\/1.9781611974331.ch55"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Driemel, A., Silvestri, F.: Locally-sensitive hashing of curves. In: 33st International Symposium on Computational Geometry, SoCG, pp. 37:1\u201337:16 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.37","DOI":"10.4230\/LIPIcs.SoCG.2017.37"},{"key":"14_CR21","unstructured":"Eiter, T., Mannila, H.: Computing discrete Fr\u00e9chet distance. Technical report, CD-TR 94\/64, Christian Doppler Laboratory (1994)"},{"key":"14_CR22","doi-asserted-by":"publisher","unstructured":"Emiris, I.Z., Psarros, I.: Products of Euclidean metrics and applications to proximity questions among curves. In: Speckmann, B., T\u00f3th, C.D. (eds.) 34th International Symposium on Computational Geometry, SoCG, pp. 37:1\u201337:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.37","DOI":"10.4230\/LIPIcs.SoCG.2018.37"},{"key":"14_CR23","doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Losievskaja, E., Rosamond, F.A., Saurabh, S.: Distortion is fixed parameter tractable. TOCT 5(4), 16:1\u201316:20 (2013). https:\/\/doi.org\/10.1145\/2489789, https:\/\/doi.org\/10.1145\/2489789","DOI":"10.1145\/2489789 10.1145\/2489789"},{"key":"14_CR24","doi-asserted-by":"publisher","unstructured":"Gold, O., Sharir, M.: Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 25:1\u201325:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.25","DOI":"10.4230\/LIPIcs.ICALP.2017.25"},{"issue":"1","key":"14_CR25","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/S0196-6774(03)00083-X","volume":"49","author":"J H\u00e5stad","year":"2003","unstructured":"H\u00e5stad, J., Ivansson, L., Lagergren, J.: Fitting points on the real line and its application to RH mapping. J. Algorithms 49(1), 42\u201362 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(03)00083-X","journal-title":"J. Algorithms"},{"key":"14_CR26","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 10\u201333 (2001). https:\/\/doi.org\/10.1109\/SFCS.2001.959878","DOI":"10.1109\/SFCS.2001.959878"},{"key":"14_CR27","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Approximate nearest neighbor algorithms for Fr\u00e9chet distance via product metrics. In: Symposium on Computational Geometry, SoCG, pp. 102\u2013106 (2002). https:\/\/doi.org\/10.1145\/513400.513414","DOI":"10.1145\/513400.513414"},{"key":"14_CR28","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch8","volume-title":"Handbook of Discrete and Computational Geometry, Second Edition","author":"Piotr Indyk","year":"2004","unstructured":"Indyk, P., Matou\u0161ek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 177\u2013196. CRC Press (2004). https:\/\/doi.org\/10.1201\/9781420035315.ch8"},{"issue":"3","key":"14_CR29","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/s10115-004-0154-9","volume":"7","author":"E Keogh","year":"2005","unstructured":"Keogh, E., Ratanamahatana, C.A.: Exact indexing of dynamic time warping. Knowl. Inf. Syst. 7(3), 358\u2013386 (2005)","journal-title":"Knowl. Inf. Syst."},{"issue":"1","key":"14_CR30","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93(1), 333\u2013344 (1996)","journal-title":"Isr. J. Math."},{"key":"14_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-540-74048-3_4","volume-title":"Information Retrieval for Music and Motion","author":"M M\u00fcller","year":"2007","unstructured":"M\u00fcller, M.: Dynamic time warping. In: M\u00fcller, M. (ed.) Information Retrieval for Music and Motion, pp. 69\u201384. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74048-3_4"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Nayyeri, A., Raichel, B.: Reality distortion: exact and approximate algorithms for embedding into the line. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pp. 729\u2013747 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.50","DOI":"10.1109\/FOCS.2015.50"},{"key":"14_CR33","doi-asserted-by":"publisher","unstructured":"Rakthanmanon, T., et al.: Searching and mining trillions of time series subsequences under dynamic time warping. In: The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 262\u2013270 (2012). https:\/\/doi.org\/10.1145\/2339530.2339576","DOI":"10.1145\/2339530.2339576"},{"issue":"1","key":"14_CR34","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3231541.3231549","volume":"10","author":"Martin Werner","year":"2018","unstructured":"Werner, M., Oliver, D.: ACM SIGSPATIAL GIS Cup 2017: range queries under Fr\u00e9chet distance. SIGSPATIAL Spec. 10(1), 24\u201327 (2018). https:\/\/doi.org\/10.1145\/3231541.3231549, http:\/\/sigspatial2017.sigspatial.org\/giscup2017\/home","journal-title":"SIGSPATIAL Special"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04693-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:24:08Z","timestamp":1710249848000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04693-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046927","9783030046934"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04693-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Helsinki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Finland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2018.hiit.fi\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}