支持均匀缩放的不等长时间子序列查询方法

doi:10.19678/j.issn.1000-3428.0066632

摘要/Abstract

摘要：

作为时序数据分析中的基础技术之一，时间序列的子序列查询旨在寻找与目标序列相似的子序列。现有的子序列查询方法大多仅支持查询与目标序列长度相同的子序列，因而均匀缩放技术常被用于解决子序列查询中的不等长问题。但现有支持均匀缩放的子序列查询技术大多未考虑子序列的Z-标准化，且对查询效率仍有改善的空间。针对该问题，提出一种基于索引技术且支持均匀缩放的子序列查询方法。结合现有索引方法ULISSE提供的树状数据结构，设计可保证非漏报的下界距离，为索引结构的剪枝提供理论保证，并利用索引中存储的元数据，提出精确K-近邻查询算法。所提方法适用于非归一化和归一化两种场景。实验结果表明，较UCR-US和ULISSE基线方法，该基于索引的不等长子序列查询方法在CAP、GAP两个真实数据集以及随机游走人工合成数据集上均实现了查询效率的显著提升，针对在非归一化和归一化两种场景下的不等长子序列查询，该方法的平均效率提升分别为2.33和2.51倍。

关键词: 时间序列, 子序列查询, 均匀缩放, 索引, 下界距离, K-近邻

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.

Key words: time series, subsequence query, uniform scaling, index, lower bound distance, K-Nearest Neighbor(K-NN)

熊浩然, 何震瀛. 支持均匀缩放的不等长时间子序列查询方法[J]. 计算机工程, 2024, 50(1): 60-67.

Haoran XIONG, Zhenying HE. Variable-Length Time Series Subsequence Query Method Supporting Uniform Scaling[J]. Computer Engineering, 2024, 50(1): 60-67.

https://www.ecice06.com/CN/Y2024/V50/I1/60

图/表 5

图1 闭包构建过程

Fig.1 Construction of the envelope

图2 下界距离

$ {\boldsymbol{D}}_{\mathbf{u}\mathbf{s}}^{\mathbf{l}\mathbf{b}} $

Fig.2 Lower bound distance

$ {\boldsymbol{D}}_{\mathbf{u}\mathbf{s}}^{\mathbf{l}\mathbf{b}} $

图3 查询上下界及

$ {\boldsymbol{D}}_{\mathbf{n}\mathbf{e}\mathbf{w}}^{\mathbf{l}\mathbf{b}} $

Fig.3 Lower and upper bounds of query and

$ {\boldsymbol{D}}_{\mathbf{n}\mathbf{e}\mathbf{w}}^{\mathbf{l}\mathbf{b}} $

图4 最近邻查询效率

Fig.4 Efficiency of 1-NN query

图5 GAP数据集上的K-近邻查询效率

Fig.5 Efficiency of K-NN query on GAP dataset

参考文献 26

1	RAZA U, CAMERRA A, MURPHY A L, et al. Practical data prediction for real-world wireless sensor networks. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8): 2231- 2244. doi: 10.1109/TKDE.2015.2411594
2	PALPANAS T. Data series management: the road to big sequence analytics. ACM SIGMOD Record, 2015, 44(2): 47- 52. doi: 10.1145/2814710.2814719
3	SHASHA D. Tuning time series queries in finance: case studies and recommendations. IEEE Data Engineering Bulletin, 1999, 22(2): 40- 46.
4	ECHIHABI K, ZOUMPATIANOS K, PALPANAS T, et al. Return of the Lernaean Hydra: experimental evaluation of data series approximate similarity search. Proceedings of the VLDB Endowment, 2019, 13(3): 403- 420. doi: 10.14778/3368289.3368303
5	李敏, 于长永, 张峰, 等. 基于LSH的时间序列DTW相似性查询. 小型微型计算机系统, 2019, 40(10): 2155- 2159. doi: 10.3969/j.issn.1000-1220.2019.10.024
	LI M, YU C Y, ZHANG F, et al. LSH and DTW-based for searching similar time series. Journal of Chinese Computer Systems, 2019, 40(10): 2155- 2159. doi: 10.3969/j.issn.1000-1220.2019.10.024
