[發(fā)明專利]基于低水位滑動時間窗口的離群數(shù)據(jù)發(fā)現(xiàn)方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201710284487.4
• 申請日: 2017-04-25
• 公開（公告）號: CN107124329B
• 公開（公告）日: 2020-05-05
• 發(fā)明（設(shè)計）人: 馬坤;周勁;于自強(qiáng);紀(jì)科
• 申請（專利權(quán)）人: 濟(jì)南大學(xué)
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/24
• 代理公司: 濟(jì)南圣達(dá)知識產(chǎn)權(quán)代理有限公司 37221
• 代理人: 黃海麗

本發(fā)明公開了基于低水位滑動時間窗口的離群數(shù)據(jù)發(fā)現(xiàn)方法及系統(tǒng)；包括：數(shù)據(jù)分發(fā)：接收外部數(shù)據(jù)流，然后將外部數(shù)據(jù)流分發(fā)給各個數(shù)據(jù)處理節(jié)點；數(shù)據(jù)處理：數(shù)據(jù)處理節(jié)點對接收到的外部數(shù)據(jù)流進(jìn)行處理；定義低水位滑動時間窗口，以時間戳為水平坐標(biāo)軸，隨著時間推移，低水位滑動時間窗口在時間戳水平坐標(biāo)軸上從左往右不斷移動，在任意時間點，低水位滑動時間窗口水平坐標(biāo)軸上方為未處理數(shù)據(jù)，水平坐標(biāo)軸下方為已處理數(shù)據(jù)；然后根據(jù)當(dāng)前數(shù)據(jù)處理時間戳在低水位滑動時間窗口范圍內(nèi)的位置來發(fā)現(xiàn)當(dāng)前數(shù)據(jù)處理是否為離群數(shù)據(jù)；數(shù)據(jù)聚合：將數(shù)據(jù)處理的結(jié)果進(jìn)行匯總進(jìn)行輸出。區(qū)分可丟棄數(shù)據(jù)、離群數(shù)據(jù)與正常待處理數(shù)據(jù)，提高數(shù)據(jù)處理可靠性，加速故障恢復(fù)。

技術(shù)領(lǐng)域

本發(fā)明涉及一種離群數(shù)據(jù)發(fā)現(xiàn)方法，尤其涉及基于低水位滑動時間窗口的離群數(shù)據(jù)發(fā)現(xiàn)方法及系統(tǒng)。

背景技術(shù)

流處理是對不斷變化的數(shù)據(jù)流進(jìn)行實時計算。為了應(yīng)對用戶對海量數(shù)據(jù)的即時處理帶來的挑戰(zhàn)，解決傳統(tǒng)MapReduce為代表的批處理方式在實時處理的瓶頸問題，新興的流處理方法，在風(fēng)險管理、營銷管理、廣告投放、社會化推薦等方面均具有重要的應(yīng)用價值。

流處理的數(shù)據(jù)來源由于網(wǎng)絡(luò)延遲、系統(tǒng)內(nèi)在并發(fā)等原因，同類數(shù)據(jù)不能保證嚴(yán)格按照時間戳順序到達(dá)數(shù)據(jù)處理節(jié)點，出現(xiàn)數(shù)據(jù)產(chǎn)生與到達(dá)數(shù)據(jù)處理節(jié)點先后不一致的離群數(shù)據(jù)。大量離群數(shù)據(jù)，其處理速度慢，對數(shù)據(jù)處理故障判定產(chǎn)生干擾，增大流處理故障誤判概率。

現(xiàn)有技術(shù)主要通過日志、熱復(fù)制、上游備份等方法實現(xiàn)容錯，均未討論離群數(shù)據(jù)。日志和熱復(fù)制容錯方法使用同步協(xié)議增量復(fù)制，因此大量離群數(shù)據(jù)會嚴(yán)重拖垮復(fù)制過程；上游備份容錯方法會將離群數(shù)據(jù)當(dāng)作故障處理，將會啟動錯誤的故障恢復(fù)。

現(xiàn)有技術(shù)D-Stream采用并行恢復(fù)方法發(fā)現(xiàn)離群數(shù)據(jù)，采用推測執(zhí)行進(jìn)行故障恢復(fù)，其依賴于批處理數(shù)據(jù)分析堆?！，F(xiàn)有技術(shù)給出了一種亂序到達(dá)處理方法，通過標(biāo)點符號和心跳機(jī)制等顯式方法將亂序數(shù)據(jù)有序化。現(xiàn)有技術(shù)MillWheel系統(tǒng)在此原理基礎(chǔ)上提出了低水位概念表示待處理數(shù)據(jù)的底限，當(dāng)時間戳小于低水位的數(shù)據(jù)到達(dá)數(shù)據(jù)處理時，會被直接丟棄。該方法給出了丟失數(shù)據(jù)的判定方法，但未給出離群數(shù)據(jù)的判定方法，僅僅用時間點表示低水位無法嚴(yán)格區(qū)分離群數(shù)據(jù)?，F(xiàn)有技術(shù)Trident通過待處理數(shù)據(jù)嚴(yán)格有序需求避免產(chǎn)生離群數(shù)據(jù)，該方法依賴于事務(wù)框架，產(chǎn)生大量額外的開銷。

發(fā)明內(nèi)容

本發(fā)明的目的就是為了解決上述問題，提供基于低水位滑動時間窗口的離群數(shù)據(jù)發(fā)現(xiàn)方法及系統(tǒng)，有效區(qū)分可丟棄數(shù)據(jù)、離群數(shù)據(jù)與正常待處理數(shù)據(jù)，提高數(shù)據(jù)處理可靠性，加速故障恢復(fù)。

為了實現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

基于低水位滑動時間窗口的離群數(shù)據(jù)發(fā)現(xiàn)方法，包括：

步驟(1)：數(shù)據(jù)分發(fā)：接收外部數(shù)據(jù)流，然后將外部數(shù)據(jù)流分發(fā)給各個數(shù)據(jù)處理節(jié)點；

步驟(2)：數(shù)據(jù)處理：數(shù)據(jù)處理節(jié)點對接收到的外部數(shù)據(jù)流進(jìn)行處理；

定義低水位滑動時間窗口，低水位滑動時間窗口的時間戳起始于低水位初值，低水位滑動時間窗口的寬度為w；低水位滑動時間窗口的時間戳范圍為[低水位初值,低水位初值+低水位滑動時間窗口的寬度w]；

以時間戳為水平坐標(biāo)軸，隨著時間推移，低水位滑動時間窗口在時間戳水平坐標(biāo)軸上從左往右不斷移動，在任意時間點，低水位滑動時間窗口水平坐標(biāo)軸上方為未處理數(shù)據(jù)，水平坐標(biāo)軸下方為已處理數(shù)據(jù)；然后根據(jù)當(dāng)前數(shù)據(jù)處理時間戳在低水位滑動時間窗口范圍內(nèi)的位置來發(fā)現(xiàn)當(dāng)前數(shù)據(jù)處理是否為離群數(shù)據(jù)；

步驟(3)：數(shù)據(jù)聚合：將數(shù)據(jù)處理的結(jié)果進(jìn)行匯總進(jìn)行輸出。

步驟(2)中來自不同關(guān)鍵詞的數(shù)據(jù)流能夠并發(fā)在不同的數(shù)據(jù)處理節(jié)點上進(jìn)行處理。