基于LSH的时间序列DTW相似性查询

摘要

提出了一种新颖的基于LSH的时间序列DTW相似性近似查询算法,较好地解决了DTW相似性查询速度慢的问题.首先,分析了DTW相似性度量的特点,即时间弯曲的重要特性;其次,将该特性与LSH函数相结合,设计了高效的DTW相似时间序列过滤方法.在很大概率程度上保证了相似的时间序列至少具有一个相同的LSH函数值;最后,给出了一个基于过滤加验证框架的时间序列DTW相似性近似查询算法,该算法利用低维的Hash索引加快候选集合的筛选,从而加快查询速度.实验结果表明,在保持较好的召回率的情况下,本文提出的方法较现有算法有效地提高了DTW相似性查询速度.