蔡青林,陈　岭,梅寒蕾,孙建伶

(浙江大学 计算机科学与技术学院,浙江 杭州 310027)



基于两级过滤的时间序列近似查询

蔡青林,陈岭,梅寒蕾,孙建伶

(浙江大学 计算机科学与技术学院,浙江 杭州 310027)

摘要:针对现有的近似查询模型对查询精度的可控性较差,后续处理效率较低的问题,提出基于两级过滤的查询模型.通过采用不同粒度的SAX表示方法提取时间序列的字符型特征向量,可以将高维的时间序列映射到低维的特征空间；将不同粒度的特征向量以向量近似文件(VA-File)的结构进行存储,有效引入了倒排索引.在查询过程中,设计了启发式的查询过滤算法,根据粗粒度特征向量查询细粒度特征向量,实现第一级过滤；针对VA-File设计了高效的边界剪枝算法,实现第二级过滤.模型基于多粒度的SAX特征向量进行构建,可以对查询精度进行有效控制；在第二级过滤中采用的边界剪枝算法可以有效地提高后续处理的执行效率.实验结果表明,提出的查询模型具有较高的性能,对时间序列长度、kNN查询规模及数据集规模具有稳定的扩展性.

关键词：时间序列；相似性查询；符号聚集近似；向量近似文件；倒排索引

时间序列相似性查询是时间序列数据挖掘领域的基本问题,可简要描述为对于给定的一条时间序列,需要快速完整的从时间序列数据库中找出与其相似的序列.针对该问题,学术界提出了大量的查询模型[1],这些模型通常基于特定的数据表示……