基于分布式架構的時間序列局部相似檢測算法

林煬+江育娥+林劼

摘 要：基于動態時間規整算法思想的CrossMatch算法可以用來解決序列間的部分相似問題，但是由于算法時間空間復雜度過高，需要消耗大量的計算資源，因此無法應用于長序列之間的計算。針對以上問題，提出了一個基于分布式平臺上的時間序列局部相似性檢測算法。將CrossMatch算法實現在了分布式框架上，解決了計算資源不足的問題。首先需要對序列進行切分，分別放置在不同的節點上；其次，各節點分別處理各自序列的相似部分；最后，通過對結果進行匯總并拼接，找出序列間的局部相似。實驗結果表明，該算法在準確性上和CrossMatch相近，在時間上也有提升。改進后的分布式算法不僅解決了單機無法處理的長序列計算問題，而且可以通過增加并行計算節點數提高運行速度。

關鍵詞：動態時間規整；MapReduce；時間序列；局部相似性；并行化

中圖分類號： TP301.6；TP311.1

文獻標志碼：A

文章編號：1001-9081（2016）12-3285-07