資料流

資料流

資料流(data stream)最初是通信領域使用的概念,代表傳輸中所使用的信息的數位編碼信號序列。然而,我們所提到的資料流概念與此不同。這個概念最初在1998年由Henzinger在文獻87中提出,他將資料流定義為"隻能以事先規定好的順序被讀取一次的資料的一個序列"。

  • 中文名稱
    資料流
  • 外文名稱
    data stream
  • 概念提出人
    Henzinger
  • 提出時間
    1998年
  • 釋義
    以規定順序被讀取一次的資料序列
  • 發展原因
    2個
  • 資料模式
    4個
  • 計算類型
    可分為兩類:基本計算和復雜計算

產生背景

資料流套用的產生的發展是以下兩個因素的結果:

細節資料

已經能夠持續自動產生大量的細節資料。這類資料最早出現于傳統的銀行和股票交易領域,後來則也出現在地質測量、氣象、天文觀測等方面。尤其是網際網路(網路流量監控,點擊流)和無線通信網(通話記錄)的出現,產生了大量的資料流類型的資料。我們註意到這類資料大都與地理信息有一定關聯,這主要是因為地理信息的維度較大,容易產生這類大量的細節資料。

復雜分析

需要以近即時的方式對更新流進行復雜分析。對以上領域的資料進行復雜分析(如趨勢分析,預測)以前往往是(在資料倉庫中)脫機進行的,然而一些新的套用(尤其是在網路安全和國家安全領域)對時間都非常敏感,如檢測網際網路上的極端事件、欺詐、入侵、異常,復雜人群監控,趨勢監控(track trend),探查性分析(exploratory analyses),和諧度分析(harmonic analysis)等,都需要進行在線上的分析。

在此之後,學術界基本認可了這個定義,有的文章也在此基礎上對定義稍微進行了修改。例如,S. Guha等[88]認為,資料流是"隻能被讀取一次或少數幾次的點的有序序列",這裏放寬了前述定義中的"一遍"限製。

為什麽在資料流的處理中,強調對資料讀取次數的限製呢?S. Muthukrishnan[89]指出資料流是指"以非常高的速度到來的輸入資料",因此對資料流資料的傳輸、計算和存儲都將變得很困難。在這種情況下,隻有在資料最初到達時有機會對其進行一次處理,其他時候很難再存取到這些資料(因為沒有也無法儲存這些資料)。

區別特征

與傳統的關系資料模式區別

B.Babcock等[90]認為資料流模式在以下幾個方面不同于傳統的關系資料模式:

1. 資料在線上到達;

2. 處理系統無法控製所處理的資料的到達順序;

3. 資料可能是無限多的;

4. 由于資料量的龐大,資料流中的元素被處理後將被拋棄或存檔(archive)。以後再想獲取這些資料將會很困難,除非將資料存儲在記憶體中,但由于記憶體大小通常遠遠小于資料流資料的數量,因此實際上通常隻能在資料第一次到達時獲取資料。

三個特點

我們認為,當前所研究的資料流計算之所以不同于傳統的計算模式,關鍵在于這些資料流資料本身具有如下三個特點:

資料的到達-快速

這意味著短時間內可能會有大量的輸入資料需要處理。這對處理器和輸入輸出設備來說都是一個較大的負擔,因此對資料流的處理應盡可能簡單。

資料的範圍-廣域

這是指資料屬性(維)的取值範圍非常大,可能取的值非常多,如地域、手機號碼、人、網路節點等。這才是導致資料流無法在記憶體或硬碟中存儲的主要原因。如果維度小,即使到來的資料量很大,也可以在較小的存儲器中儲存這些資料。例如,對于無線通信網來說,同樣的100萬條通話記錄,如果隻有1000個使用者,那麽使用1000個存儲單位就可以儲存足夠多和足夠精確的資料來回答"某一使用者的累計通話時間有多長"的問題;而如果共有100000個使用者,要儲存這些信息,就需要100000個存儲單位。資料流資料的屬性大多與地理信息、IP地址、手機號碼等有關,而且往往與時間聯系在一起。這時,資料的維度遠遠超過了記憶體和硬碟容量,這意味著系統無法完整儲存這些信息,通常隻能在資料到達的時候存取資料一次。

資料到達的時間-持續

資料的持續到達意味著資料量可能是無限的。而且,對資料進行處理的結果不會是最終的結果,因為資料還會不斷地到達。因此,對資料流的查詢的結果往往不是一次性而是持續的,即隨著底層資料的到達而不斷返回最新的結果。

以上資料流的特點決定了資料流處理的特點一次存取,持續處理,有限存儲, 近似結果,快速回響。

