{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T14:16:05Z","timestamp":1762956965250,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["JA 2109\/4-2","NI 369\/18-1"],"award-info":[{"award-number":["JA 2109\/4-2","NI 369\/18-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length-<jats:italic>n<\/jats:italic> time series, however, requires\u00a0<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\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, which is often too slow for real-world applications. Therefore, many heuristics have been proposed to speed up the DTW computation. These are often based on lower bounding techniques, approximating the DTW distance, or considering special input data such as binary or piecewise constant time series. In this paper, we present a first exact algorithm to compute the DTW distance of two run-length encoded time series whose running time only depends on the encoding lengths of the inputs. The worst-case running time is cubic in the encoding length. In experiments we show that our algorithm is indeed fast for time series with short encoding lengths.<\/jats:p>","DOI":"10.1007\/s00453-022-01038-3","type":"journal-article","created":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T08:04:14Z","timestamp":1663833854000},"page":"492-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8499-0130","authenticated-orcid":false,"given":"Vincent","family":"Froese","sequence":"first","affiliation":[]},{"given":"Brijnesh","family":"Jain","sequence":"additional","affiliation":[]},{"given":"Maciej","family":"Rymar","sequence":"additional","affiliation":[]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,22]]},"reference":[{"key":"1038_CR1","first-page":"1","volume":"33","author":"A Abanda","year":"2018","unstructured":"Abanda, A., Mori, U., Lozano, J.A.: A review on distance based time series classification. Data Min. Knowl. Disc. 33, 1\u201335 (2018)","journal-title":"Data Min. Knowl. Disc."},{"key":"1038_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u00a0\u201915), pp 59\u201378 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"1038_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Bringmann, K., K\u00fcnnemann, M.: Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u00a0\u201917), IEEE, pp 192\u2013203 (2017)","DOI":"10.1109\/FOCS.2017.26"},{"key":"1038_CR4","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.is.2015.04.007","volume":"53","author":"S Aghabozorgi","year":"2015","unstructured":"Aghabozorgi, S., Shirkhorshidi, A.S., Wah, T.Y.: Time-series clustering-a decade review. Inf. Syst. 53, 16\u201338 (2015)","journal-title":"Inf. Syst."},{"issue":"8","key":"1038_CR5","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.4304\/jcp.9.8.1769-1775","volume":"9","author":"SB Ahsan","year":"2014","unstructured":"Ahsan, S.B., Aziz, S.P., Rahman, M.S.: Longest common subsequence problem for run-length-encoded strings. J. Comput. 9(8), 1769\u20131775 (2014)","journal-title":"J. Comput."},{"issue":"3","key":"1038_CR6","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s10618-016-0483-9","volume":"31","author":"A Bagnall","year":"2017","unstructured":"Bagnall, A., Lines, J., Bostrom, A., Large, J., Keogh, E.: The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Min. Knowl. Disc. 31(3), 606\u2013660 (2017)","journal-title":"Data Min. Knowl. Disc."},{"key":"1038_CR7","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u00a0\u201915), pp 79\u201397 (2015)","DOI":"10.1109\/FOCS.2015.15"},{"issue":"2","key":"1038_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1145\/568518.568520","volume":"27","author":"K Chakrabarti","year":"2002","unstructured":"Chakrabarti, K., Keogh, E., Mehrotra, S., Pazzani, M.: Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst. 27(2), 188\u2013228 (2002)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"1038_CR9","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00453-011-9592-4","volume":"65","author":"K Chen","year":"2013","unstructured":"Chen, K., Chao, K.: A fully compressed algorithm for computing the edit distance of run-length encoded strings. Algorithmica 65(2), 354\u2013370 (2013)","journal-title":"Algorithmica"},{"key":"1038_CR10","unstructured":"Clifford, R., Gawrychowski, P., Kociumaka, T., Martin, D.P., Uznanski, P.: RLE edit distance in near optimal time. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u00a0\u201919), Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol. 138, pp 66:1\u201366:13 (2019)"},{"key":"1038_CR11","unstructured":"Dau, H.A., Keogh, E., Kamgar, K., Yeh, C.C.M., Zhu, Y., Gharghabi, S., Ratanamahatana, C.A., Yanping, Hu, B., Begum, N., Bagnall, A., Mueen, A., Batista, G., Hexagon-M.L.: The UCR time series classification archive. (2018) https:\/\/www.cs.ucr.edu\/~eamonn\/time_series_data_2018\/"},{"key":"1038_CR12","doi-asserted-by":"crossref","unstructured":"Dupont, M., Marteau, P.F.: Coarse-DTW for sparse time series alignment. In: First ECML PKDD Workshop on Advanced Analysis and Learning on Temporal Data (AALTD\u00a0\u201915), pp 157\u2013172 (2016)","DOI":"10.1007\/978-3-319-44412-3_11"},{"key":"1038_CR13","unstructured":"Faloutsos, C., Jagadish, H., Mendelzon, A., Milo, T.: A signature technique for similarity-based queries. In: Proceedings of the Compression and Complexity of Sequences 1997\u00a0(SEQUENCES \u201997), IEEE, pp 11\u201313 (1997)"},{"issue":"4","key":"1038_CR14","doi-asserted-by":"publisher","first-page":"50:1","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. Algorithm. 14(4), 50:1-50:17 (2018)","journal-title":"ACM Trans. Algorithm."},{"key":"1038_CR15","doi-asserted-by":"crossref","unstructured":"Hwang, Y., Gelfand, S.B.: Sparse dynamic time warping. In: Proceedings of the 13th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM\u00a0\u201917), pp 163\u2013175 (2017)","DOI":"10.1007\/978-3-319-62416-7_12"},{"key":"1038_CR16","doi-asserted-by":"crossref","unstructured":"Hwang, Y., Gelfand, S.B.: Constrained sparse dynamic time warping. In: 2018 17th IEEE International Conference on Machine Learning and Applications (ICMLA\u00a0\u201918), pp 216\u2013222 (2018)","DOI":"10.1109\/ICMLA.2018.00039"},{"key":"1038_CR17","unstructured":"Hwang, Y., Gelfand, S.B.: Binary sparse dynamic time warping. In: Proceedings of the 15th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM\u00a0\u201919) (2019)"},{"issue":"4","key":"1038_CR18","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1038_CR19","unstructured":"Jain, B.J., Froese, V., Schultz, D.: An average-compress algorithm for the sample mean problem under dynamic time warping. CoRR (2019) arXiv:1909.13541"},{"issue":"3","key":"1038_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/PL00011669","volume":"3","author":"E Keogh","year":"2001","unstructured":"Keogh, E., Chakrabarti, K., Pazzani, M., Mehrotra, S.: Dimensionality reduction for fast similarity search in large time series databases. Knowl. Inf. Syst. 3(3), 263\u2013286 (2001)","journal-title":"Knowl. Inf. Syst."},{"key":"1038_CR21","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 (ICALP\u00a0\u201919), Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol 132, pp 80:1\u201380:15 (2019)"},{"key":"1038_CR22","unstructured":"Kuszmaul, W.: Binary dynamic time warping in linear time. CoRR (2021) arXiv:2101.01108"},{"key":"1038_CR23","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. In: 2016 IEEE 16th International Conference on Data Mining (ICDM\u00a0\u201916), pp 350\u2013359 (2016)","DOI":"10.1109\/ICDM.2016.0046"},{"issue":"1","key":"1038_CR24","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":"2","key":"1038_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10115-018-1163-4","volume":"57","author":"A Sharabiani","year":"2018","unstructured":"Sharabiani, A., Darabi, H., Harford, S., Douzali, E., Karim, F., Johnson, H., Chen, S.: Asymptotic dynamic time warping calculation with utilizing value repetition. Knowl. Inf. Syst. 57(2), 359\u2013388 (2018)","journal-title":"Knowl. Inf. Syst."},{"issue":"4","key":"1038_CR26","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1007\/s10618-018-0557-y","volume":"32","author":"DF Silva","year":"2018","unstructured":"Silva, D.F., Giusti, R., Keogh, E., Batista, G.: Speeding up similarity search under dynamic time warping by pruning unpromising alignments. Data Min. Knowl. Disc. 32(4), 988\u20131016 (2018)","journal-title":"Data Min. Knowl. Disc."},{"issue":"2","key":"1038_CR27","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."},{"key":"1038_CR28","doi-asserted-by":"crossref","unstructured":"Yamada, K., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Faster STR-EC-LCS computation. In: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Informatics, (SOFSEM\u00a0\u201920), Springer, LNCS, vol. 12011, pp 125\u2013135 (2020)","DOI":"10.1007\/978-3-030-38919-2_11"},{"key":"1038_CR29","unstructured":"Yi, B.K., Faloutsos, C.: Fast time sequence indexing for arbitrary $$\\cal{L}_p$$ norms. In: Proceedings of the 26th VLDB Conference, pp 385\u2013394 (2000)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01038-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01038-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01038-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T09:18:56Z","timestamp":1674811136000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01038-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,22]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1038"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01038-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,9,22]]},"assertion":[{"value":"17 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}