MapReduce并行加速數據流多模式相似性搜索

付 晨，鐘 誠，葉 波

(1.廣西大學 計算機與電子信息學院，南寧 530004； 2.廣西科技信息網絡中心，南寧 530012)

(*通信作者電子郵箱chzhong@gxu.edu.cn)

MapReduce并行加速數據流多模式相似性搜索

付 晨1，鐘 誠1*，葉 波2

(1.廣西大學 計算機與電子信息學院，南寧 530004； 2.廣西科技信息網絡中心，南寧 530012)

(*通信作者電子郵箱chzhong@gxu.edu.cn)

設計時間序列數據在Hadoop分布式文件系統(HDFS)中的有效存儲方式，利用分布式緩存工具Distributed Cache將各子序列分發到Hadoop集群的計算節點上，將動態時間彎曲距離矩陣劃分成多個子矩陣，采取并行迭代計算每條反對角線上子矩陣的方法，基于MapReduce編程模型，實現高效并行計算時間序列動態彎曲距離，通過改進剪裁冗余計算方法，設計實現一種數據流多模式相似性搜索并行算法。中國雪深長時間序列數據集的實驗結果表明，當每條時間序列的長度達到5 000以上時，并行計算動態彎曲距離所需時間少于串行計算所需時間，當每條時間序列的長度達到9 000以上時，參與計算的集群節點越多，并行計算所需時間越少；當模式長度達到4 000、參與計算的集群節點數達5個以上時，從數據流中并行搜索出與模式匹配的相似子序列所需時間約為串行搜索所需時間的20%。

時間序列；數據流；動態時間彎曲距離；模式搜索；Hadoop

0 引言

時間序列數據流相似性搜索在網絡點擊流分析、金融分析、氣象監測、語音識別等諸多領域具有廣泛的應用[1]。大數據環境下長時間序列數據流多模式相似性搜索十分耗時。因此，在分布式并行計算Hadoop平臺上，研究設計實現高效的數據流多模式相似性搜索并行算法具有重要應用價值。

歐氏距離及其擴展的相似性度量方法針對時間序列在時間軸上拉伸、收縮、平移等變形的健壯性不強[2]。動態時間彎曲(Dynamic Time Warping, DTW)距離[3]能夠度量不同步不等長的時間序列，使它們通過一定的變形進行比較，適合于時間序列相似性比較。文獻[4]利用MPI(Message Passing Interface)和Open MP機制，采取均勻劃分數據分配方法，設計機群計算時間序列動態彎曲距離的并行算法，獲得了較好的加速。文獻[5]針對無線傳感器網絡環境下不確定異常時間序列檢測效率低下的問題，對不確定時間序列進行壓縮變換，以減少不確定數據量，利用MapReduce架構實現基于期望距離的不確定時間序列動態彎曲距離算法并行化,同時提出了基于顯著特征匹配的局部約束算法,對彎曲路徑進行局部限制，提高了檢測效率。文獻[6]提出一種判斷累加距離是否超出閾值的推算方法，以減少一些不必要的冗余計算。文獻[7]利用值域劃分柱圖，將時間序列映射到k維空間，構造新的距離函數，獲得動態時間彎曲距離的新的上、下界，從而縮小原始候選集，使算法僅需在小規模候選集上計算DTW距離，降低了計算復雜度。時間序列動態彎曲距離的一個重要應用是被用來搜索數據流中的相似模式。通過保存時間序列累計距離和候選序列的起始點，采取計算時間子序列匹配矩陣的方法，文獻[8]的SPRING算法解決了針對數據流連續、實時、無限制等特性的時間序列的子序列匹配問題，但該算法存在冗余計算。文獻[9]構造一個計分函數來降低動態時間彎曲距離的計算量，然后利用得到的時間彎曲距離來搜索發現數據流中公共的局部相似模式。

本文基于Hadoop平臺，通過設計時間序列數據在HDFS中的有效存儲方式和改進剪裁減少冗余計算方法，采取MapReduce并行迭代計算每條反對角線上動態時間彎曲距離子矩陣的方法，設計實現高效的數據流多模式相似性搜索并行算法，在獲得較好匹配效果的同時，大大縮短計算時間。

1 MapReduce并行計算動態時間彎曲距離

1.1 遞推計算動態時間彎曲距離

采用遞推方法計算時間序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}之間的動態彎曲距離矩陣D(X,Y)[9]：

(1)