近似結果是在前三個條件限製下產生的必然結果。由于隻能存取資料一次,而且隻有相對較小的有限空間存儲資料,因此產生精確的計算結果通常是不可能的。而將對結果的要求從過去的"精確"改為"近似"後,實現資料流查詢的快速回響也就成為了可能。

分類

資料的性質、格式不同,則對流的處理方法也不同,因此,在Java的輸入/輸出類庫中,有不同的流類來對應不同性質的輸入/輸出流。在java.io包中,基本輸入/輸出流類可按其讀寫資料的類型之不同分為兩種:位元組流和字元流。

輸入流與輸出流

資料流分為輸入流(InputStream)和輸出流(OutputStream)兩類。輸入流隻能讀不能寫,而輸出流隻能寫不能讀。通常程式中使用輸入流讀出資料,輸出流寫入資料,就好像資料流入到程式並從程式中流出。採用資料流使程式的輸入輸出操作獨立與相關設備。

輸入流可從鍵盤或檔案中獲得資料,輸出流可向顯示器、印表機或檔案中傳輸資料。

緩沖流

為了提高資料的傳輸效率,通常使用緩沖流(Buffered Stream),即為一個流配有一個緩沖區(buffer),一個緩沖區就是專門用于傳輸資料的記憶體塊。當向一個緩沖流寫入資料時,系統不直接傳送到外部設備,而是將資料傳送到緩沖區。緩沖區自動記錄資料,當緩沖區滿時,系統將資料全部傳送到相應的設備。

當從一個緩沖流中讀取資料時,系統實際是從緩沖區中讀取資料。當緩沖區空時,系統就會從相關設備自動讀取資料,並讀取盡可能多的資料充滿緩沖區。

模型描述

我們嘗試從資料集合、資料屬性和計算類型三個不同方面對資料流的模型進行歸納和描述。實際上,很多文章提出了各種各樣的資料流模型,我們並沒有包括所有這些模型,隻是將其中比較重要的和常見的進行了歸納和分類。

形式化

以下是對資料流的一個形式化描述。

考慮向量α,其屬性的域為[1..n](秩為n),而且向量α在時間t的狀態

α(t)=<α1(t), ...αi(t), ...αn(t) >

在時刻s,α是0向量,即對于所有i,αi(s)=0。對向量的各個分量的更新是以二元組流的形式出現的。即,第t個更新為(i, ct),意味著αi(t)= αi(t . 1) + ct,且對于i. =.i,αi. (t)= αi. (t . 1)。在時刻t發生的查詢是針對α(t)的。

資料集合

我們首先考慮在進行資料流計算時,有哪些資料被包含在計算範圍之內。關于這個問題,主要有三種不同的模型:分別是資料流模型(data stream model)、滑動視窗模型(sliding window model)和n-of-N模型。

資料流模型(data stream model)在資料流模型中,從某個特定時間開始至今的所有資料都要被納入計算範圍。此時,s=0,即在時刻0,α是0向量。即這是資料流最初和最普遍的模型。

滑動視窗模型(sliding window model ,計算最近的N個資料)滑動視窗模型是指,從計算時算起,向前追溯的N個資料要被納入計算範圍。此時,s = t . N,即在時刻t . N,α是0向量。換句話說,要計算最近的N個資料。由于資料流的資料是不斷涌現的,所以直觀的看,這種模式就像用一個不變的視窗,資料隨時間的推移經過視窗,出現在視窗內的資料就是被計算的資料集合。M. Datar等[91]首先提出這一模式,隨後得到了廣泛回響[92]。

n-of-N模型(計算最近的n個資料,其中0 <n ≤ N) 文獻[93] 提出的這種模型建立在滑動視窗模型的基礎之上,比滑動視窗模型更為靈活:被納入計算範圍的是從計算時算起,向前追溯的n個資料。此時,s = t . n,即在時刻t . n,α是0向量。註意,其中n ≤ N,而且是可以隨查詢要求變化的。而在滑動視窗模型中,n = N而且是固定不變的。對于資料流處理系統來說,要能夠回答所有長度小于等于N的滑動視窗問題。

資料屬性

我們在來看一下資料本身的特征。

時間序列(time series model) 資料按照其屬性(實際上就是時間)的順序前來。在這種情況下,i = t,即一個t時刻的更新為(t, ct)。此時對α的更新操作為αt(t)= ct, 且對于i. =.t,αi. (t)= αi. (t . 1)。這種模型適用于時序資料,如某特定IP的傳出的資料,或股票的定期更新資料等。

