基于Map/Reduce的时间序列相似性搜索算法  

Time series similarity searching algorithm based on Map / Reduce

作　　者：王会青[1] 孙宏伟[1] 张建辉[1] 

机构地区：[1]太原理工大学计算机科学与技术学院,山西太原030024

出　　处：《山东大学学报（工学版）》2016年第1期15-21,共7页Journal of Shandong University（Engineering Science）

基　　金：国家自然科学基金青年科学基金资助项目(61402318);高等学校博士学科点专项科研基金资助项目(20131402120009);山西省科技攻关资助项目(20130313012-2);太原理工大学校青年团队资助项目(2013T049)

摘　　要：将并行计算的策略引入到时间序列处理中,提出基于Map/Reduce的时间序列相似性搜索算法,充分利用云计算可进行大规模计算和数据处理的特点,有效降低了时间序列相似性搜索中运算量,简化了计算过程。该算法在心电图数据集上进行相似性搜索,分别进行PAA下界过滤和DTW距离的计算,验证运算时间和并行加速比随节点变化的情况,与传统的单机运算相比,有效地提高了时间序列挖掘效率。The strategy of parallel computing was introduced into time series processing,and time series similarity searching algorithm based on Map / Reduce was proposed. The proposed algorithm could make use of the features of cloud computing to take large-scale computing and data processing,and could efficiently reduce the large calculation and simplify the computing process of time series similarity searching. The proposed algorithm was adopted on electrocardiograph dataset to complete similarity searching with piecewise aggregate approximation lower bound and dynamic time warping distance,which verified the effect of nodes changing on operation time and parallel speed up. Compared with the traditional one running on single PC,the proposed algorithm improved the efficiency of time series mining effectively.

关 键 词：并行计算 时间序列挖掘 相似性搜索 动态时间弯曲距离 下界算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]