一种基于LSH的时间子序列匹配查询算法
一种基于LSH的时间子序列匹配查询算法
(宁波大学信息科学与工程学院宁波315211)
摘 要：
提出了一种基于LSH（locality sensitive hashing，局部敏感散列）算法处理时间子序列匹配问题的方法LSHSM。不同于FRM和DualMatch方法，该方法不需要对时间序列做DFI'、DWT等特征变换，而是直接把序列看成高维数据点，利用LSH能处理高维数据的特性来查找相似时间子序列。实验采用3种不同的时间序列数据集，通过与线性扫描算法比较，验证了算法的有效性，性能有很大的提高。
关键词：时间子序列；LSH;匹配查询
结论
时间序列的相似性查询已有很长的研究历史，在子序列匹配问题中，传统基于树的方法虽然能很好地解决低维空间的问题，但当数据维度增加时，它们的效果甚至不如线性扫描算法。本文提出了用LSH技术与时间序列结合的方法，既能避免高维数据导致的维度灾难，又能保留时间序列的主要特征。利用LSH的局部敏感性，把相似的子序列聚集到一起，过滤掉很多不相似的对象，减少所需的比较次数，提高效率。实验结果表明，该方法在性能上有很大的提升。
关键字：