其中c=min{d(i,j-1),d(i-1,j),d(i-1,j-1)},i=1,2,…,m,j=1,2，…,n。從動態時間彎曲距離矩陣中可以尋找出彎曲路徑DTW(X,Y)={w1,w2,…,wk}，從而得到X和Y之間的匹配關系。

1.2 數據存儲與算法設計

1.2.1 算法設計

采用MapReduce編程模型可有效處理大規模科學計算問題[10]。為了在Hadoop平臺上實現并行計算動態時間彎曲距離矩陣，將序列X劃分為長度分別為「m/p?的p個子序列X0,X1,…,Xp-1，并將序列Y劃分為長度分別為「n/q?的q個子序列Y0,Y1,…,Yq-1。利用Hadoop分布式緩存工具Distributed Cache將各子序列分發到Hadoop集群計算節點上，于是構造p×q個子矩陣D(f,g)，f=1,2,…,p，g=1,2,…,q，每個子矩陣規模為「m/p?×「n/q?，這些子矩陣D(f,g)可以并行計算[11]。

算法1描述了Hadoop平臺上并行計算動態時間彎曲距離(ParallelComputingDistancesofTimeWinding,PCDTW)算法。

算法1PCDTW算法。

輸入：時間序列X和Y。 輸出：動態時間彎曲距離矩陣D。Begin1) 計算子矩陣D(1,1)，將其最后一行和最后一列存入HDFS中； 2) 讀取HDFS中D(1,1)最后一行，存入D(2,1)的第0行，用于D(2,1)的計算；讀取HDFS中D(1,1)最后一列，存入D(1,2)的第0列，用于D(1,2)的計算；將D(2,1)的最后一行與D(1,2)的最后一列存儲到HDFS中； 3) 獲取子矩陣D(2,1)的最后一行，存入D(3,1)的第0行；獲取D(1,2)的最后一行及D(2,1)的最后一列，分別存入D(2,2)的第0行和第0列；獲取D(1,2)的最后一列，存入D(1,3)的第0列；并行計算D(3,1)、D(2,2)和D(1,3)； 4) 依此類推，獲取子矩陣D(f-1,g)的最后一行及D(f,g-1)的最后一列，存入D(f,g)的第0行和第0列，計算D(f,g)，將D(f,g)的最后一行傳送給D(f+1,g)計算，將D(f,g)的最后一列傳送給D(f,g+1)計算；并行計算每條反對角線上的子矩陣，每次Map/Reduce過程完成計算一條反對角線上的子矩陣； 5) 若距離累加超過事先設定的閾值，則算法結束；否則迭代k=p+q-1次，并行計算D(f,g);End

1.2.2 動態時間彎曲距離矩陣數據存儲設計

