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

摘要：

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

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

所属期刊栏目：50

分类号：TP39(计算技术、计算机技术)

资助基金：中国工业和信息化部“核高基”重大专项基金资助项目2010ZX01042-002-003-001;中国工程科技知识中心基金资助项目CKCEST2014-1-5;国家自然科学基金资助项目61332017

在线出版日期：2016-10-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1290-1297,1321