Variable-Length Time Series Subsequence Query Method Supporting Uniform Scaling
Subsequence query,a fundamental technique in time-series data analysis,aims to find subsequences similar to the target sequence.Most existing methods for subsequence query support the query of subsequences of the same length as the target sequence.Therefore,uniform scaling is often used to address the problem of variable lengths in subsequence query.However,most existing subsequence query techniques that support uniform scaling do not consider the Z-normalization of subsequences,and the query efficiency requires improvement.To address this problem,a novel subsequence query method based on indexing techniques and supporting uniform scaling is proposed.Combined with the tree data structure provided by the existing ULISSE index method,a lower bound distance is designed to guarantee non-dismissal matching,which provides a theoretical guarantee for the pruning of the index structure.Furthermore,an exact K-Nearest Neighbor(K-NN)query algorithm is proposed using the metadata stored in the index.In addition,the entire set of methods is applicable to both nonnormalized and normalized scenarios.The experimental results show that this index-based query method achieves a significant improvement in efficiency compared with the baseline methods,UCR-US and ULISSE,on real datasets,CAP and GAP,as well as on synthetic datasets using random walking.For variable-length query in nonnormalized and normalized scenarios,the average efficiency improvement of this method is 2.33 times and 2.51 times,respectively.
time seriessubsequence queryuniform scalingindexlower bound distanceK-Nearest Neighbor(K-NN)