林煬+江育娥+林劼

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

關(guān)鍵詞：動態(tài)時間規(guī)整；MapReduce；時間序列；局部相似性；并行化

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

文獻(xiàn)標(biāo)志碼：A

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