滑動(dòng)窗口(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-25 20:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-25 20:30:01 來源：信息時(shí)代

    滑動(dòng)窗口 : 數(shù)據(jù)流系統(tǒng)在內(nèi)存中開辟的區(qū)間,該區(qū)間只保存最近一段時(shí)間內(nèi)到達(dá)的數(shù)據(jù)流數(shù)據(jù),并隨著新數(shù)據(jù)到來,窗口不斷向前滑動(dòng),用新數(shù)據(jù)替換舊數(shù)據(jù),以實(shí)時(shí)地支持查詢請(qǐng)求。例如,設(shè)S={…,a_t-1,a_t,a_t+1,…}為一個(gè)數(shù)據(jù)流,T為一個(gè)時(shí)間長(zhǎng)度,t>T是一個(gè)變化的時(shí)刻,t和T具有相同的度量單位,則S的一個(gè)時(shí)間間隔為T的滑動(dòng)窗口可表示為S[t-T:t]。數(shù)據(jù)流系統(tǒng)可以同時(shí)存在多個(gè)數(shù)據(jù)流和多個(gè)滑動(dòng)窗口,同一個(gè)滑動(dòng)窗口可以被多個(gè)不同的連續(xù)查詢共享,同一個(gè)連續(xù)查詢也可能查詢多個(gè)滑動(dòng)窗口中的數(shù)據(jù)。
傳統(tǒng)數(shù)據(jù)庫(kù)中的數(shù)據(jù)是靜態(tài)有界的,所以各種查詢操作可以處理全部數(shù)據(jù),而數(shù)據(jù)流通常具有動(dòng)態(tài)和無界的特性,系統(tǒng)無法一次性處理全部數(shù)據(jù),而某些查詢操作所處理的對(duì)象必須有界,因此,數(shù)據(jù)流上的查詢多為基于窗口的查詢。
數(shù)據(jù)流是無界的,而數(shù)據(jù)流處理的某些操作如連接,只能在數(shù)據(jù)流的有限窗口內(nèi)運(yùn)行。為支持各種不同類型的查詢要求,必須建立多樣化的窗口模型來處理數(shù)據(jù)流中已到達(dá)的和即將到達(dá)的數(shù)據(jù)部分; 同時(shí)要提供靈活的窗口機(jī)制傳遞查詢結(jié)果,使查詢結(jié)果可直接呈現(xiàn)給用戶或由用戶根據(jù)需要取出。窗口是數(shù)據(jù)流有限部分的歷史性快照,從這種意義上可把窗口分為: 基于時(shí)間的滑動(dòng)窗口、基于元組的滑動(dòng)窗口和分區(qū)滑動(dòng)窗口。
基于時(shí)間的滑動(dòng)窗口(time-based sliding windows):數(shù)據(jù)流S的基于時(shí)間的滑動(dòng)窗口實(shí)質(zhì)上是大小變化的窗口,窗口以時(shí)間T為單位,T為數(shù)據(jù)流運(yùn)行時(shí)間的計(jì)算周期。從直觀上來說,基于時(shí)間的滑動(dòng)窗口定義了時(shí)間間隔T上的輸出關(guān)系,從而捕獲到有序數(shù)據(jù)流的最新到達(dá)的元組。輸出關(guān)系可定義為:

R(τ)={S|<S,τ>∈S∧(τ′≤τ)∧(τ′≥max{τ-T,0})}

有兩種特殊情況: 當(dāng)T=0時(shí),R(τ)由數(shù)據(jù)流S中帶有時(shí)間戳τ的元素組成;當(dāng)T=∞時(shí),R(τ)由數(shù)據(jù)流S中所有時(shí)間戮τ≤T的元素組成。
基于元組的滑動(dòng)窗口(tuple-based windows): 數(shù)據(jù)流S的基于元組的滑動(dòng)窗口實(shí)質(zhì)是大小固定的滑動(dòng)窗口,窗口模型以正整數(shù)N作為參數(shù)。直觀地看,帶有時(shí)間的基于元組的滑動(dòng)窗口的輸出關(guān)系是有序數(shù)據(jù)流到目前為止最近到達(dá)的N個(gè)元組。形式上來說,R(τ)是數(shù)據(jù)流S到目前為止最大時(shí)間戳≤τ的N個(gè)元組組成。這樣就產(chǎn)生一個(gè)問題: 假設(shè)我們定義了一個(gè)N個(gè)元組的滑動(dòng)窗口,在某個(gè)時(shí)刻,可能有幾個(gè)第N個(gè)最近時(shí)間戳的元組,因此要處理這種情況以產(chǎn)生精確的N個(gè)元組。如果任意地處理這種情況,基于元組的滑動(dòng)窗口可能就是非確定的,而且當(dāng)時(shí)間戳不唯一時(shí),基于元組的滑動(dòng)窗口可能是不合適的。要解決這樣的問題,需要引入近似時(shí)間戳的概念,使任何兩個(gè)相鄰數(shù)據(jù)的到達(dá)都是在不同的時(shí)間間隔內(nèi)。數(shù)據(jù)流中計(jì)算總和、平均值、直方圖、散列表、頻率方差等統(tǒng)計(jì)值時(shí),采用基于元組的滑動(dòng)窗口比較方便。
分區(qū)滑動(dòng)窗口(partitioned windows): 數(shù)據(jù)流上的分區(qū)滑動(dòng)窗口以正整數(shù)N和數(shù)據(jù)流S的屬性集{A₁,…,A_t}作為參數(shù)。這種窗口將數(shù)據(jù)流S按屬性A₁,…,A_t進(jìn)行分類(類似于group by),分成各個(gè)不同的子數(shù)據(jù)流,然后對(duì)這些子數(shù)據(jù)流分別得到大小為N、基于元組的滑動(dòng)窗口。例如,元組s和它的屬性值a₁,…,a_t,某時(shí)刻的輸出關(guān)系為R(τ),當(dāng)且僅當(dāng)存在一個(gè)元素<s,τ′>∈S,τ′≤T,τ′ 是屬性值為a₁,…,a_t的N個(gè)元素中的最大時(shí)間戳。
根據(jù)滑動(dòng)方式不同,滑動(dòng)窗口分為連續(xù)更新滑動(dòng)窗口和周期更新滑動(dòng)窗口。連續(xù)更新滑動(dòng)窗口定義為: 設(shè)S[t-T:t]為數(shù)據(jù)流S上的一個(gè)滑動(dòng)窗口,如果t始終保持為S中最新元素到達(dá)的時(shí)刻,則稱S[t-T:t]為連續(xù)更新的滑動(dòng)窗口。
周期更新滑動(dòng)窗口定義為: 設(shè)S[t-T:t]為數(shù)據(jù)流S的t時(shí)刻的一個(gè)滑動(dòng)窗口,△t是一個(gè)時(shí)間間隔,如果S[t-T:t]僅在每個(gè)Δt時(shí)間間隔的結(jié)束時(shí)刻改變?yōu)镾[t+kΔt-T:t+kΔt],則稱S[t-T:t]為周期更新的滑動(dòng)窗口。