[發(fā)明專利]一種實時尋找流數(shù)據(jù)自身重復規(guī)律的方法

在審

• 申請?zhí)枺?/td>: 201910011400.5
• 申請日: 2019-01-07
• 公開（公告）號: CN111414577A
• 公開（公告）日: 2020-07-14
• 發(fā)明（設計）人: 呂紀竹
• 申請（專利權）人: 呂紀竹
• 主分類號: G06F17/15
• 分類號: G06F17/15
• 代理公司: 北京市隆安律師事務所 11323
• 代理人: 權鮮枝

自相關函數(shù)可用于尋找流數(shù)據(jù)自身重復規(guī)律。本發(fā)明公開了一種通過迭代計算指定規(guī)模的計算窗口的指定延遲范圍的自相關函數(shù)從而可以實時地尋找流數(shù)據(jù)自身重復規(guī)律的方法，系統(tǒng)和計算設備程序產(chǎn)品。本發(fā)明的實施方案包括基于調整前計算窗口的指定延遲范圍的自相關函數(shù)的多個組件迭代計算調整后計算窗口的指定延遲范圍的自相關函數(shù)的多個組件，然后根據(jù)需要基于迭代計算的組件生成調整后計算窗口的指定延遲范圍的自相關函數(shù)。迭代計算自相關函數(shù)避免訪問調整后計算窗口中的所有數(shù)據(jù)元素和執(zhí)行重復計算從而可以提高計算效率，節(jié)省計算資源和降低計算系統(tǒng)能耗，使得實時尋找流數(shù)據(jù)自身重復規(guī)律高效低耗及一些實時尋找流數(shù)據(jù)自身重復規(guī)律從不可能變?yōu)榭赡堋?/p>

技術領域

大數(shù)據(jù)或流數(shù)據(jù)分析。

背景技術

互聯(lián)網(wǎng)，移動通訊,導航,網(wǎng)游,感應技術和大規(guī)模計算基礎設施每天產(chǎn)生海量數(shù)據(jù)。大數(shù)據(jù)就是由于其巨大規(guī)模,快速變化及增長速度而超出了傳統(tǒng)數(shù)據(jù)庫系統(tǒng)的處理能力及傳統(tǒng)分析方法的分析能力的數(shù)據(jù)。

流數(shù)據(jù)是從數(shù)據(jù)源不斷傳出并連續(xù)地被接收器接收的數(shù)據(jù)。流數(shù)據(jù)可以是傳感器采集并連續(xù)傳送到計算設備或電子設備上的實時數(shù)據(jù)。通常這包括連續(xù)接收有時間間隔,具有相似格式的數(shù)據(jù)元素。流數(shù)據(jù)也可以是從存儲器連續(xù)讀出的數(shù)據(jù),例如存儲在多個計算設備存儲器上的大數(shù)據(jù)集。因此,流數(shù)據(jù)處理算法可以延伸到大數(shù)據(jù)處理上,因為大數(shù)據(jù)集隨著時間積累而可以被認為是具有不規(guī)律時間間隔的數(shù)據(jù)流。

計算自相關函數(shù)是一種尋找時間序列或流數(shù)據(jù)自身重復規(guī)律的有效方法。自相關，也被稱為延遲相關或序列相關，是一個特定的時間序列與延遲了l個時間點的該時間序列本身的相關程度的一個度量。它可以通過一個時間序列的相隔了l個時間點的觀察值的協(xié)相關除以其標準方差來得到。如果計算了一個時間序列的所有不同延遲值的自相關就得到該時間序列的自相關函數(shù)。某個延遲的自相關值為1或接近1可認為時間序列或流數(shù)據(jù)在該延遲后出現(xiàn)自身重復規(guī)律，因此計算自相關函數(shù)后尋找流數(shù)據(jù)自身重復規(guī)律顯而易見，而困難和挑戰(zhàn)在于如何實時地在流數(shù)據(jù)上計算自相關函數(shù)。

為了能夠實時得到利用了最新數(shù)據(jù)的自身重復規(guī)律，自相關函數(shù)可能會在流數(shù)據(jù)有變化后需要重新計算。因此，一些(可能很多)數(shù)據(jù)元素會被重復訪問和使用。例如，有可能自相關函數(shù)在含有n個數(shù)據(jù)元素的計算窗口上被計算。當一個數(shù)據(jù)元素從計算窗口里被去除和一個數(shù)據(jù)元素被加入計算窗口后，計算窗口里所有的n個數(shù)據(jù)元素被訪問來重新計算自相關函數(shù)。

取決于需要，計算窗口的規(guī)模可能非常大，例如計算窗口中的數(shù)據(jù)元素可能分布在云平臺的成千上萬臺計算設備上。在一些數(shù)據(jù)變化后的流數(shù)據(jù)上用傳統(tǒng)方法重新計算自相關函數(shù)無法做到實時處理并且占用和浪費大量計算資源，因此用傳統(tǒng)方法實時地尋找流數(shù)據(jù)自身重復規(guī)律不僅浪費大量計算資源也可能無法滿足需求地實現(xiàn)。

發(fā)明內容

本發(fā)明拓展到方法，系統(tǒng)和計算系統(tǒng)程序產(chǎn)品以迭代方式計算流數(shù)據(jù)的調整后計算窗口的自相關函數(shù)從而可以實時地尋找時間序列或流數(shù)據(jù)自身重復規(guī)律。為一個調整后計算窗口迭代計算自相關函數(shù)包括基于調整前計算窗口的自相關函數(shù)的多個組件迭代計算調整后計算窗口的自相關函數(shù)的多個組件然后根據(jù)需要基于迭代計算的組件生成調整后計算窗口的自相關函數(shù)。某延遲的自相關值為1或接近1可認為數(shù)據(jù)在該延遲后出現(xiàn)自身重復規(guī)律。迭代計算自相關函數(shù)避免訪問調整后計算窗口中的所有數(shù)據(jù)元素和執(zhí)行重復計算從而降低數(shù)據(jù)訪問延遲，提高計算效率，節(jié)省計算資源和降低計算系統(tǒng)能耗，使得一些實時尋找流數(shù)據(jù)自身重復規(guī)律從不可能變?yōu)榭赡堋?/p>

對于一個給定的自相關函數(shù)迭代算法,假設在同一輪迭代計算中一個給定延遲范圍內的每個延遲上所有迭代計算的組件(包括計算窗口的和或平均值)總數(shù)為p(p1)。直接迭代的組件個數(shù)為v(1≤f≤p),則間接迭代的組件個數(shù)為w＝p-f(w≥0)。其中計算窗口的和或平均值是必須迭代計算的特殊組件。和或平均值可以被直接或間接迭代計算。