{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313644,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of length<jats:italic>n<\/jats:italic>such that the dissimilarity between any elements is an integer between zero and<jats:italic>c<\/jats:italic>, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(c n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>c<\/mml:mi><mml:msup><mml:mi>n<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which can be translated to<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for constant dissimilarity functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.<\/jats:p>","DOI":"10.1007\/s00453-022-00968-2","type":"journal-article","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T06:03:01Z","timestamp":1652248981000},"page":"2581-2596","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length"],"prefix":"10.1007","volume":"84","author":[{"given":"Yoshifumi","family":"Sakai","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,11]]},"reference":[{"key":"968_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures, FOCS 2015: 59\u201378","DOI":"10.1109\/FOCS.2015.14"},{"key":"968_CR2","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. FOCS 2015: 79\u201397","DOI":"10.1109\/FOCS.2015.15"},{"key":"968_CR3","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"968_CR4","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inform. Comput. 208, 1054\u20131059 (2010)","journal-title":"Inform. Comput."},{"key":"968_CR5","doi-asserted-by":"crossref","unstructured":"Dupont, M., Marteau, P.-F.: Coarse-DTW for sparse time series alignment. AALTD 2015: 157\u2013172","DOI":"10.1007\/978-3-319-44412-3_11"},{"key":"968_CR6","unstructured":"Froese, V., Jain, B., Rymar, M., Weller, M.: Fast exact dynamic time warping on run-length encoded time series. CoRR abs\/1903.03003 (2020)"},{"issue":"4","key":"968_CR7","doi-asserted-by":"publisher","first-page":"501","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. Algorith. 14(4), 501\u20135017 (2018)","journal-title":"ACM Trans. Algorith."},{"key":"968_CR8","unstructured":"Gold, O., Sharir, M.: Dynamic time warping and geometric edit distance: breaking the quadratic barrier. CoRR abs\/1607.05994v4 (2020)"},{"issue":"6","key":"968_CR9","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"key":"968_CR10","doi-asserted-by":"crossref","unstructured":"Hwang, Y., Gelfand, S.B.: Sparse dynamic time warping. MLDM 2017: 163\u2013175","DOI":"10.1007\/978-3-319-62416-7_12"},{"key":"968_CR11","first-page":"748","volume":"2","author":"Y Hwang","year":"2019","unstructured":"Hwang, Y., Gelfand, S.B.: Binary sparse dynamic time warping. MLDM 2, 748\u2013759 (2019)","journal-title":"MLDM"},{"key":"968_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.compenvurbsys.2015.10.009","volume":"55","author":"Z Izakian","year":"2016","unstructured":"Izakian, Z., Mesgari, M.S., Abraham, A.: Automated clustering of trajectory data using a particle swarm optimization. Comput. Environ. Urban Syst. 55, 55\u201365 (2016)","journal-title":"Comput. Environ. Urban Syst."},{"key":"968_CR13","doi-asserted-by":"crossref","unstructured":"Jang, J.-S.R., Lee, H.-R.: Hierarchical filtering method for content-based music retrieval via acoustic input. ACM Multimedia 2001: 401\u2013410","DOI":"10.1145\/500141.500201"},{"issue":"1\u201350","key":"968_CR14","first-page":"6","volume":"50","author":"P Jangyodsuk","year":"2014","unstructured":"Jangyodsuk, P., Conly, C., Athitsos, V.: Sign language recognition using dynamic time warping and hand shape distance based on histogram of oriented gradient features. PETRA 50(1\u201350), 6 (2014)","journal-title":"PETRA"},{"key":"968_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.cmpb.2017.09.007","volume":"152","author":"J Jiang","year":"2017","unstructured":"Jiang, J., Xing, Y., Wang, S., Liang, K.: Evaluation of robotic surgery skills using dynamic time warping. Comput. Methods Programs Biomed. 152, 71\u201383 (2017)","journal-title":"Comput. Methods Programs Biomed."},{"key":"968_CR16","doi-asserted-by":"crossref","unstructured":"Johnen, B., Kuhlenk\u00f6tter, B.: A dynamic time warping algorithm for industrial robot motion analysis. CISS 2016: 18\u201323","DOI":"10.1109\/CISS.2016.7460470"},{"issue":"1\u201380","key":"968_CR17","first-page":"15","volume":"80","author":"W Kuszmaul","year":"2019","unstructured":"Kuszmaul, W.: Dynamic time warping in strongly subquadratic time: algorithms for the low-distance regime and approximate evaluation. ICALP 80(1\u201380), 15 (2019)","journal-title":"ICALP"},{"key":"968_CR18","unstructured":"Kuszmaul, W.: Binary dynamic time warping in linear time. CoRR abs\/2101.01108 (2021)"},{"key":"968_CR19","unstructured":"Muda, L., Begam, M., Elamvazuthi, I.: Voice recognition algorithms using mel frequency cepstral coefficient (MFCC) and dynamic time warping (DTW) techniques. CoRR abs\/1003.4083 (2010)"},{"key":"968_CR20","doi-asserted-by":"crossref","unstructured":"Mueen, A., Chavoshi, N., Abu-El-Rub, N., Hamooni, H., Minnich, A.: AWarp: Fast warping distance for sparse time series. ICDM 2016: 350\u2013359","DOI":"10.1109\/ICDM.2016.0046"},{"key":"968_CR21","doi-asserted-by":"crossref","unstructured":"M\u00fcller, M.: Dynamic time warping. In: Information Retrieval for Music and Motion (2007)","DOI":"10.1007\/978-3-540-74048-3"},{"key":"968_CR22","doi-asserted-by":"crossref","unstructured":"Rath, T.M., Manmatha, R.: Word image matching using dynamic time warping. CVPR 2: 521\u2013527 (2003)","DOI":"10.1109\/CVPR.2003.1211511"},{"key":"968_CR23","doi-asserted-by":"publisher","first-page":"2175","DOI":"10.1016\/j.dam.2011.06.022","volume":"159","author":"Y Sakai","year":"2011","unstructured":"Sakai, Y.: A fast algorithm for multiplying min-sum permutations. Discrete Appl. Math. 159, 2175\u20132183 (2011)","journal-title":"Discrete Appl. Math."},{"key":"968_CR24","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2018.06.034","volume":"753","author":"Y Sakai","year":"2019","unstructured":"Sakai, Y.: A substring-substring LCS data structure. Theor. Comput. Sci. 753, 16\u201334 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20136","key":"968_CR25","first-page":"16","volume":"6","author":"Y Sakai","year":"2020","unstructured":"Sakai, Y., Inenaga, S.: A reduction of the dynamic time warping distance to the longest increasing subsequence length. ISAAC 6(1\u20136), 16 (2020)","journal-title":"ISAAC"},{"issue":"1","key":"968_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/TASSP.1978.1163055","volume":"26","author":"H Sakoe","year":"1978","unstructured":"Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26(1), 43\u201349 (1978)","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"issue":"8","key":"968_CR27","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1109\/34.57669","volume":"12","author":"CC Tappert","year":"1990","unstructured":"Tappert, C.C., Suen, C.Y., Wakahara, T.: The state of the art in online handwriting recognition. IEEE Trans. Pattern Anal. Mach. Intell. 12(8), 787\u2013808 (1990)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"968_CR28","first-page":"570","volume":"1","author":"A Tiskin","year":"2008","unstructured":"Tiskin, A.: Semi-local string comparison: algorithmic techniques and applications. Math. Compt. Sci. 1, 570\u2013581 (2008)","journal-title":"Math. Compt. Sci."},{"key":"968_CR29","doi-asserted-by":"crossref","unstructured":"Tiskin, A.: Fast distance multiplication of unit-Monge matrices, Algorithmica, 71 (2015) 859\u2013888 (in Proc.\u00a0of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp.\u00a01287\u20131295)","DOI":"10.1007\/s00453-013-9830-z"},{"key":"968_CR30","doi-asserted-by":"crossref","unstructured":"Vaughan, N., Gabrys, B.: Comparing and combining time series trajectories using dynamic time warping. KES 2016: 465\u2013474","DOI":"10.1016\/j.procs.2016.08.106"},{"issue":"2","key":"968_CR31","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.J.: Experimental comparison of representation methods and distance measures for time series data. Data Min. Knowl. Discov. 26(2), 275\u2013309 (2013)","journal-title":"Data Min. Knowl. Discov."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00968-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00968-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00968-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T09:48:39Z","timestamp":1727171319000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00968-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,11]]},"references-count":31,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["968"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00968-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,5,11]]},"assertion":[{"value":"25 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}