MapReduce并行加速数据流多模式相似性搜索

Accelerating parallel searching similar multiple patterns from data streams by using MapReduce

设计时间序列数据在Hadoop分布式文件系统(HDFS)中的有效存储方式,利用分布式缓存工具Distributed Cache将各子序列分发到Hadoop集群的计算节点上,将动态时间弯曲距离矩阵划分成多个子矩阵,采取并行迭代计算每条反对角线上子矩阵的方法,基于MapReduce编程模型,实现高效并行计算时间序列动态弯曲距离,通过改进剪裁冗余计算方法,设计实现一种数据流多模式相似性搜索并行算法。中国雪深长时间序列数据集的实验结果表明,当每条时间序列的长度达到5 000以上时,并行计算动态弯曲距离所需时间少于串行计算所需时间,当每条时间序列的长度达到9 000以上时,参与计算的集群节点越多,并行计算所需时间越少;当模式长度达到4 000、参与计算的集群节点数达5个以上时,从数据流中并行搜索出与模式匹配的相似子序列所需时间约为串行搜索所需时间的20%。

The effective storage mode for time series was designed on Hadoop Distributed File System （ HDFS）, the sub- series were distributed to the compute nodes on Hadoop cluster by applying Distributed Cache tool, and the matrix of dynamic time warping distances was partitioned into several sub-matrixes. Based on MapReduce programming mode, by parallel computing sub-matrixes in each back-diagonal iteratively, the parallel computation of dynamic time warping distances was implemented, and an efficient parallel algorithm for searching similar patterns from data streams was developed by improving pruning redundant computation. The experimental results on the data set of snow depth long time series in China show that when the length of each time series is equal to or longer than 5 000, the required time of parallel computing dynamic time warping distances is less than that of the corresponding sequential computation, and when the length of each time series is equal to or longer than 9000, the more the compute nodes used, the less the required parallel computation time; furthermore, when the length of each pattern is equal to or longer than 4000 and the number of compute nodes is equal to or larger than 5, the required time of parallel searching similar sub-series from data streams is 20% of the corresponding sequential searching time.