ICDM——Time Series Join on Subsequence Correlation

将两个时间序列在他们相关的片段上进行合并,可以挖掘出有效的信息。两个时间序列的合并可以发生在任意位置及任意长度。由于时间序列的长度通常很长,因此关联合并通常要消耗大量时间,最简单的算法的时间复杂度为O(n^4)。本文致力于改进这一时间复杂度。

在最简单的算法中,每次从一个位置进行匹配,若是该位置没有找到相关度较好的片段,则从下一个位置继续进行匹配。作者采用了一种类似于KMP算法的思想。即每次不是从紧接着的一个位置重新匹配,而是重复利用上一次匹配的信息,进行跳跃匹配。该算法的时间复杂度仍然较高,作者在此基础上,进一步提出了一个近似算法,每次选择要匹配的序列片段时,也进行跳跃选择,如何可大大加快速度。作者进一步使用了GPU来加速了该算法。

本文的算法思想与KMP算法具有很大的相似性,均是重复利用已经计算的信息,这是一种可以应用到各问题求解中的思想。

anyShare分享到:
This entry was posted in 新闻动态. Bookmark the permalink.

发表评论