HDFS文件中每一行存儲動態時間彎曲距離子矩陣中每個元素的信息，子矩陣信息用坐標(子矩陣分塊行號，子矩陣分塊列號)表示，元素信息包括(行號，列號#元素值)。HDFS中每一行的存儲格式為〈(子矩陣分塊行號，子矩陣分塊列號)(元素行號，元素列號#元素值)〉，即以〈(f,g)(i,j#d[i][j])〉的形式存儲，f和g代表子矩陣在動態時間彎曲距離矩陣分塊中的行、列號，i和j為子矩陣元素在子矩陣中的行、列號，d[i][j]代表元素值。

1.2.3Map過程的設計

并行計算Map階段的主要工作：從HDFS文件中逐行讀取動態時間彎曲距離矩陣數據〈(f,g)(i,j#d[i][j])〉；篩選出本次計算的子矩陣分塊坐標(f,g)，獲取子矩陣的第0行元素和第0列元素。

如果上一輪迭代計算有相關子矩陣傳遞最后一行記錄數據，那么本次計算的子矩陣用第0行接收。如果上一輪迭代計算有相關子矩陣傳遞最后一列記錄數據，那么本次計算的子矩陣用第0列接收。

算法2 并行計算DTW距離的Map函數。

輸入：〈key1,value1〉為〈行號，HDFS中每一行記錄〉。 輸出：中間結果〈key2,value2〉。Begin1) 逐行讀取HDFS文件，獲取子矩陣中每個元素信息〈(f,g)(i,j#d[i][j])〉: ①key1←行號； ②value1←〈(f,g)(i,j#d[i][j])〉。 2) 篩選出本輪迭代計算的子矩陣分塊坐標(f,g)，記錄其第0行和第0列信息； 3) 將中間結果〈key2,value2〉寫入本地節點的中間文件： ①key2←(f,g)；value2←(0,j#d[0][j])； 將中間結果〈key2,value2〉以“〈(子矩陣分塊行號，子矩陣分塊列號)(第0行，元素列號#元素值)〉”的形式(即〈(f,g)(0,j#d[0][j])〉)寫入本地中間文件； ②key2←(f,g)；value2←(i,0#d[i][0])； 將中間結果〈key2,value2〉以“〈(子矩陣分塊行號，子矩陣分塊列號)(元素行號，第0列#元素值)〉”的形式(即〈(f,g)(i,0#d[i][0])〉)寫入中間文件；End

算法2中步驟3)的中間結果key2值為本次計算的子矩陣坐標(f,g)，相應的value2值為本次計算子矩陣第0行每個元素信息(0，j#d[0][j])或者第0列元素的信息(i,0#d[i][0])。通過算法2可篩選本次計算的子矩陣分塊坐標(f,g)，獲取本次計算的子矩陣的第0行元素和第0列元素，并將其記錄到中間文件。

1.2.4Reduce函數的設計

并行計算Reduce階段的任務：根據輸入的鍵值對〈key2,list〈value2〉〉，接收相同key2值對應的list〈value2〉得到本次計算子矩陣第0行元素集合和第0列元素集合。提取分布式緩存中本次參與計算子序列Xf和Yg。記錄本輪迭代計算的反對角線上的各個DTW距離子矩陣，同時將子矩陣最后一行和最后一列寫到HDFS結果文件中，以傳遞給下一輪迭代計算時Map函數使用。

算法3 并行計算DTW距離的Reduce函數。

輸入：key2值為子矩陣坐標(f,g),list〈value2〉值為計算子矩陣第0行元素集合和第0列元素集合。 輸出：結果〈key3,value3〉。

Begin1)for(相同key2值(f,g)對應的list〈value2〉)dobegin2) 獲取value2，給子矩陣第0行和第0列賦值； 3) 提取分布式緩存中參與計算子矩陣D(f,g)的子序列Xf和Yg； 4) 計算并記錄子矩陣中各DTW距離d[i][j]；

5) 將〈key3,value3〉寫入HDFS的結果文件： ①key3←本輪迭代計算的子矩陣坐標(f,g)；value3←(i,j#d[i][j])；將本次計算的子矩陣結果〈key3,value3〉以“〈(子矩陣分塊行號，子矩陣分塊列號)(元素行號，元素列號#元素值)〉”的形式(即〈(f,g)(i,j#d[i][j])〉)寫入HDFS的結果文件中； ②d[c][j] ←本次計算的子矩陣最后一行元素值；key3←下輪迭代要計算的子矩陣坐標(f+1,g)；value3←(0,j#d[c][j])；將下輪迭代計算的子矩陣〈key3,value3〉以“〈(子矩陣分塊行號，子矩陣分塊列號)(第0行，元素列號#元素值)〉”的形式(即〈(f+1,g)(0,j#d[c][j])〉)寫入HDFS的結果文件中； ③d[i][c]←本次計算的子矩陣最后一列元素值；key3←下輪迭代計算的子矩陣坐標(f,g+1)；value3←(i,0#d[i][c])；將下輪迭代計算的子矩陣〈key3,value3〉以“〈(子矩陣分塊行號，子矩陣分塊列號)(元素行號，第0列#元素值)〉”的形式(即〈(f,g+1)(i,0#d[i][c])〉)寫入HDFS的結果文件中；end

End

并行計算DTW距離矩陣的主函數迭代地啟動Job調用算法2和3的Map/Reduce函數。一輪迭代過程結束則計算完成一條反對角線上的子矩陣塊，迭代次數加1，輸出路徑編號加1。算法采用MapReduce的多目錄輸出，將要傳遞的子矩陣最后一行及最后一列與本次計算的子矩陣分開不同目錄存放。僅將本次MapReduce的輸出路徑中存放子矩陣最后一行及最后一列的目錄，作為下輪迭代計算的輸入目錄，從而避免了不必要的數據復制和傳遞。在Reduce過程中，若出現DTW距離超過閾值，則算法提前結束。所有Reduce寫入的子矩陣結果集合即為最終結果的DTW距離矩陣。

2 數據流多模式相似性并行搜索

模式Q與數據流S子序列S[ts,te]之間的DTW距離為d(S[ts,te],Q)，起始點位置記為sp(t,i)[8]：

(2)

其中d(t,0)=0,d(0,i)=∞,t=1,2,…,n,i=1,2,…,m。

(3)

從式(2)可看出，若min{d(t,i-1),d(t-1,i-1),d(t-1,i)}>ε且d(t,i)≥0，則d(t,i)>ε，ε為相似性閾值。因此，可以按式(2)裁剪計算，提前排除超出閾值的子序列，以提高搜索效率。

算法4描述了Hadoop平臺上時間序列數據流多模式相似性并行搜索(Multi-PatternParallelSearchingOfDistributedStreams,MPPSODS)算法。

算法4MPPSODS算法。

輸入：數據流S，模式Q1,Q2,Q3,…。 輸出：S中與每個模式相匹配的前k條數據流子序列對應的起止點。Begin1)Map階段。將數據流分段分配到不同的Map任務中，每個任務在相應的DataNode上采用改進的SPRING算法進行相似性搜索: ①將數據流分段S1,S2,S3,…以及模式Q1,Q2,Q3,…發送到各計算節點上，Map獲取計算的數據流分段及其id號、模式及其id號; ②每個節點運行改進的SPRING算法，判斷相似性閾值是否符合提前終止的條件； ③將模式id號與每次計算得到的DTW距離連接作為中間結果〈key，value〉中的key，將匹配子序列的起始點、結束點存儲在value中。 2) 中間階段。將所有中間結果〈key，value〉經過一個名為Shuffle的過程，按key值排序并分配給對應的Reducer處理； 3) Reduce階段。輸入的〈key，list〈value〉〉已按從小到大的順序排列好，分解key中模式id與DTW距離，對于模式id相同的記錄只讀取前k條記錄作為結果輸出，同時將前k條記錄匹配的數據流子序列對應的起止點寫入文件；End