收款機模型(cash register model) 同一屬性的資料相加,資料為正。在這種模型中,ct >=0。這意味著對于所有的i和t來說,αi(t)總是不小于零,而且是遞增的。實際上,這種模型被認為是最常用的,例如可以用于對收款機(收款機模型由此得名),各個IP的網路傳輸量,手機使用者的通話時長的監控等等。

十字轉門模型(turnstile model) 同一屬性的資料相加,資料為正或負。在這種模型中,ct可以大于0也可以小于0。這是最通用的模型。S. Muthukrishnan[89]稱其為十字轉門模型起因于這種模型的功能就象捷運站的十字轉門,可以用來計算有多少人到達和離開,從而得出捷運中的人數。

計算類型

對資料流資料的計算可以分為兩類:基本計算和復雜計算。基本計算主要包括對點查詢、範圍查詢和內積查詢這三種查詢的計算。復雜計算包括對分位數的計算、頻繁項的計算以及資料挖掘等。

點查詢(Point query) 返回αi(t)的值。

範圍查詢(Range query) 對于範圍查詢Q(f, t),返回

t

. αi(t)

i=f

內積(Inner product) 對于向量β,α與β的內積

α . β =Σni=1αi(t)βi

分位數(Quantile) 給定一個序號r,返回值v,並確保v在α中的真實排序r.符合以下要求:

r . εN ≤ r. ≤ r + εN

其中,ε是精度,N =Σni=1αi(t)。

G. S. Manku等[94]提供了對分位數進行一遍掃描進行近似估計的架構結構,將資料集合看成樹的節點,這些節點擁有不同的權重(如節點中包含的資料個數)。認為所有的分位數的估計演算法都可以被認為由三個對節點的操作組成產生新節點(NEW) 、合並(COLLAPSE)和輸出(OUTPUT)。不同的策略構成了不同類型的樹。這個架構結構成為後來很多分位數估計演算法的基礎。

頻繁項(Frequent items)有時也稱Heavy hitters,即找出在資料流中頻繁出現的項。在這種計算中,實際上令ct =1。這樣,αi(t)中儲存了截至t時刻,維值等于i的資料到達的頻率。對這些資料的查詢又可分為兩種:

找出頭k個最頻繁出現的項

找出所有出現頻率大于1/k的項

對頻率項的研究主要集中在後一種計算[95]。

挖掘對資料流資料進行挖掘涉及更復雜的計算。對這方面的研究包括:多維分析[96],分類分析[97, 98],聚類分析[99–102],以及其他one-pass演算法[103]。

相關思路

簡介

資料流處理過程中的主要難點在于如何將存儲資料所花費的空間控製在一定範圍之內。查詢回響時間問題雖然也很重要,但相對容易解決。作為研究領域的一個熱點,資料流處理問題得到了廣泛的研究,出現了很多演算法。

解決資料流龐大的資料量與有限的存儲空間之間的矛盾的一個思路是使用採樣,另一個思路是,構造一個小的、能提供近似結果的資料結構存放壓縮的資料流資料,這個結構能存放在存儲器中。略圖(Sketch)、直方圖(histogram)和小波(wavelet)實際上就都是這樣的資料結構中最重要的三種。

以上方法實際上大都已用于傳統資料庫領域,問題在于如何將它們套用于資料流的特殊環境。

隨機採樣

隨機採樣(Random sampling)可以通過抽取少量樣本來捕捉資料集合的基本特徵。一個很常見的簡單方法就是一致性採樣(uniform sample)。作為一個備選的採樣方法分層採樣(strati.ed sampling)可以減少資料的不均勻分布所帶來的誤差。不過,對于復雜的分析,普通的採樣演算法還是需要太大的空間。

對于資料流的一些特殊計算,已經出現了一些有趣的採樣演算法。粘採樣(Sticky sampling)[95]用于頻繁項(frequent items)的計算。粘採樣使用的方法是,在記憶體中存放二元組(i,f)所構成的集合S,對于每到來的一個資料,如果其鍵i已經存在于S,則對應的f加1;否則,以1 r 的概率進行採樣,如果該項被選中,在S中增加一組(i,1);每過一段時間,對S中的組進行一遍掃描,對其中的值進行更新。然後增加r的值;結束(或使用者要求結果)時,輸出所有f.(s-e)N的組。

P. Gibbons提出的distinct sampling[104]用于distinct counting ,即找出資料流中不同值的個數。它使用哈希(hash )函式對每一個到來的不同值以2.(i+1)的概率對應到級別i上;如果i ≥記憶體級別L(L的初始值為0),將其加入記憶體,否則拋棄;記憶體滿時,將記憶體中級別為L的值移除,並將L加1;最終對distinct count的估計為記憶體中不同的值乘以2L。distinct counting是資料庫處理中的一個老問題,這種演算法的優點是,通過設定合適的參數,可套用于帶謂詞的查詢(即對資料流的一個子集進行distinct counting)。

