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

作者：熊浩然; 何震瀛

来源：计算机工程, 2023, 1-10.

DOI：10.19678/j.issn.1000-3428.0066632

• 时间序列
• 子序列匹配
• 均匀缩放
• 索引
• 下界距离
• K-近邻

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

• 单位
  复旦大学