3 實驗分析

3.1 實驗數據及環境

實驗數據來源于“寒區旱區科學數據中心”(http://westdc.westgis.ac.cn)的中國雪深長時間序列數據集(1978—2012)[12-14]，將其中的時間序列文件預處理為時間序列的每個數值點占一行，以〈序號，數值〉的形式存儲。

Hadoop平臺采用通過交換機連接的6臺計算機組成分布式并行計算環境，其中每臺計算機的內存容量為2GB、處理器為IntelPentiumCPUG2020、主頻為2.90GHz，將1臺計算機的角色作為主節點(Master)、名稱節點(NameNode)和作業跟蹤節點(JobTracker)，其余5臺計算機的角色作為從節點(Slave)、數據節點(DataNode)和任務跟蹤節點(TaskTracker)，系統網絡傳輸速率為100Mb/s。Hadoop版本為hadoop-1.0.4。運行的操作系統為ubuntu-10.04.4版本。開發環境為Eclipse，采用Java語言編程實現算法。

3.2 實驗結果

首先測試并行計算動態時間彎曲距離(PCDTW)算法對運行時間改進的程度。

對于12個不同規模的數據集，當Hadoop平臺上參與計算的節點數目逐步增多時，圖1給出了PCDTW并行算法和串行算法的運行時間。

從圖1的結果可以看出，當時間序列長度小于5 000時，PCDTW并行算法的運行時間多于串行算法的運行時間，且集群中參與計算節點越多反而越耗時。這是因為對于較短的時間序列，需要計算的DTW距離矩陣也相對較小，而每次計算一條反對角線上的子矩陣，都要啟動一次Job調用Map/Reduce過程，通信交互和輸入輸出IO操作都相對耗時。

當每條時間序列的長度達到5 000以上時，在Hadoop上運行PCDTW算法的耗時低于串行算法。時間序列越長，PCDTW算法加速效果越明顯。當每條時間序列的長度達到9 000以上時，集群中參與計算的節點越多，PCDTW算法所需運行時間越少。

值得注意的是，當每條時間序列的長度達到8 000以上時,運行串行算法產生內存溢出，無法獲得計算結果。

圖1 PCDTW算法與串行算法的運行時間

對于時間序列X和Y的長度在10 000以上的數據集A、B、C、D和E，PCDTW算法計算DTW距離矩陣需要的存儲容量如表1所示。

表1 計算DTW距離矩陣需要的存儲容量

從表1可知，當時間序列較長時，計算兩序列之間的DTW距離矩陣需要較大的存儲容量。

圖2給出了Hadoop集群中參與計算的節點數目分別為2，3，4，5和6時，PCDTW算法計算數據集A、B、C、D和E的DTW距離所需的時間。

圖2 參與計算節點增多時PCDTW算法的運行時間

從圖2可以看出，當參與計算的節點數目固定時，時間序列數據集規模越大，PCDTW算法所需時間也越多；對于同一個數據集，當集群中參與計算的節點增多時，PCDTW算法所需時間逐漸減少。這表明，Hadoop平臺上并行計算時間序列DTW矩陣的PCDTW算法能夠利用集群中不斷增多的節點的計算能力。

加速比反映了算法的并行性對運行時間的改進程度。Hadoop集群中參與計算的節點數目分別為2，3，4，5和6時，PCDTW并行算法獲得的加速比如圖3所示。

圖3的結果表明，隨著時間序列的增長，PCDTW算法獲得的加速比逐漸提高。當每條時間序列長度達到7 000以上時，在Hadoop集群上運行的PCDTW算法加速更加明顯。這說明，PCDTW并行算法適用于計算時間序列長、數據集大的動態時間彎曲距離。

圖3 參與計算節點增多時PCDTW算法的加速比

為了測試數據流多模式相似性搜索并行算法MPPSODS相對于串行算法STRING運行時間的改進程度，將包含25 000個數據點的數據流劃分為5段，依次對表2中的H、I、J和K這4組模式集中每組的3個模式(查詢序列)進行并行搜索，算法所需的運行時間如圖4所示。

表2 模式(查詢序列)集及相似性閾值

圖4 MPPSODS算法與串行算法的運行時間

從圖4中可看出，隨著模式(查詢序列)中時間序列長度的增大，并行算法MPPSODS和串行算法SPRING搜索時間也隨之增長，但SPRING算法所需的運行時間增長較快，而MPPSODS算法的運行時間增長較為緩慢，且Hadoop集群中參與計算的節點越多，MPPSODS算法運行時間越少。

對于H、I、J和K這4組模式(查詢序列)，圖5給出了Hadoop集群參與計算的節點增多時，MPPSODS算法的運行時間。

圖5的結果表明，對于同一組模式(查詢序列)，隨著Hadoop集群中參與計算的節點增多，MPPSODS算法運行時間逐漸減少；而且模式越長、參與計算的節點越多，MPPSODS算法所需時間越少。這說明，MPPSODS算法有效利用了Hadoop集群中逐步增多的節點的計算能力。

圖6～8分別給出MPPSODS算法對模式(查詢序列)集H中3條序列HQ1、HQ2、HQ3進行相似性搜索得到的結果。

圖5 參與計算節點增多時MPPSODS算法的運行時間

圖6 MPPSODS算法對HQ1搜索的結果

圖7 MPPSODS算法對HQ2搜索的結果

從圖6可以看到，在數據流上搜索出與模式(查詢序列)HQ1最為匹配的數據流子序列的開始位置為6 362、結束位置為7 337、長度為986。

從圖7可以看到，在數據流上搜索出與模式(查詢序列)HQ2最為匹配的數據流子序列的開始位置為2 008、結束位置為3 001、長度為994。

從圖8可以看到，在數據流上搜索出與模式(查詢序列)HQ3最為匹配的數據流子序列的開始位置為11 455、結束位置為12 425、長度為971。

圖6～8的結果表明，MPPSODS算法并行搜索數據流得到匹配的子序列與模式(查詢序列)在形態上具有很高的相似性。

圖8 MPPSODS算法對HQ3搜索的結果

4 結語

時間序列數據流具有連續、實時和無限制特性。大數據環境下長時間序列的動態彎曲距離計算和數據流多模式相似性搜索相當耗時，并行求解算法提供了有效的解決方案。基于Hadoop平臺和MapReduce編程模型，本文設計實現的并行算法能夠利用集群中不斷增加的節點的計算能力，高效地計算動態時間彎曲距離和從數據流中搜索出與模式相似的子序列,所得到的匹配子序列與模式序列在形態上具有很高的相似性。下一步的工作將在Hadoop平臺上開發一個時間序列數據流多模式相似性并行搜索軟件包供人們在線使用。

References)