採樣演算法的缺點是:它們對異常資料不夠敏感。而且,即使它們可以很好的套用于普通的資料流模型,但如果要用于滑動視窗模型(sliding window model)[91] 或n-of-N模型[93],還需要進行較大的修改。

構造略圖

構造略圖(sketching)是指使用隨機對應(Random projections)將資料流投射在一個小的存儲空間內作為整個資料流的概要,這個小空間存儲的概要資料稱為略圖,可用于近似回答特定的查詢。不同的略圖可用于對資料流的不同Lp範數的估算,進而這些Lp範數可用于回答其它類型的查詢。如L0範數可用于估算資料流的不同值(distinct count);L1範數可用于計算分位數(quantile)和頻繁項(frequent items);L2範數可用于估算自連線的長度等等。

略圖的概念最早由N. Alon在[105]中提出,從此不斷涌現出各種略圖及其構造演算法。

N. Alon 在[105]中提出的隨機略圖構造(randomized steching)可以用于對不同Lp範數的估算,最多需要O(n 1. lg n)的空間。該文更重要的貢獻在于,它還可以以O(log n + log t)的空間需求估算L2。它的主要思路是,使用哈希函式,將資料屬性的域D中的每一個元素一致地隨機對應到zi ∈ {.1+ 1}上,令隨機變數X = .i αizi,X2就可作為對L2範數的估計。

p1

S. Guha 等[88]提出的分位數略圖(quantile sketch) 保持一組形如(vi,gi, Δi)的資料結構,rmax(vi) 和rmin(vi)分別是vi可能的排位的最大和最小值。對于i>j 滿足:

vi >vj

gi = rmin(vi) . rmin(vi . 1)

Δi = rmax(vi) . rmin(vi)

隨著資料的到來,對此略圖進行相應的更新操作,使估算保持在一定的精度之內。X. Lin等[93]對于這個問題做出了更形式化的描述。

若令AS為一個從[1..n]中提取的隨機集合,每一個元素被提取的概率為1/2。A. Gilbert 等[106]構造若幹個AS,將每個集合中元素值的和稱為隨機和(random sum)。多個隨機和構成一個略圖。對αi的估算為

2E(||AS|| |αi ∈ AS) . ||A||, 其中||A||為資料流中所有數的和。因此,這種略圖可用于估算點查詢的結果。使用多個這樣的略圖,可用于估算範圍查詢、分位數查詢等。略圖技術實際上是空間和精度相權衡的結果。為保證點查詢結果的誤差小于εN, 上述略圖需要的空間通常是以ε.2作為系數的。與此相比較,G. Cormode 等提出的計數-最小略圖(Count-Min Sketch )[19]隻需要ε.1系數的空間。其思路也比較簡單,使用若幹個哈希函式將分別資料流投射到多個小的略圖上,回答點查詢時,每個略圖分別作答,並選擇值最小的作為答案。以點查詢為基礎,計數-最小略圖可以用于其它各種查詢和復雜計算。計數-最小略圖並不計算Lp範數,而是直接計算出點查詢的結果,這是它的時空效率比其它略圖高的原因之一。

直方圖

直方圖(histogram)有兩個含義:一個是普通意義上的直方圖,是一種用于顯示近似統計的視覺手段;另外,它還是一種捕捉資料的近似分布的資料結構/方法。作為後者出現時時,直方圖是這樣構造的:將資料按其屬性分到多個不相交的子集(稱為桶)並用某種統一的方式近似表示桶中的值[107]。

直方圖直方圖

直方圖方法主要用于信號處理、統計、圖像處理、電腦視覺和資料庫。在資料庫領域,直方圖原先主要用于選擇性估計(selectivity estimation),用于選擇查詢最佳化和近似查詢處理。直方圖是一種最簡單、最靈活的近似處理方法,同時也是最有效的一種。隻要解決好資料更新問題,就可以將原有的直方圖運用到資料流處理中。這類根據新的資料自動調節的直方圖被稱為動態(或自適應/自調節)直方圖。

L. Fu等[108]提出的直方圖主要用于中值函式(Median )和其他分位數函式的計算,可用于近似計算,也可用于精確查詢。它通過確定性分桶(Deterministic Bucketing )和隨機分桶(Randomized Bucketing )技術,構造多個不同精度的桶(buckets),然後將輸入資料逐級分到這些桶中,從而完成了動態直方圖的構造。

