FSMDTW: A Fast Index-free Subsequence Matching Algorithm for Dynamic Time Warping

Download PDF

Abstract

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 𝑂 ( 𝑚 ) time for each candidate, where 𝑚 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 𝑂 ( log 𝑚 ) 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.