计算机工程2024，Vol.50Issue(1)：60-67,8.DOI:10.19678/j.issn.1000-3428.0066632
支持均匀缩放的不等长时间子序列查询方法
Variable-Length Time Series Subsequence Query Method Supporting Uniform Scaling
摘要
Abstract
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.关键词
时间序列/子序列查询/均匀缩放/索引/下界距离/K-近邻Key words
time series/subsequence query/uniform scaling/index/lower bound distance/K-Nearest Neighbor(K-NN)分类
信息技术与安全科学引用本文复制引用
熊浩然,何震瀛..支持均匀缩放的不等长时间子序列查询方法[J].计算机工程,2024,50(1):60-67,8.基金项目
国家重点研发计划(2021YFB3300502). （2021YFB3300502）
