随着信息技术的不断发展,各个行业的数据量都开始呈现出一个增长的趋势,而“大数据”这一概念也成为了时下一个非常火热的话题。时间序列作为数据中常见的一个种类,数据量同样也在不断快速增长,因此对于时间序列的处理也变得越来越占用资源。在面向时间序列的研究中,时间序列的相似性是一个非常基础同时也是非常重要的科研方向。由于传统常用的计算时间序列相似性的算法复杂度过高,长序列的相似性计算经常会遇到计算资源不足的情况。因此降低计算相似性算法的复杂性或计算资源,是时间序列研究的一个重要研究方向。本文以DTW(Dynamic Time Warping)算法为基础,从时间资源与空间资源两个方面对时间序列的全序列匹配问题和子序列匹配问题进行改进,主要完成了以下三点工作:1.改进时间序列局部相似检测算法。针对时间序列局部相似检测时的时间复杂度与空间复杂度过高的问题,提出了适用于MapReduce框架下的路径分割与拼接方式,在保证算法精确度的前提下,降低了算法的空间资源占用与运行时间消耗。本工作的创新部分在于对序列进行分割计算路径后,提出了对路径进行拼接的算法,将复杂的计算分摊到分布式集群各个节点中,不仅减少了算法运行的时间,而且将单机无法提供的海量内存需求分布到各个节点,充分解决长序列寻找局部相似时遇到的时间与空间的问题。2.改进DTW回溯路径算法,提出线性空间复杂度动态规划算法,将原DTW算法在计算回溯路径所需O(MN)的空间减少到O(N)空间,其中M,N分别是两条参与计算的时间序列长度。本工作借鉴了 Hirschberg算法,提出了 DC-DTW算法,解决了 Hirschberg算法使用在时间序列上结果不精确的问题。DC-DTW通过迭代计算的方式,将DTW算法的空间复杂度降低为线性,并且能够精确地计算出DTW距离以及相应的回溯路径。3.在线性空间复杂度动态规划算法工作基础上,提出一种分布式长时间序列相似性搜索应用框架。该应用框架通过下界距离计算过滤了不相似的时间序列对,然后再计算DTW距离,降低了相似性搜索时所需的时间与空间资源。首先,应用分布式框架计算下界距离,并应用DTW下界距离将相似的时间序列对作为候选序列对筛选出来,再与线性空间复杂度动态规划算法计算相结合,计算候选序列对之间的DTW距离。以上计算均在MapReduce框架中进行,并已经完全实现。