由于將靜態直方圖直接套用到資料流處理比較困難。S. Guha等[88]雖然可以動態地構造近最優的V-optimal 直方圖,但隻能套用于時間序列模型(time series model) 下的資料流。

一個常採用的方法是將整個演算法分為兩步:首先構造一個資料流資料的略圖;然後從這個略圖中構造合適的直方圖。這種方法可以利用略圖資料易于更新的特點,又能實現直方圖的動態化。N. Thaper等[109]首先是構造一個近似反映資料流資料的略圖,利用略圖的優良的更新性能來實現資料的更新,然後從這個略圖中導出一個直方圖來實現對資料流資料的近似。由于從略圖中導出最佳的直方圖是一個NP-hard問題,作者提供了一個啓發式演算法(貪婪演算法)來搜尋一個較佳的直方圖。

A. Gilbert等[110]構造了一個概要的資料結構,該結構使用一組與文獻[106]中類似的隨機和結構來儲存不同粒度級別的dyadic interval的值。隨後,將不同粒度級別的dyadic interval([111])從大到小地加入所要構造的直方圖中,這樣就將近似誤差降到最低(求精)。

A. Gilbert等在文獻[112]中主要考慮的是如何降低對資料流中每個輸入資料的處理復雜度。他們先將輸入資料轉化為小波系數(利用小波系數是信號與基向量的內積),然後採用了與文獻[110]類似的dyadic interval處理方法。略圖與直方圖有很密切的聯系,從某種方面來說,可以認為直方圖是略圖的一種特殊情況。

小波變換

小波變換(wavelet transformation)常用于生成資料的概要信息。這是因為通常小波系數隻有很少一部分是重要的,大部分系數或者值很小,或者本身不重要。所以,如果忽略資料經過小波變換後生成的不重要系數,就可以使用很少的空間完成對原資料的近似。

Y. Matias等[113] 首先針對資料流資料構造一個直方圖,使用小波對其進行模擬。隨後保留若幹最重要的小波系數實現對直方圖的模擬。當新的資料出現時,通過對這些小波系數進行更新以實現直方圖的更新。

文獻[113]提出的實際上是一種直方圖方法,隻不過使用了小波變換。A. Gilbert等[114]指出小波變換可以認為是信號與一組正交的長度為N的向量集合所作的內積,因此構造一組資料流資料的略圖,由于略圖可以相當容易和準確地計算信號與一組向量的內積,則可以從略圖計算出小波系數,從而用于點查詢和範圍查詢的估計。

新動向

研究人員對資料流處理的研究不斷深入,我們認為出現了以下新的動向:

未來略圖

引入更多多的的統計

計技技術來構造略圖

G. Cormode等[115]主要處理對頻繁項的計算。它以前人的主項(majority item ) 演算法([116, 117])為基礎,使用了error-correcting codes來處理問題。如資料的每一位設立一個計數器,再根據這些計數器的計數結果來推斷頻繁項集合。

Y. Tao等[118]實質上是對Probabilistic counting [119] (已經廣泛地用于資料庫領域的distinct counting)在資料流處理的一種套用。

擴展略圖

對略圖進行擴展,以處理更更復復雜的查詢詢需需求

Lin等在文獻[93]中構造了一個復雜的略圖體系,可用于滑動視窗模型(sliding window model )和n-of-N模型的分位數估計,這是簡單略圖難以做到的。

在滑動視窗模型下,文獻[93]將資料按時間順序分為多個桶,在每個桶中建立略圖(精度比要求的高),然後查詢時再將這些略圖合並(merge),其中對最後一個桶可能需要進行提升(lift )操作。維護時隻移除過期的桶,增加新的桶。

在n-of-N model中,文獻[93]將資料按EH Partitioning技術分為多個大小不同的桶,在每個桶中建立略圖(精度比要求的高),然後查詢時再將其中一部分略圖合並,可以保證要求的精度,其中對最後一個同可能需要進行提升。

結合時空資料

與時空資料處理的進一步結合

資料流資料流

J. Sun等在文獻[120]中雖然主要針對時空資料的歷史查詢和預測處理。然而,文章卻強調時空資料是以資料流的形式出現的,處理中也更著重于時空資料的更新性能。

Y. Tao等[118]使用資料流的方法處理時空資料,通過對動態的時空資料構造略圖,用于分辨物體是否在多個區域間運動或靜止的狀態,並估算其數量。而這種問題在原先的時空處理中是很難解決的。

小說流派

網路小說資料流是新興流派,意思是小說主角實力資料化,和網遊屬性欄一樣的資料顯示。

相關詞條

相關搜尋

其它詞條