時間:2022-11-21 14:30:02 | 來源:信息時代
時間:2022-11-21 14:30:02 來源:信息時代
數(shù)據(jù)流過濾器 : 在數(shù)據(jù)流中選擇滿足特定性質(zhì)的元組。在數(shù)據(jù)流應用中特別是在多路連接中經(jīng)常使用過濾器。在連續(xù)的元組被處理時,可以形象地將處理流程看成一條管道,對元組的每步操作可看成一個過濾器。每通過一個過濾器,有的元組被過濾,有的元組被保留,最后剩下的元組通過運算得到查詢的結果。當然,實際上被保留的元組可能需經(jīng)過過濾器操作后產(chǎn)生下一個過濾器的輸入。過濾器的過濾操作可以是針對元組的投影、選擇、連接或者它們的組合構成的運算等。管道式過濾器順序問題就是在當前環(huán)境下,如何安排這些過濾器的順序而使得處理代價最小,提高處理效率。過濾器在數(shù)據(jù)流應用中是極為普遍的。
例如,在網(wǎng)絡中,A、B、C、D分別為四個路由,需要計算過去半個小時內(nèi)分別通過四個路由的總的網(wǎng)絡流量。本例中有四個流SA、SB、SC和SD,分別表示四個路由產(chǎn)生的數(shù)據(jù)包,每個數(shù)據(jù)流的模式相同,都為(pid,size,ts),其中pid為數(shù)據(jù)包的標記號,size為包的大小,ts為時間戳。每個數(shù)據(jù)流包含一個基于時間的大小為半個小時的滑動窗口,分別用WA、WB、WC和WD表示,并為pid建立索引以方便查找。當元組t插入WA時,則以一定的順序檢測其他三個窗口WB、WC、WD中pid的索引,即通過過濾器過濾,如果每個窗口中都包含t.pid,則將t送入聚集算子sum(size),否則過濾該元組,不同的順序?qū)е聇被過濾的時刻不同。這里值得指出的是,如果元組t被過濾,則在t被過濾前對t所有的操作都是無效的,也就是說如果t被過濾,則過濾得越早付出的處理代價越小。當元組進入其他窗口時類似。
圖1展示了以WD、WB、WC為檢測順序的處理策略。在這種策略下,如果路由A中數(shù)據(jù)大部分是從路由B和D中來的,而從C中來的很少,則顯然沒有以WC、WB、WD為檢測順序的處理策略來的高。因為采用WC、WB、WD為檢測順序的處理策略,則許多元組將在第一次檢測時被過濾,可以很好地減少處理代價。
輸入流滑動窗口
圖1 處理策略
微信公眾號
版權所有? 億企邦 1997-2022 保留一切法律許可權利。