计算机工程

作者：熊浩然, 何震瀛

单位：1. 复旦大学软件学院, 上海 2004332. 复旦大学计算机科学技术学院, 上海 200433

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

基金：国家重点研发计划(2021YFB3300502)

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

来源：2024年第1期

《计算机工程》期刊编辑部

查看计算机工程杂志2024年第1期