论文：CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series
会议：VLDB 2024
作者：Haoran Xiong, Hang Zhang, Zeyu Wang, Zhenying He, Peng Wang, X. Sean Wang
简介：时间序列数据广泛存在，对该类数据的管理和分析也愈发重要。作为时间序列分析的核心步骤，子序列匹配的相关研究备受关注。然而，大多数以往的研究仅关注于与查询序列长度相同的子序列匹配（fixed-length subsequence matching），因此我们聚焦于不等长子序列匹配问题（variable-length subsequence matching）。在可变长度情况下，查询涉及的搜索空间更大，且距离计算更为复杂和耗时。
针对这些问题，本工作设计了一个高效的索引和查询算法，以避免不必要的计算，该方法称为CIVET。首先，我们提出了一种新的子序列表征方法——均匀分段聚合近似（Uniform Piecewise Aggregate Approximation, UPAA），该表征具有对不同长度时间序列进行特征对齐能力，且保有下界性质。继而基于UPAA，我们通过分别对相邻子序列和相似子序列进行分组，提出了一种iSAX结构的紧凑索引。此外，我们还提出了一套索引剪枝和数据过滤算法，以实现高效的不等长时间子序列匹配，且能支持近似查询和精确查询两种需求。在多个数据集的实验结果表明，本方法在查询效率、可扩展性和有效性方面均优于现有方法。
