{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T18:00:44Z","timestamp":1755799244591,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s00453-022-00966-4","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T15:06:59Z","timestamp":1650899219000},"page":"2395-2413","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating the Geometric Edit Distance"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2446-8594","authenticated-orcid":false,"given":"Kyle","family":"Fox","sequence":"first","affiliation":[]},{"given":"Xinyi","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"966_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 59\u201378 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"966_CR2","unstructured":"Agarwal, P.K., Fox, K., Pan, J., Ying, R.: Approximating dynamic time warping and edit distance for a pair of point sequences. In: Proceedings of the 32nd International Symposium on Computational Geometry, pp. 6:1\u20136:16 (2016)"},{"key":"966_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Polylogarithmic approximation for edit distance and the asymmetric query complexity. In: Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 377\u2013386 (2010)","DOI":"10.1109\/FOCS.2010.43"},{"key":"966_CR4","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nosatzki, N.S.: Edit distance in near-linear time: it\u2019s a constant factor. In: Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (2020, to appear)","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"966_CR5","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pp. 51\u201358 (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"966_CR6","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: Why walking the dog takes time: Fr\u00e9chet distance has no strongly subquadratic algorithms unless SETH fails. In: Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 661\u2013670 (2014)","DOI":"10.1109\/FOCS.2014.76"},{"key":"966_CR7","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 79\u201397 (2015)","DOI":"10.1109\/FOCS.2015.15"},{"issue":"2","key":"966_CR8","first-page":"46","volume":"7","author":"K Bringmann","year":"2016","unstructured":"Bringmann, K., Mulzer, W.: Approximability of the discrete Fr\u00e9chet distance. JoCG 7(2), 46\u201376 (2016)","journal-title":"JoCG"},{"key":"966_CR9","doi-asserted-by":"crossref","unstructured":"Chakraborty, D., Das, D., Goldenberg, E., Koucky, M., Saks, M.: Approximating edit distance within constant factor in truly sub-quadratic time. In: Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 979\u2013990. IEEE (2018)","DOI":"10.1109\/FOCS.2018.00096"},{"key":"966_CR10","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.ipl.2018.06.011","volume":"138","author":"TM Chan","year":"2018","unstructured":"Chan, T.M., Rahmati, Z.: An improved approximation algorithm for the discrete Fr\u00e9chet distance. Inf. Process. Lett. 138, 72\u201374 (2018)","journal-title":"Inf. Process. Lett."},{"key":"966_CR11","doi-asserted-by":"crossref","unstructured":"Chen, L., Ng, R.: On the marriage of Lp-norms and edit distance. In: Proceedings of the 30th International Conference on Very Large Databases, pp. 792\u2013803 (2004)","DOI":"10.1016\/B978-012088469-8.50070-X"},{"key":"966_CR12","doi-asserted-by":"crossref","unstructured":"Chen, L., \u00d6zsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pp. 491\u2013502 (2005)","DOI":"10.1145\/1066157.1066213"},{"key":"966_CR13","unstructured":"Fox, K., Li, X.: Approximating the geometric edit distance. In: Proceedings of the 30th International Symposium on Algorithms and Computation, pp. 26:1\u201326:16 (2019)"},{"issue":"4","key":"966_CR14","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/3230734","volume":"14","author":"O Gold","year":"2018","unstructured":"Gold, O., Sharir, M.: Dynamic time warping and geometric edit distance: breaking the quadratic barrier. ACM Trans. Algorithms 14(4), 50 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"966_CR15","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Geometric approximation algorithms, chap. 11, Random Partition via Shifting. American Mathematical Society (2011)","DOI":"10.1090\/surv\/173"},{"issue":"2","key":"966_CR16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comp. Sys. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comp. Sys. Sci."},{"key":"966_CR17","unstructured":"Kuszmaul, W.: Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation. In: Proceedings of the 46th International Colloquium on Automata, Languages and Programming (2019)"},{"issue":"2","key":"966_CR18","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"GM Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27(2), 557\u2013582 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"966_CR19","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/TPAMI.2008.76","volume":"31","author":"PF Marteau","year":"2009","unstructured":"Marteau, P.F.: Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans. Pattern Anal. Mach. Intell. 31(2), 306\u2013318 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"966_CR20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"966_CR21","doi-asserted-by":"crossref","unstructured":"Sankararaman, S., Agarwal, P.K., M\u00f8lhave, T., Pan, J., Boedihardjo, A.P.: Model-driven matching and segmentation of trajectories. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 234\u2013243 (2013)","DOI":"10.1145\/2525314.2525360"},{"issue":"4","key":"966_CR22","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1089\/cmb.2008.0100","volume":"16","author":"A Stojmirovic","year":"2009","unstructured":"Stojmirovic, A., Yu, Y.K.: Geometric aspects of biological sequence comparison. J. Comput. Biol. 16(4), 579\u2013611 (2009)","journal-title":"J. Comput. Biol."},{"issue":"1\u20133","key":"966_CR23","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Algorithms for approximate string matching. Inf. Control 64(1\u20133), 100\u2013118 (1985)","journal-title":"Inf. Control"},{"issue":"1","key":"966_CR24","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"issue":"2","key":"966_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10618-012-0250-5","volume":"26","author":"X Wang","year":"2013","unstructured":"Wang, X., Mueen, A., Ding, H., Trajcevski, G., Scheuermann, P., Keogh, E.: Experimental comparison of representation methods and distance measures for time series data. Data Min. Knowl. Disc. 26(2), 275\u2013309 (2013)","journal-title":"Data Min. Knowl. Disc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00966-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00966-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00966-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T14:14:53Z","timestamp":1660313693000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00966-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":25,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["966"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00966-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"14 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}