{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T14:54:55Z","timestamp":1775660095555,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP210100072"],"award-info":[{"award-number":["DP210100072"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Nearest neighbour similarity measures are widely used in many time series data analysis applications. They compute a measure of similarity between two time series. Most applications require tuning of these measures\u2019 meta-parameters in order to achieve good performance. However, most measures have at least <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(L^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>L<\/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> complexity, making them computationally expensive and the process of learning their meta-parameters burdensome, requiring days even for datasets containing only a few thousand series. In this paper, we propose <jats:sc>UltraFastMPSearch<\/jats:sc>, a family of algorithms to learn the meta-parameters for different types of time series distance measures. These algorithms are significantly faster than the prior state of the art. Our algorithms build upon the state of the art, exploiting the properties of a new efficient exact algorithm which supports early abandoning and pruning for most time series distance measures. We show on 128 datasets from the UCR archive that our new family of algorithms are up to an order of magnitude faster than the previous state of the art.\n<\/jats:p>","DOI":"10.1007\/s10115-022-01827-w","type":"journal-article","created":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T20:02:52Z","timestamp":1673640172000},"page":"2123-2157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Ultra-fast meta-parameter optimization for time series similarity measures with application to nearest neighbour classification"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8377-3241","authenticated-orcid":false,"given":"Chang Wei","family":"Tan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0074-470X","authenticated-orcid":false,"given":"Matthieu","family":"Herrmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9963-5169","authenticated-orcid":false,"given":"Geoffrey I.","family":"Webb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,13]]},"reference":[{"issue":"3","key":"1827_CR1","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1007\/s10618-021-00740-0","volume":"35","author":"S Alaee","year":"2021","unstructured":"Alaee S, Mercer R, Kamgar K, Keogh E (2021) Time series motifs discovery under DTW allows more robust discovery of conserved structure. Data Min Knowl Disc 35(3):863\u2013910","journal-title":"Data Min Knowl Disc"},{"key":"1827_CR2","unstructured":"Bagnall A, Flynn M, Large J, Lines J, Middlehurst M (2020) A tale of two toolkits, report the third: on the usage and performance of HIVE-COTE v1.0. arXiv e-prints pp. arXiv\u20132004"},{"issue":"3","key":"1827_CR3","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 (2017) The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Min Knowl Disc 31(3):606\u2013660","journal-title":"Data Min Knowl Disc"},{"issue":"2","key":"1827_CR4","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1117\/12.238675","volume":"5","author":"JS Boreczky","year":"1996","unstructured":"Boreczky JS, Rowe LA (1996) Comparison of video shot boundary detection techniques. J Electron Imaging 5(2):122\u2013128","journal-title":"J Electron Imaging"},{"key":"1827_CR5","doi-asserted-by":"crossref","unstructured":"Chen L, Ng R (2004) On the marriage of Lp-norms and edit distance. In: Proceedings of the 30th international conference on very large databases (VLDB), pp 792\u2013803","DOI":"10.1016\/B978-012088469-8.50070-X"},{"key":"1827_CR6","doi-asserted-by":"crossref","unstructured":"Chen L, \u00d6zsu MT , Oria V (2005) Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD international conference on management of data (SIGMOD), pp\u00a0491\u2013502","DOI":"10.1145\/1066157.1066213"},{"key":"1827_CR7","doi-asserted-by":"crossref","unstructured":"Dau HA, Keogh E, Kamgar K, Yeh C-CM, Zhu Y, Gharghabi S, Ratanamahatana CA, Yanping Hu, B, Begum N, Bagnall A, Mueen A, Batista G, Hexagon-ML (2018) The UCR time series classification archive. https:\/\/www.cs.ucr.edu\/~eamonn\/time_series_data_2018\/","DOI":"10.1109\/JAS.2019.1911747"},{"issue":"4","key":"1827_CR8","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1007\/s10618-018-0565-y","volume":"32","author":"HA Dau","year":"2018","unstructured":"Dau HA, Silva DF, Petitjean F, Forestier G, Bagnall A, Mueen A, Keogh E (2018) Optimizing dynamic time warping\u2019s window width for time series data mining applications. Data Min Knowl Disc 32(4):1074\u20131120","journal-title":"Data Min Knowl Disc"},{"issue":"5","key":"1827_CR9","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1007\/s10618-020-00701-z","volume":"34","author":"A Dempster","year":"2020","unstructured":"Dempster A, Petitjean F, Webb GI (2020) ROCKET: exceptionally fast and accurate time series classification using random convolutional kernels. Data Min Knowl Disc 34(5):1454\u20131495","journal-title":"Data Min Knowl Disc"},{"key":"1827_CR10","first-page":"1","volume":"7","author":"J Dem\u0161ar","year":"2006","unstructured":"Dem\u0161ar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1\u201330","journal-title":"J Mach Learn Res"},{"key":"1827_CR11","doi-asserted-by":"crossref","unstructured":"Herrmann M, Webb GI (2021) Early abandoning and pruning for elastic distances including dynamic time warping. Data Min Knowl Discov, pp\u00a01\u201325","DOI":"10.1007\/s10618-021-00782-4"},{"issue":"1","key":"1827_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/TASSP.1975.1162641","volume":"23","author":"F Itakura","year":"1975","unstructured":"Itakura F (1975) Minimum prediction residual principle applied to speech recognition. IEEE Trans Acoust Speech Signal Process 23(1):67\u201372","journal-title":"IEEE Trans Acoust Speech Signal Process"},{"issue":"9","key":"1827_CR13","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1016\/j.patcog.2010.09.022","volume":"44","author":"Y-S Jeong","year":"2011","unstructured":"Jeong Y-S, Jeong MK, Omitaomu OA (2011) Weighted dynamic time warping for time series classification. Pattern Recogn 44(9):2231\u20132240","journal-title":"Pattern Recogn"},{"key":"1827_CR14","doi-asserted-by":"crossref","unstructured":"Keogh EJ , Pazzani MJ (2001) Derivative dynamic time warping. In: Proceedings of the 2001 SIAM international conference on data mining, SIAM, pp\u00a01\u201311","DOI":"10.1137\/1.9781611972719.1"},{"issue":"3","key":"1827_CR15","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 CA (2005) Exact indexing of dynamic time warping. Knowl Inf Syst 7(3):358\u2013386","journal-title":"Knowl Inf Syst"},{"key":"1827_CR16","unstructured":"Kim S-W, Park S, Chu WW (2001) An index-based approach for similarity search supporting time warping in large sequence databases. In: Proceedings 17th international conference on data engineering, IEEE, pp\u00a0607\u2013614"},{"issue":"9","key":"1827_CR17","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 (2009) Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recogn 42(9):2169\u20132180","journal-title":"Pattern Recogn"},{"issue":"3","key":"1827_CR18","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10618-014-0361-2","volume":"29","author":"J Lines","year":"2015","unstructured":"Lines J, Bagnall A (2015) Time series classification with ensembles of elastic distance measures. Data Min Knowl Disc 29(3):565\u2013592","journal-title":"Data Min Knowl Disc"},{"key":"1827_CR19","doi-asserted-by":"crossref","unstructured":"Lines J, Taylor S, Bagnall A (2018) Time series classification with HIVE-COTE: the Hierarchical Vote Collective of Transformation-based Ensembles. ACM Trans Knowl Discov Data 12(5)","DOI":"10.1145\/3182382"},{"issue":"3","key":"1827_CR20","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s10618-019-00617-3","volume":"33","author":"B Lucas","year":"2019","unstructured":"Lucas B, Shifaz A, Pelletier C, O\u2019Neill L, Zaidi N, Goethals B, Petitjean F, Webb GI (2019) Proximity Forest: an effective and scalable distance-based classifier for time series. Data Min Knowl Disc 33(3):607\u2013635","journal-title":"Data Min Knowl Disc"},{"issue":"2","key":"1827_CR21","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/TPAMI.2008.76","volume":"31","author":"P-F Marteau","year":"2008","unstructured":"Marteau P-F (2008) Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans Pattern Anal Mach Intell 31(2):306\u2013318","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"11","key":"1827_CR22","doi-asserted-by":"publisher","first-page":"3211","DOI":"10.1007\/s10994-021-06057-9","volume":"110","author":"M Middlehurst","year":"2021","unstructured":"Middlehurst M, Large J, Flynn M, Lines J, Bostrom A, Bagnall A (2021) Hive-cote 2.0: a new meta ensemble for time series classification. Mach Learn 110(11):3211\u20133243","journal-title":"Mach Learn"},{"issue":"3","key":"1827_CR23","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1016\/j.patcog.2010.09.013","volume":"44","author":"F Petitjean","year":"2011","unstructured":"Petitjean F, Ketterlin A, Gan\u00e7arski P (2011) A global averaging method for dynamic time warping, with applications to clustering. Pattern Recogn 44(3):678\u2013693","journal-title":"Pattern Recogn"},{"key":"1827_CR24","doi-asserted-by":"crossref","unstructured":"Rakthanmanon T, Campana B, Mueen A, Batista G, Westover B, Zhu Q, Zakaria J, Keogh E (2012) Searching and mining trillions of time series subsequences under dynamic time warping. In: Proceedings of 18th ACM SIGKDD international conference on knowledge discovery and data mining, pp\u00a0262\u2013270","DOI":"10.1145\/2339530.2339576"},{"key":"1827_CR25","doi-asserted-by":"crossref","unstructured":"Ratanamahatana CA , Keogh E (2004) Making time-series classification more accurate using learned constraints. In: Proceedings of the 2004 SIAM international conference on data mining, SIAM, pp\u00a011\u201322","DOI":"10.1137\/1.9781611972740.2"},{"key":"1827_CR26","doi-asserted-by":"crossref","unstructured":"Ratanamahatana CA, Keogh E (2005) Three myths about dynamic time warping data mining. In: Proceedings of the 2005 SIAM international conference on data mining, SIAM, pp\u00a0506\u2013510","DOI":"10.1137\/1.9781611972757.50"},{"key":"1827_CR27","unstructured":"Sakoe H, Chiba S (1971) A dynamic programming approach to continuous speech recognition. In: International congress on acoustics, vol\u00a03, pp\u00a065\u201369"},{"issue":"5","key":"1827_CR28","doi-asserted-by":"publisher","first-page":"561","DOI":"10.3233\/IDA-2007-11508","volume":"11","author":"S Salvador","year":"2007","unstructured":"Salvador S, Chan P (2007) Toward accurate dynamic time warping in linear time and space. Intell Data Anal 11(5):561\u2013580","journal-title":"Intell Data Anal"},{"issue":"3","key":"1827_CR29","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/s10618-020-00679-8","volume":"34","author":"A Shifaz","year":"2020","unstructured":"Shifaz A, Pelletier C, Petitjean F, Webb GI (2020) TS-CHIEF: a scalable and accurate forest algorithm for time series classification. Data Min Knowl Disc 34(3):742\u2013775","journal-title":"Data Min Knowl Disc"},{"key":"1827_CR30","doi-asserted-by":"crossref","unstructured":"Silva DF, Batista GEAPA (2016) Speeding up all-pairwise dynamic time warping matrix calculation. In: Proceedings of the 2016 SIAM international conference on data mining, Society for Industrial and Applied Mathematics, pp\u00a0837\u2013845","DOI":"10.1137\/1.9781611974348.94"},{"issue":"4","key":"1827_CR31","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1007\/s10618-018-0557-y","volume":"32","author":"DF Silva","year":"2018","unstructured":"Silva DF, Giusti R, Keogh E, Batista GE (2018) Speeding up similarity search under dynamic time warping by pruning unpromising alignments. Data Min Knowl Disc 32(4):988\u20131016","journal-title":"Data Min Knowl Disc"},{"issue":"6","key":"1827_CR32","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1109\/TKDE.2012.88","volume":"25","author":"A Stefan","year":"2012","unstructured":"Stefan A, Athitsos V, Das G (2012) The Move-Split-Merge metric for Time Series. IEEE Trans Knowl Data Eng 25(6):1425\u20131438","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1827_CR33","doi-asserted-by":"crossref","unstructured":"Tan CW, Bergmeir C, Petitjean F, Webb GI (2021) Time series extrinsic regression. Data Min Knowl Discov:1032\u20131060","DOI":"10.1007\/s10618-021-00745-9"},{"key":"1827_CR34","doi-asserted-by":"crossref","unstructured":"Tan CW, Herrmann M, Forestier G, Webb GI, Petitjean F (2018) Efficient search of the best warping window for dynamic time warping. In: Proceedings of the 2018 SIAM international conference on data mining, SIAM, pp\u00a0225\u2013233","DOI":"10.1137\/1.9781611975321.26"},{"key":"1827_CR35","doi-asserted-by":"crossref","unstructured":"Tan CW, Herrmann M , Webb GI (2021) Ultra fast warping window optimization for dynamic time warping. In: 2021 IEEE international conference on data mining, IEEE, pp\u00a0589\u2013598","DOI":"10.1109\/ICDM51629.2021.00070"},{"key":"1827_CR36","doi-asserted-by":"crossref","unstructured":"Tan CW, Petitjean F, Webb GI (2019) Elastic bands across the path: a new framework and method to lower bound DTW. In: Proceedings of the 2019 SIAM international conference on data mining, SIAM, pp\u00a0522\u2013530","DOI":"10.1137\/1.9781611975673.59"},{"issue":"1","key":"1827_CR37","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10618-019-00663-x","volume":"34","author":"CW Tan","year":"2020","unstructured":"Tan CW, Petitjean F, Webb GI (2020) FastEE: fast ensembles of elastic distances for time series classification. Data Min Knowl Disc 34(1):231\u2013272","journal-title":"Data Min Knowl Disc"},{"key":"1827_CR38","doi-asserted-by":"crossref","unstructured":"Tan CW, Webb GI, Petitjean F (2017) Indexing and classifying gigabytes of time series under time warping. In: Proceedings of the 2017 SIAM international conference on data mining, SIAM, pp\u00a0282\u2013290","DOI":"10.1137\/1.9781611974973.32"},{"key":"1827_CR39","doi-asserted-by":"crossref","unstructured":"Vlachos M, Hadjieleftheriou M, Gunopulos D, Keogh E (2003) Indexing multi-dimensional time-series with support for multiple distance measures. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, pp\u00a0216\u2013225","DOI":"10.1145\/956750.956777"},{"key":"1827_CR40","doi-asserted-by":"crossref","unstructured":"Vlachos M, Kollios G, Gunopulos D (2002) Discovering similar multidimensional trajectories. In: Proceedings 18th international conference on data engineering, IEEE, pp\u00a0673\u2013684","DOI":"10.1109\/ICDE.2002.994784"},{"key":"1827_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.107895","volume":"115","author":"GI Webb","year":"2021","unstructured":"Webb GI, Petitjean F (2021) Tight lower bounds for dynamic time warping. Pattern Recogn 115:107895","journal-title":"Pattern Recogn"},{"key":"1827_CR42","doi-asserted-by":"crossref","unstructured":"Wu R, Keogh EJ (2020) FastDTW is approximate and generally slower than the algorithm it approximates. IEEE Trans Knowl Data Eng","DOI":"10.1109\/ICDE51399.2021.00249"},{"key":"1827_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2010\/303140","volume":"2010","author":"D Zhang","year":"2010","unstructured":"Zhang D, Zuo W, Zhang D, Zhang H, Li N (2010) Classification of pulse waveforms using edit distance with real penalty. EURASIP J Adv Signal Process 2010:1\u20138","journal-title":"EURASIP J Adv Signal Process"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01827-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-022-01827-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01827-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,5]],"date-time":"2023-04-05T10:12:02Z","timestamp":1680689522000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-022-01827-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,13]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1827"],"URL":"https:\/\/doi.org\/10.1007\/s10115-022-01827-w","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,13]]},"assertion":[{"value":"28 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 December 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2023","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Change history text: Missing funding note has been updated.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}