[1] MATSUBARA Y, SAKURAI Y, FALOUTSOS C, et al.Fast mining and forecasting of complex time-stamped events [C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2012: 271-279.

[2] WANG L, LEEDHAM G.Near and far infrared imaging for vein pattern biometrics [C]// Proceedings of the 2006 IEEE International Conference on Video and Signal Based Surveillance.Piscataway, NJ: IEEE, 2006: 52-52.

[3] 陳乾,胡谷雨.一種新的DTW最佳彎曲窗口學習方法[J].計算機科學,2012,39(8):191-195.(CHEN Q, HU G Y.New leaning method for optimal warping window of DTW [J].Computer Science, 2012, 39(8): 191-195.)

[4] 莫倩蕓,鐘誠.機群系統上并行計算時間序列的動態彎曲距離[J].微電子學與計算機,2008,25(10):155-158.(MO Q Y, ZHONG C.Parallel computing dynamic warping distances for time sequences on the cluster computing systems [J].Microelectronics & Computer, 2008, 25(10): 155-158.)

[5] 張建平，李斌，劉學軍，等.基于Hadoop的不確定異常時間序列檢測[J].傳感技術學報,2014,27(12):1659-1665.(ZHANG J P, LI B, LIU X J, et al.Uncertain abnormal time series detection based on Hadoop [J].Chinese Journal of Sensors and Actuators, 2014, 27(12): 1659-1665.)

[6] 沙劍.基于GPU的時間序列并行檢索算法研究[D].大連:大連理工大學,2011:42-55.(SHA J.The research on parallel time series retrieval method based on GPU [D].Dalian: Dalian University of Technology, 2011: 42-55.)[7] 歐陽一村.基于DTW距離的兩步式時間序列相似搜索[D].廣州:中山大學,2010:33-54.(OUYANG Y C.Two-step similarity search of time series based on DTW distance [D].Guangzhou: Sun Yat-sen University, 2010: 33-54.)

[8] SAKURAI Y, FALOUTSOS C, YAMAMURO M.Stream monitoring under the time warping distance [C]// Proceedings of the 23rd International Conference on Data Engineering.Piscataway, NJ: IEEE, 2007: 1046-1055.

[9] TOYODA M, SAKURAI Y, ISHIKAWA Y.Pattern discovery in data streams under the time warping distance [J].VLDB Journal, 2013, 22(3): 295-318.

[10] SRIRAMA S N, JAKOVITS P, VAINIKKO E.Adapting scientific computing problems to clouds using MapReduce [J].Future Generations Computer System, 2012, 28(1): 184-192.

[11] 鐘誠,陳國良.PRAM和LARPBS模型上的近似串匹配并行算法[J].軟件學報,2004,15(2):159-169.(ZHONG C, CHEN G L.Parallel algorithms for approximate string matching on PRAM and LARPBS [J].Journal of Software, 2004, 15(2): 159-169.)

[12] 寒區旱區科學數據中心.中國雪深長時間序列數據集(1978—2012) [EB/OL].[2014-09-28].http://westdc.westgis.ac.cn.(Cold and Arid Regions Science Data Center at Lanzhou.Snow depth long time series data set in China (1978—2012) [EB/OL].[2014-09-28].http://westdc.westgis.ac.cn.)

[13] CHE T, LI X, JIN R, et al.Snow depth derived from passive microwave remote-sensing data in China [J].Annals of Glaciology, 2008, 49(1): 145-154.

[14] DAI L, CHE T, WANG J, et al.Snow depth and snow water equivalent estimation from AMSR-E data based on a priori snow characteristics in Xinjiang, China [J].Remote Sensing of Environment, 2012, 127: 14-29.

This work is supported by the Natural Science Foundation of Guangxi (2014GXNSFAA118396).

FU Chen, born in 1988, M.S.Her research interests include network software engineering, high-performance computing for big data.

ZHONG Cheng, born in 1964, Ph.D., professor.His research interests include high-performance computing for big data, network software engineering.

YE Bo, born in 1974, Ph.D., senior engineer.His research interests include network software engineering, management information system.

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

FU Chen1, ZHONG Cheng1*, YE Bo2

(1.SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,NanningGuangxi530004,China;2.GuangxiScientificandTechnologicalInformationCenter,NanningGuangxi530012,China)

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 9 000, 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 4 000 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.

time series; data stream; dynamic time warping distance; pattern searching; Hadoop

2016-08-25;

2016-09-03。 基金項目:廣西自然科學基金資助項目(2014GXNSFAA118396)。

付晨(1988—)，女，江西瑞昌人，碩士，主要研究方向：網絡軟件工程、大數據高性能計算； 鐘誠(1964—)，男，廣西桂平人，教授，博士，CCF高級會員，主要研究方向：并行計算、大數據高性能計算、網絡軟件工程； 葉波(1974—)，男，廣西南寧人，教授級高級工程師，博士，主要研究方向：網絡軟件工程、管理信息系統。

1001-9081(2017)01-0037-05

10.11772/j.issn.1001-9081.2017.01.0037

TP338.6; TP301.6

A