6	PAPARRIZOS J, LIU C W, ELMORE A J, et al. Debunking four long-standing misconceptions of time-series distance measures[C]//Proceedings of 2020 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2020: 1887-1905.
7	WU J, WANG P, PAN N, et al. KV-match: a subsequence matching approach supporting normalization and time warping[C]//Proceedings of the 35th International Conference on Data Engineering. Washington D. C., USA: IEEE Press, 2019: 866-877.
8	LINARDI M, PALPANAS T. Scalable, variable-length similarity search in data series: the ULISSE approach. Proceedings of the VLDB Endowment, 2018, 11(13): 2236- 2248.
9	LINARDI M, PALPANAS T. Scalable data series subsequence matching with ULISSE. The VLDB Journal, 2020, 29(6): 1449- 1474.
10	KEOGH E, PALPANAS T, ZORDAN V B, et al. Indexing large human-motion databases[C]//Proceedings of the 30th International Conference on Very Large Data Bases. New York, USA: ACM Press, 2014: 780-791.
11	RAKTHANMANON T, CAMPANA B, MUEEN A, et al. Addressing big data time series: mining trillions of time series subsequences under dynamic time warping. ACM Transactions on Knowledge Discovery from Data, 2013, 7(3): 1- 31.
12	SHEN Y, CHEN Y, KEOGH E, et al. Accelerating time series searching with large uniform scaling[C]//Proceedings of 2018 SIAM International Conference on Data Mining. Philadelphia, USA: Society for Industrial and Applied Mathematics, 2018: 234-242.
13	DANNENBERG R B, BIRMINGHAM W P, TZANETAKIS G P, et al. The MUSART testbed for query-by-humming evaluation. Computer Music Journal, 2004, 28(2): 34- 48.
14	LI Y, WANG T S, SHUM H Y. Motion texture: a two-level statistical model for character motion synthesis[C]//Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press, 2002: 465-472.
15	ROSE C, GUENTER B, BODENHEIMER B, et al. Efficient generation of motion transitions using spacetime constraints[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press, 1996: 147-154.
16	WAIYAWUTH E, RATANAMAHATANA C A. Efficient multimedia time series data retrieval under uniform scaling and normalization[C]//Proceedings of the 30th European Conference on IR Research. Washington D. C., USA: IEEE Press, 2008: 506-513.
17	FU A W C, KEOGH E, LAU L Y H, et al. Scaling and time warping in time series querying. The VLDB Journal, 2008, 17(4): 899- 921.
18	LINARDI M, ZHU Y, PALPANAS T, et al. Matrix profile X: VALMOD-scalable discovery of variable-length motifs in data series[C]//Proceedings of 2018 International Conference on Management of Data. New York, USA: ACM Press, 2018: 1053-1066.
19	KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 2001, 3(3): 263- 286.
20	YI B K, FALOUTSOS C. Fast time sequence indexing for arbitrary Lp norms[C]//Proceedings of the 26th International Conference on VLDB. New York, USA: ACM Press, 2000: 385-394.
21	LIN J, KEOGH E, LONARDI S, et al. A symbolic representation of time series, with implications for streaming algorithms[C]//Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. New York, USA: ACM Press, 2003: 2-11.
22	SHIEH J, KEOGH E. iSAX: indexing and mining terabyte sized time series[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2008: 623-631.
23	LIN J, KEOGH E, WEI L, et al. Experiencing SAX: a novel symbolic representation of time series. Data Mining and Knowledge Discovery, 2007, 15(2): 107- 144.
24	RAKTHANMANON T, CAMPANA B, MUEEN A, et al. Searching and mining trillions of time series subsequences under dynamic time warping[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2012: 262-270.
25	ASUNCION A, NEWMAN D. UCI machine learning repository[EB/OL]. [2022-08-31]. https://archive.ics.uci.edu/ml/index.php.
26	TERZANO M G, PARRINO L, SMERIERI A, et al. Atlas, rules, and recording techniques for the scoring of Cyclic Alternating Pattern(CAP) in human sleep. Sleep Medicine, 2002, 3(2): 187- 199.

[1]	李俊俊, 董建刚, 李坤. 基于Kubernetes的集群节能策略研究[J]. 计算机工程, 2024, 50(9): 82-91.
[2]	王汝英, 马嘉骏, 董建强, 刘万龙, 张海涛, 尹凯, 赵博超. 基于MTS-BiGRU-DMHSA的工业负荷预测方法[J]. 计算机工程, 2024, 50(9): 169-178.
[3]	严银凯, 彭宁宁, 易丽莎. 基于持续同调的倾斜时间序列分类算法[J]. 计算机工程, 2024, 50(6): 110-123.
[4]	丁国辉, 刘宇琪, 王言开, 耿施展, 姜天昊. 基于翻转网络的低相关性序列数据预测研究[J]. 计算机工程, 2024, 50(2): 78-90.
[5]	艾青松, 张皓喆, 严俊伟. 基于自适应伽马校正的异常驾驶行为检测方法[J]. 计算机工程, 2023, 49(9): 279-286.
[6]	韩璐, 霍纬纲, 张永会, 刘涛. 基于多尺度特征融合与双注意力机制的多元时间序列预测[J]. 计算机工程, 2023, 49(9): 99-108.
[7]	汤卫芬, 高翠芳. 极值点自适应加权的动态时间规整算法[J]. 计算机工程, 2023, 49(7): 150-160.
[8]	蔡瑞初, 伍运金, 陈薇, 郝志峰. 面向多元时间序列的群体因果关系发现算法[J]. 计算机工程, 2023, 49(2): 127-135.
[9]	高峰, 李秋, 顾进广. 基于图结构特征采样数据摘要的联邦知识图谱查询[J]. 计算机工程, 2023, 49(1): 73-81.
[10]	刘杭, 殷歆, 陈杰, 罗恒. 基于混合网络模型的多维时间序列预测[J]. 计算机工程, 2023, 49(1): 121-129.
[11]	李海林, 夏燕燕, 邹金串. 基于CPET时序聚类的中长跑耐力运动员选拔方法[J]. 计算机工程, 2022, 48(9): 262-268.
[12]	梁小慧, 郭晟楠, 万怀宇. 基于自适应小波分解的时间序列分类方法[J]. 计算机工程, 2022, 48(4): 81-88,98.
[13]	李晓, 卢先领. 基于双重注意力机制和GRU网络的短期负荷预测模型[J]. 计算机工程, 2022, 48(2): 291-296,305.
[14]	陆怡, 王鹏, 汪卫. 基于子序列相似性的时间序列语义挖掘算法[J]. 计算机工程, 2022, 48(10): 88-94.
[15]	白梅, 苌仕涵, 王习特. 基于位置的路网Skyline查询处理研究[J]. 计算机工程, 2022, 48(1): 127-134.

选择文件类型/文献管理软件名称

选择包含的内容