{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:43:14Z","timestamp":1757612594499,"version":"3.44.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            The subsequence matching problem utilizing dynamic time warping as the similarity measurement has been recognized as a key operation in time series analysis for more than two decades. Existing index-free algorithms depend on DTW lower bounds to discard the unpromising candidate. However, these approaches typically cost\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            ) time for each candidate, where\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            is the length of the query. Consequently, the overhead of computing the DTW lower bounds occupies a significant portion of the time in subsequence matching tasks. This paper proposes new algorithms capable of computing the DTW lower bounds in average\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (log\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            ) time for each candidate, substantially alleviating this bottleneck of the subsequence matching problem. In addition, this paper designs novel DTW lower bounds according to the characteristics of the subsequence matching problem, which is more effective without introducing significant computational overhead. Based on the above improvements, an efficient subsequence matching algorithm called FSMDTW is designed. Experiments conducted on both real and synthetic datasets show that the proposed algorithm is about 2.6 times faster than SOTA on short and medium-length queries and up to one order of magnitude faster on longer queries.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748220","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3628-3640","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["FSMDTW: A Fast Index-Free Subsequence Matching Algorithm for Dynamic Time Warping"],"prefix":"10.14778","volume":"18","author":[{"given":"Zemin","family":"Chao","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Harbin, Heilongjiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiaoyi","family":"Zheng","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, Heilongjiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhixin","family":"Qi","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, Heilongjiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongzhi","family":"Wang","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Harbin, Heilongjiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 59\u201378","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight hardness results for LCS and other sequence similarity measures. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 59\u201378."},{"key":"e_1_2_1_2_1","volume-title":"2020 IEEE International Conference on Data Mining (ICDM). IEEE, 900\u2013905","author":"Alaee Sara","year":"2020","unstructured":"Sara Alaee, Kaveh Kamgar, and Eamonn Keogh. 2020. Matrix profile XXII: exact discovery of time series motifs under DTW. In 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 900\u2013905."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1007\/s10618-021-00740-0","article-title":"Time series motifs discovery under DTW allows more robust discovery of conserved structure","volume":"35","author":"Alaee Sara","year":"2021","unstructured":"Sara Alaee, Ryan Mercer, Kaveh Kamgar, and Eamonn Keogh. 2021. Time series motifs discovery under DTW allows more robust discovery of conserved structure. Data Mining and Knowledge Discovery 35 (2021), 863\u2013910.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","author":"Anzaroot Sam","year":"2013","unstructured":"Sam Anzaroot and Andrew McCallum. 2013. UMass Citation Field Extraction Dataset. Retrieved May 27, 2019 from http:\/\/www.iesl.cs.umass.edu\/data\/data-umasscitationfield"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.neuroimage.2009.06.057","article-title":"Detection of EEG transients in neonates and older children using a system based on dynamic time-warping template matching and spatial dipole clustering - ScienceDirect","volume":"48","year":"2009","unstructured":"Ardalan, Aarabi,, , Kamran, Kazemi,, , Reinhard, Grebe,, , and Hamid. 2009. Detection of EEG transients in neonates and older children using a system based on dynamic time-warping template matching and spatial dipole clustering - ScienceDirect. NeuroImage 48, 1 (2009), 50\u201362.","journal-title":"NeuroImage"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.14778\/3523210.3523222","article-title":"The inherent time complexity and an efficient algorithm for subsequence matching problem","volume":"15","author":"Chao Zemin","year":"2022","unstructured":"Zemin Chao, Hong Gao, Yinan An, and Jianzhong Li. 2022. The inherent time complexity and an efficient algorithm for subsequence matching problem. Proceedings of the VLDB Endowment 15, 7 (2022), 1453\u20131465.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2025.3544751"},{"key":"e_1_2_1_8_1","first-page":"28","article-title":"Debot: Twitter bot detection via warped correlation","volume":"18","author":"Chavoshi Nikan","year":"2016","unstructured":"Nikan Chavoshi, Hossein Hamooni, and Abdullah Mueen. 2016. Debot: Twitter bot detection via warped correlation.. In Icdm, Vol. 18. 28\u201365.","journal-title":"Icdm"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"2577","DOI":"10.1007\/s10618-021-00782-4","article-title":"Early abandoning and pruning for elastic distances including dynamic time warping","volume":"35","author":"Herrmann Matthieu","year":"2021","unstructured":"Matthieu Herrmann and Geoffrey I Webb. 2021. Early abandoning and pruning for elastic distances including dynamic time warping. Data Mining and Knowledge Discovery 35, 6 (2021), 2577\u20132601.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jneumeth.2016.02.025","article-title":"Rapid annotation of interictal epileptiform discharges via template matching under Dynamic Time Warping","volume":"274","author":"Jing J.","year":"2016","unstructured":"J. Jing, J. Dauwels, T. Rakthanmanon, E. Keogh, and M. B. Westover. 2016. Rapid annotation of interictal epileptiform discharges via template matching under Dynamic Time Warping. Journal of Neuroscience Methods 274 (2016), 179\u2013190.","journal-title":"Journal of Neuroscience Methods"},{"volume-title":"Web and Big Data","author":"Kang Rong","key":"e_1_2_1_11_1","unstructured":"Rong Kang, Chen Wang, Peng Wang, Yuting Ding, and Jianmin Wang. 2018. Matching Consecutive Subpatterns over Streaming Time Series. In Web and Big Data, Yi Cai, Yoshiharu Ishikawa, and Jianliang Xu (Eds.). Springer International Publishing, Cham, 90\u2013105."},{"key":"e_1_2_1_12_1","volume-title":"Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems 3","author":"Keogh Eamonn","year":"2001","unstructured":"Eamonn Keogh, Kaushik Chakrabarti, Michael Pazzani, and Sharad Mehrotra. 2001. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and information Systems 3 (2001), 263\u2013286."},{"key":"e_1_2_1_13_1","volume-title":"Exact indexing of dynamic time warping. Knowledge and information systems 7","author":"Keogh Eamonn","year":"2005","unstructured":"Eamonn Keogh and Chotirat Ann Ratanamahatana. 2005. Exact indexing of dynamic time warping. Knowledge and information systems 7 (2005), 358\u2013386."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings 17th international conference on data engineering. IEEE, 607\u2013614","author":"Kim Sang-Wook","year":"2001","unstructured":"Sang-Wook Kim, Sanghyun Park, and Wesley W Chu. 2001. An index-based approach for similarity search supporting time warping in large sequence databases. In Proceedings 17th international conference on data engineering. IEEE, 607\u2013614."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.11.030"},{"key":"e_1_2_1_16_1","volume-title":"Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern recognition 42, 9","author":"Lemire Daniel","year":"2009","unstructured":"Daniel Lemire. 2009. Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern recognition 42, 9 (2009), 2169\u20132180."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"2236","DOI":"10.14778\/3275366.3284968","article-title":"Scalable, variable-length similarity search in data series: The ULISSE approach","volume":"11","author":"Linardi Michele","year":"2018","unstructured":"Michele Linardi and Themis Palpanas. 2018. Scalable, variable-length similarity search in data series: The ULISSE approach. Proceedings of the VLDB Endowment 11, 13 (2018), 2236\u20132248.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_18_1","volume-title":"2019 IEEE International Conference on Big Knowledge (ICBK). IEEE, 175\u2013182","author":"Madrid Frank","year":"2019","unstructured":"Frank Madrid, Shima Imani, Ryan Mercer, Zachary Zimmerman, Nader Shakibay, and Eamonn Keogh. 2019. Matrix profile xx: Finding and visualizing time series motifs of all lengths using the matrix profile. In 2019 IEEE International Conference on Big Knowledge (ICBK). IEEE, 175\u2013182."},{"key":"e_1_2_1_19_1","volume-title":"Carlo Galuzzi, and Berthold Stegemann","author":"Marcinkevics Ricards","year":"2019","unstructured":"Ricards Marcinkevics, Steven Kelk, Carlo Galuzzi, and Berthold Stegemann. 2019. Discovery of Important Subsequences in Electrocardiogram Beats Using the Nearest Neighbour Algorithm. (2019)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"3729","DOI":"10.1109\/JSTARS.2016.2517118","article-title":"A time-weighted dynamic time warping method for land-use and land-cover mapping","volume":"9","author":"Maus Victor","year":"2016","unstructured":"Victor Maus, Gilberto C\u00e2mara, Ricardo Cartaxo, Alber Sanchez, Fernando M Ramos, and Gilberto R De Queiroz. 2016. A time-weighted dynamic time warping method for land-use and land-cover mapping. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing 9, 8 (2016), 3729\u20133739.","journal-title":"IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2009 SIAM international conference on data mining. SIAM, 473\u2013484","author":"Mueen Abdullah","year":"2009","unstructured":"Abdullah Mueen, Eamonn Keogh, Qiang Zhu, Sydney Cash, and Brandon Westover. 2009. Exact discovery of time series motifs. In Proceedings of the 2009 SIAM international conference on data mining. SIAM, 473\u2013484."},{"key":"e_1_2_1_22_1","volume-title":"New Frontiers in Applied Data Mining: PAKDD 2009 International Workshops","author":"Niennattrakul Vit","year":"2010","unstructured":"Vit Niennattrakul, Dechawut Wanichsan, and Chotirat Ann Ratanamahatana. 2010. Accurate subsequence matching on data stream under time warping distance. In New Frontiers in Applied Data Mining: PAKDD 2009 International Workshops, Bangkok, Thailand, April 27\u201330, 2009. Revised Selected Papers 13. Springer, 156\u2013167."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 262\u2013270","author":"Rakthanmanon Thanawin","year":"2012","unstructured":"Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. 2012. Searching and mining trillions of time series subsequences under dynamic time warping. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 262\u2013270."},{"key":"e_1_2_1_24_1","volume-title":"Addressing big data time series: Mining trillions of time series subsequences under dynamic time warping. ACM Transactions on Knowledge Discovery from Data (TKDD) 7, 3","author":"Rakthanmanon Thanawin","year":"2013","unstructured":"Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. 2013. Addressing big data time series: Mining trillions of time series subsequences under dynamic time warping. ACM Transactions on Knowledge Discovery from Data (TKDD) 7, 3 (2013), 1\u201331."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2005 SIAM international conference on data mining. SIAM, 506\u2013510","author":"Ratanamahatana Chotirat Ann","year":"2005","unstructured":"Chotirat Ann Ratanamahatana and Eamonn Keogh. 2005. Three myths about dynamic time warping data mining. In Proceedings of the 2005 SIAM international conference on data mining. SIAM, 506\u2013510."},{"key":"e_1_2_1_26_1","volume-title":"Dynamic programming algorithm optimization for spoken word recognition","author":"Sakoe Hiroaki","year":"1978","unstructured":"Hiroaki Sakoe and Seibi Chiba. 1978. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing 26, 1 (1978), 43\u201349."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1007\/s10618-018-0557-y","article-title":"Speeding up similarity search under dynamic time warping by pruning unpromising alignments","volume":"32","author":"Silva Diego F","year":"2018","unstructured":"Diego F Silva, Rafael Giusti, Eamonn Keogh, and Gustavo EAPA Batista. 2018. Speeding up similarity search under dynamic time warping by pruning unpromising alignments. Data Mining and Knowledge Discovery 32 (2018), 988\u20131016.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"e_1_2_1_28_1","volume-title":"Healthcare","volume":"8","author":"St\u00fcbinger Johannes","year":"2020","unstructured":"Johannes St\u00fcbinger and Lucas Schneider. 2020. Epidemiology of coronavirus COVID-19: Forecasting the future incidence in different countries. In Healthcare, Vol. 8. MDPI, 99."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2019 SIAM International Conference on Data Mining. SIAM, 522\u2013530","author":"Tan Chang Wei","year":"2019","unstructured":"Chang Wei Tan, Fran\u00e7ois Petitjean, and Geoffrey I Webb. 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, 522\u2013530."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Charles Van Loan. 1992. Computational frameworks for the fast Fourier transform. SIAM.","DOI":"10.1137\/1.9781611970999"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.107895"},{"key":"e_1_2_1_32_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 866\u2013877","author":"Wu Jiaye","year":"2019","unstructured":"Jiaye Wu, Peng Wang, Ningting Pan, Chen Wang, Wei Wang, and Jianmin Wang. 2019. Kv-match: A subsequence matching approach supporting normalization and time warping. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 866\u2013877."},{"key":"e_1_2_1_33_1","volume-title":"2017 IEEE international conference on data mining (ICDM). IEEE, 565\u2013574","author":"Michael Yeh Chin-Chia","year":"2017","unstructured":"Chin-Chia Michael Yeh, Nickolas Kavantzas, and Eamonn Keogh. 2017. Matrix profile VI: Meaningful multidimensional motif discovery. In 2017 IEEE international conference on data mining (ICDM). IEEE, 565\u2013574."},{"key":"e_1_2_1_34_1","volume-title":"2016 IEEE 16th international conference on data mining (ICDM). Ieee, 1317\u20131322","author":"Michael Yeh Chin-Chia","year":"2016","unstructured":"Chin-Chia Michael Yeh, Yan Zhu, Liudmila Ulanova, Nurjahan Begum, Yifei Ding, Hoang Anh Dau, Diego Furtado Silva, Abdullah Mueen, and Eamonn Keogh. 2016. Matrix profile I: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets. In 2016 IEEE 16th international conference on data mining (ICDM). Ieee, 1317\u20131322."},{"key":"e_1_2_1_35_1","volume-title":"MASS: distance profile of a query over a time series. Data Mining and Knowledge Discovery","author":"Zhong Sheng","year":"2024","unstructured":"Sheng Zhong and Abdullah Mueen. 2024. MASS: distance profile of a query over a time series. Data Mining and Knowledge Discovery (2024), 1\u201327."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2003 ACM SIGMOD international conference on Management of data. 181\u2013192","author":"Zhu Yunyue","year":"2003","unstructured":"Yunyue Zhu and Dennis Shasha. 2003. Warping indexes with envelope transforms for query by humming. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data. 181\u2013192."},{"key":"e_1_2_1_37_1","volume-title":"2016 IEEE 16th international conference on data mining (ICDM). IEEE, 739\u2013748","author":"Zhu Yan","year":"2016","unstructured":"Yan Zhu, Zachary Zimmerman, Nader Shakibay Senobari, Chin-Chia Michael Yeh, Gareth Funning, Abdullah Mueen, Philip Brisk, and Eamonn Keogh. 2016. Matrix profile ii: Exploiting a novel algorithm and gpus to break the one hundred million barrier for time series motifs and joins. In 2016 IEEE 16th international conference on data mining (ICDM). IEEE, 739\u2013748."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:55:27Z","timestamp":1756994127000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748220"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748220","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}