產生背景
數據流細節數據
已經能夠持續自動產生大量的細節數據。這類數據最早出現於傳統的銀行和股票交易領域，後來則也出現在地質測量、氣象、天文觀測等方面。尤其是網際網路(網路流量監控，點擊流)和無線通信網（通話記錄）的出現，產生了大量的數據流類型的數據。我們注意到這類數據大都與地理信息有一定關聯，這主要是因為地理信息的維度較大，容易產生這類大量的細節數據。複雜分析
需要以近實時的方式對更新流進行複雜分析。對以上領域的數據進行複雜分析（如趨勢分析，預測）以前往往是（在數據倉庫中）脫機進行的，然而一些新的套用（尤其是在網路安全和國家安全領域）對時間都非常敏感，如檢測網際網路上的極端事件、欺詐、入侵、異常，複雜人群監控，趨勢監控(tracktrend)，探查性分析（exploratoryanalyses），和諧度分析(harmonicanalysis)等，都需要進行在線上的分析。在此之後，學術界基本認可了這個定義，有的文章也在此基礎上對定義稍微進行了修改。例如，S.Guha等[88]認為，數據流是“只能被讀取一次或少數幾次的點的有序序列”，這裡放寬了前述定義中的“一遍”限制。
為什麼在數據流的處理中，強調對數據讀取次數的限制呢？S.Muthukrishnan[89]指出數據流是指“以非常高的速度到來的輸入數據”，因此對數據流數據的傳輸、計算和存儲都將變得很困難。在這種情況下，只有在數據最初到達時有機會對其進行一次處理，其他時候很難再存取到這些數據（因為沒有也無法保存這些數據）。
定義
數據流（datastream）最初是通信領域使用的概念，代表傳輸中所使用的信息的數字編碼信號序列。然而，我們所提到的數據流概念與此不同。這個概念最初在1998年由Henzinger在文獻[87]中提出，他將數據流定義為“只能以事先規定好的順序被讀取一次的數據的一個序列”。
數據流套用的產生的發展是以下兩個因素的結果：
1.已經能夠持續自動產生大量的細節數據。這類數據最早出現於傳統的銀行和股票交易領域，現在則也出現在地質測量、氣象、天文觀測等方面。尤其是網際網路(網路流量監控，點擊流)和無線通信網（通話記錄）的出現，產生了大量的數據流類型的數據。我們注意到這類數據大都與地理信息有一定關聯，這主要是因為地理信息的維度較大，容易產生這類大量的細節數據。
2.需要以近實時的方式對更新流進行複雜分析。對以上領域的數據進行複雜分析（如趨勢分析，預測）以前往往是（在數據倉庫中）脫機進行的，然而一些新的套用（尤其是在網路安全和國家安全領域）對時間都非常敏感，如檢測網際網路上的極端事件、欺詐、入侵、異常，複雜人群監控，趨勢監控(tracktrend)，探查性分析（exploratoryanalyses），和諧度分析(harmonicanalysis)等，都需要進行在線上的分析。
在此之後，學術界基本認可了這個定義，有的文章也在此基礎上對定義稍微進行了修改。例如，S.Guha等[88]認為，數據流是“只能被讀取一次或少數幾次的點的有序序列”，這裡放寬了前述定義中的“一遍”限制。
為什麼在數據流的處理中，強調對數據讀取次數的限制呢？S.Muthukrishnan[89]指出數據流是指“以非常高的速度到來的輸入數據”，因此對數據流數據的傳輸、計算和存儲都將變得很困難。在這種情況下，只有在數據最初到達時有機會對其進行一次處理，其他時候很難再存取到這些數據（因為沒有也無法保存這些數據）。
B.Babcock等[90]認為數據流模式在以下幾個方面不同於傳統的關係數據模式：
北京交通大學博士學位論文
1.數據在線上到達；
2.處理系統無法控制所處理的數據的到達順序；
3.數據可能是無限多的；
4.由於數據量的龐大，數據流中的元素被處理後將被拋棄或存檔（archive）。以後再想獲取這些數據將會很困難，除非將數據存儲在記憶體中，但由於記憶體大小通常遠遠小於數據流數據的數量，因此實際上通常只能在數據第一次到達時獲取數據。
特徵
我們認為，當前所研究的數據流計算之所以不同於傳統的計算模式，關鍵在於這些數據流數據本身具有如下三個特點：
數據的到達—快速這意味著短時間內可能會有大量的輸入數據需要處理。這對處理器和輸入輸出設備來說都是一個較大的負擔，因此對數據流的處理應儘可能簡單。
數據的範圍—廣域這是指數據屬性（維）的取值範圍非常大，可能取的值非常多，如地域、手機號碼、人、網路節點等。這才是導致數據流無法在記憶體或硬碟中存儲的主要原因。如果維度小，即使到來的數據量很大，也可以在較小的存儲器中保存這些數據。例如，對於無線通信網來說，同樣的100萬條通話記錄，如果只有1000個用戶，那么使用1000個存儲單位就可以保存足夠多和足夠精確的數據來回答“某一用戶的累計通話時間有多長”的問題；而如果共有100000個用戶，要保存這些信息，就需要100000個存儲單位。而目前數據流數據的屬性大多與地理信息、IP位址、手機號碼等有關，而且往往與時間聯繫在一起。這時，數據的維度遠遠超過了記憶體和硬碟容量，這意味著系統無法完整保存這些信息，通常只能在數據到達的時候存取數據一次。
數據到達的時間—持續數據的持續到達意味著數據量可能是無限的。而且，對數據進行處理的結果不會是最終的結果，因為數據還會不斷地到達。因此，對數據流的查詢的結果往往不是一次性而是持續的，即隨著底層數據的到達而不斷返回最新的結果。
以上數據流的特點決定了數據流處理的特點一次存取，持續處理，有限存儲，近似結果，快速回響。
近似結果是在前三個條件限制下產生的必然結果。由於只能存取數據一次，而且只有相對較小的有限空間存儲數據，因此產生精確的計算結果通常是不可能的。而將對結果的要求從過去的“精確”改為“近似”後，實現數據流查詢的快速回響也就成為了可能。
模型
我們試圖從數據集合、數據屬性和計算類型三個不同方面對數據流的模型進行歸納和描述。實際上，近年來很多文章提出了各種各樣的數據流模型，我們並沒有包括所有這些模型，只是將其中比較重要的和常見的進行了歸納和分類。
形式化描述
以下是對數據流的一個形式化描述。
考慮向量α，其屬性的域為[1..n](秩為n)，而且向量α在時間t的狀態
α(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)的。
數據集合
我們首先考慮在進行數據流計算時，有哪些數據被包含在計算範圍之內。關於這個問題，主要有三種不同的模型：分別是數據流模型（datastreammodel）、滑動視窗模型（slidingwindowmodel）和n-of-N模型。
數據流模型（datastreammodel）在數據流模型中，從某個特定時間開始至今的所有數據都要被納入計算範圍。此時，s=0，即在時刻0，α是0向量。即這是數據流最初和最普遍的模型。
北京交通大學博士學位論文
滑動視窗模型（slidingwindowmodel，計算最近的N個數據）滑動視窗模型是指，從計算時算起，向前追溯的N個數據要被納入計算範圍。此時，s=t.N，即在時刻t.N，α是0向量。換句話說，要計算最近的N個數據。由於數據流的數據是不斷湧現的，所以直觀的看，這種模式就像用一個不變的視窗，數據隨時間的推移經過視窗，出現在視窗內的數據就是被計算的數據集合。M.Datar等[91]首先提出這一模式，隨後得到了廣泛回響[92]。
n-of-N模型(計算最近的n個數據，其中0=0。這意味著對於所有的i和t來說，αi(t)總是不小於零，而且是遞增的。實際上，這種模型被認為是最常用的，例如可以用於對收款機（收款機模型由此得名），各個IP的網路傳輸量，手機用戶的通話時長的監控等等。
十字轉門模型（turnstilemodel）同一屬性的數據相加，數據為正或負。在這種模型中，ct可以大於0也可以小於0。這是最通用的模型。S.Muthukrishnan[89]稱其為十字轉門模型起因於這種模型的功能就象捷運站的十字轉門，可以用來計算有多少人到達和離開，從而得出捷運中的人數。
計算類型
對數據流數據的計算可以分為兩類：基本計算和複雜計算。目前，基本計算主要包括對點查詢、範圍查詢和內積查詢這三種查詢的計算。複雜計算包括對分位數的計算、頻繁項的計算以及數據挖掘等。
點查詢（Pointquery）返回αi(t)的值。
範圍查詢（Rangequery）對於範圍查詢Q(f,t)，返回
t
.αi(t)
i=f
內積（Innerproduct）對於向量β，α與β的內積
α.β=Σ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）。不同的策略構成了不同類型的樹。這個框架結構成為後來很多分位數估計算法的基礎。
頻繁項（Frequentitems）有時也稱Heavyhitters，即找出在數據流中頻繁出現的項。在這種計算中，實際上令ct=1。這樣，αi(t)中保存了截至t時刻，維值等於i的數據到達的頻率。對這些數據的查詢又可分為兩種：
找出頭k個最頻繁出現的項
找出所有出現頻率大於1/k的項
目前對頻率項的研究主要集中在後一種計算。
挖掘對數據流數據進行挖掘涉及更複雜的計算。近年來對這方面的研究包括：多維分析[96]，分類分析[97,98]，聚類分析[99–102]，以及其他one-pass算法。
區別特徵
與傳統的關係數據模式區別
B.Babcock等[90]認為數據流模式在以下幾個方面不同於傳統的關係數據模式：1.數據在線上到達；
2.處理系統無法控制所處理的數據的到達順序；
3.數據可能是無限多的；
4.由於數據量的龐大，數據流中的元素被處理後將被拋棄或存檔（archive）。以後再想獲取這些數據將會很困難，除非將數據存儲在記憶體中，但由於記憶體大小通常遠遠小於數據流數據的數量，因此實際上通常只能在數據第一次到達時獲取數據。
三個特點
我們認為，當前所研究的數據流計算之所以不同於傳統的計算模式，關鍵在於這些數據流數據本身具有如下三個特點：數據的到達—快速
這意味著短時間內可能會有大量的輸入數據需要處理。這對處理器和輸入輸出設備來說都是一個較大的負擔，因此對數據流的處理應儘可能簡單。數據的範圍—廣域
這是指數據屬性（維）的取值範圍非常大，可能取的值非常多，如地域、手機號碼、人、網路節點等。這才是導致數據流無法在記憶體或硬碟中存儲的主要原因。如果維度小，即使到來的數據量很大，也可以在較小的存儲器中保存這些數據。例如，對於無線通信網來說，同樣的100萬條通話記錄，如果只有1000個用戶，那么使用1000個存儲單位就可以保存足夠多和足夠精確的數據來回答“某一用戶的累計通話時間有多長”的問題；而如果共有100000個用戶，要保存這些信息，就需要100000個存儲單位。數據流數據的屬性大多與地理信息、IP位址、手機號碼等有關，而且往往與時間聯繫在一起。這時，數據的維度遠遠超過了記憶體和硬碟容量，這意味著系統無法完整保存這些信息，通常只能在數據到達的時候存取數據一次。
數據到達的時間—持續
數據的持續到達意味著數據量可能是無限的。而且，對數據進行處理的結果不會是最終的結果，因為數據還會不斷地到達。因此，對數據流的查詢的結果往往不是一次性而是持續的，即隨著底層數據的到達而不斷返回最新的結果。以上數據流的特點決定了數據流處理的特點一次存取，持續處理，有限存儲，近似結果，快速回響。
近似結果是在前三個條件限制下產生的必然結果。由於只能存取數據一次，而且只有相對較小的有限空間存儲數據，因此產生精確的計算結果通常是不可能的。而將對結果的要求從過去的“精確”改為“近似”後，實現數據流查詢的快速回響也就成為了可能。
相關工作
數據流處理過程中的主要難點在於如何將存儲數據所花費的空間控制在一定範圍之內。查詢回響時間問題雖然也很重要，但相對容易解決。作為近年來研究領域的一個熱點，數據流處理問題得到了廣泛的研究，出現了很多算法。
解決數據流龐大的數據量與有限的存儲空間之間的矛盾的一個思路是使用採樣，另一個思路是，構造一個小的、能提供近似結果的數據結構存放壓縮的數據流數據，這個結構能存放在存儲器中。略圖（Sketch）、直方圖（histogram）和小波（wavelet）實際上就都是這樣的數據結構中最重要的三種。
以上方法實際上大都已用於傳統資料庫領域，問題在於如何將它們套用於數據流的特殊環境。
2.1隨機採樣（Randomsampling）
隨機採樣（Randomsampling）可以通過抽取少量樣本來捕捉數據集合的基本特性。一個很常見的簡單方法就是一致性採樣（uniformsample）。作為一個備選的採樣
北京交通大學博士學位論文
方法分層採樣（strati.edsampling）可以減少數據的不均勻分布所帶來的誤差。不過，對於複雜的分析，普通的採樣算法還是需要太大的空間。
對於數據流的一些特殊計算，已經出現了一些有趣的採樣算法。粘採樣（Stickysampling）[95]用於頻繁項（frequentitems）的計算。粘採樣使用的方法是，在記憶體中存放二元組(i,f)所構成的集合S，對於每到來的一個數據，如果其鍵i已經存在於S,則對應的f加1；否則，以1r的機率進行採樣，如果該項被選中，在S中增加一組（i,1）；每過一段時間，對S中的組進行一遍掃描，對其中的值進行更新。然後增加r的值；結束（或用戶要求結果）時，輸出所有f.(s-e)N的組。
P.Gibbons提出的distinctsampling[104]用於distinctcounting，即找出數據流中不同值的個數。它使用哈希（hash）函式對每一個到來的不同值以2.(i 1)的機率映射到級別i上；如果i≥記憶體級別L（L的初始值為0），將其加入記憶體，否則拋棄；記憶體滿時，將記憶體中級別為L的值刪除，並將L加1；最終對distinctcount的估計為記憶體中不同的值乘以2L。distinctcounting是資料庫處理中的一個老問題，這種算法的優點是，通過設定合適的參數，可套用於帶謂詞的查詢（即對數據流的一個子集進行distinctcounting）。
採樣算法的缺點是：它們對異常數據不夠敏感。而且，即使它們可以很好的套用於普通的數據流模型，但如果要用於滑動視窗模型（slidingwindowmodel）[91]或n-of-N模型[93]，還需要進行較大的修改。
略圖（sketch）
數據流略圖的概念最早由N.Alon在[105]中提出，從此不斷湧現出各種略圖及其構造算法。
N.Alon在[105]中提出的隨機略圖構造（randomizedsteching）可以用於對不同Lp範數的估算，最多需要O(n1.lgn)的空間。該文更重要的貢獻在於，它還可以以O(logn logt)的空間需求估算L2。它的主要思路是，使用哈希函式，將數據屬性的域D中的每一個元素一致地隨機映射到zi∈{.1 1}上，令隨機變數X=.iαizi，X2就可作為對L2範數的估計。
p1
S.Guha等[88]提出的分位數略圖(quantilesketch)保持一組形如（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，將每個集合中元素值的和稱為隨機和（randomsum）。多個隨機和構成一個略圖。對αi的估算為
2E(||AS|||αi∈AS).||A||，其中||A||為數據流中所有數的和。因此，這種略圖可用於估算點查詢的結果。使用多個這樣的略圖，可用於估算範圍查詢、分位數查詢等。略圖技術實際上是空間和精度相權衡的結果。為保證點查詢結果的誤差小於εN，上述略圖需要的空間通常是以ε.2作為係數的。與此相比較，G.Cormode等提出的計數-最小略圖（Count-MinSketch）[19]只需要ε.1係數的空間。其思路也比較簡單，使用若干個哈希函式將分別數據流投射到多個小的略圖上，回答點查詢時，每個略圖分別作答，並選擇值最小的作為答案。以點查詢為基礎，計數-最小略圖可以用於其它各種查詢和複雜計算。計數-最小略圖並不計算Lp範數，而是直接計算出點查詢的結果，這是它的時空效率比其它略圖高的原因之一。
北京交通大學博士學位論文
直方圖（Histogram）
數據流直方圖方法主要用於信號處理、統計、圖像處理、計算機視覺和資料庫。在資料庫領域，直方圖原先主要用於選擇性估計（selectivityestimation），用於選擇查詢最佳化和近似查詢處理。直方圖是一種最簡單、最靈活的近似處理方法，同時也是最有效的一種。只要解決好數據更新問題，就可以將原有的直方圖運用到數據流處理中。這類根據新的數據自動調節的直方圖被稱為動態（或自適應/自調節）直方圖。
L.Fu等[108]提出的直方圖主要用於中值函式（Median）和其他分位數函式的計算，可用於近似計算，也可用於精確查詢。它通過確定性分桶（DeterministicBucketing）和隨機分桶（RandomizedBucketing）技術，構造多個不同精度的桶（buckets），然後將輸入數據逐級分到這些桶中，從而完成了動態直方圖的構造。
由於將靜態直方圖直接套用到數據流處理比較困難。S.Guha等[88]雖然可以動態地構造近最優的V-optimal直方圖，但只能套用於時間序列模型（timeseriesmodel）下的數據流。
一個常採用的方法是將整個算法分為兩步：首先構造一個數據流數據的略圖；然後從這個略圖中構造合適的直方圖。這種方法可以利用略圖數據易於更新的特點，又能實現直方圖的動態化。N.Thaper等[109]首先是構造一個近似反映數據流數據的略圖，利用略圖的優良的更新性能來實現數據的更新，然後從這個略圖中導出一個直方圖來實現對數據流數據的近似。由於從略圖中導出最佳的直方圖是一個NP-hard問題，作者提供了一個啟發式算法(貪婪算法)來搜尋一個較佳的直方圖。
A.Gilbert等[110]構造了一個概要的數據結構，該結構使用一組與文獻[106]中類似的隨機和結構來保存不同粒度級別的dyadicinterval的值。隨後，將不同粒度級別的dyadicinterval（[111]）從大到小地加入所要構造的直方圖中，這樣就將近似誤差降到最低（求精）。
A.Gilbert等在文獻[112]中主要考慮的是如何降低對數據流中每個輸入數據的處理複雜度。他們先將輸入數據轉化為小波係數（利用小波係數是信號與基向量的內積），然後採用了與文獻[110]類似的dyadicinterval處理方法。略圖與直方圖有很密切的聯繫，從某種方面來說，可以認為直方圖是略圖的一種特殊情況。
小波（Wavelet）
數據流小波變換（wavelettransformation）常用於生成數據的概要信息。這是因為通常小波係數只有很少一部分是重要的，大部分係數或者值很小，或者本身不重要。所以，如果忽略數據經過小波變換後生成的不重要係數，就可以使用很少的空間完成對原數據的近似。
Y.Matias等[113]首先針對數據流數據構造一個直方圖，使用小波對其進行模擬。隨後保留若干最重要的小波係數實現對直方圖的模擬。當新的數據出現時，通過對這些小波係數進行更新以實現直方圖的更新。
文獻[113]提出的實際上是一種直方圖方法，只不過使用了小波變換。A.Gilbert等[114]指出小波變換可以認為是信號與一組正交的長度為N的向量集合所作的內積，因此構造一組數據流數據的略圖，由於略圖可以相當容易和準確地計算信號與一組向量的內積，則可以從略圖計算出小波係數，從而用於點查詢和範圍查詢的估計。
新動向
近年來研究人員對數據流處理的研究不斷深入，我們認為出現了以下新的動向：
1引入更多多的的統計
計技技術來構造略圖
G.Cormode等[115]主要處理對頻繁項的計算。它以前人的主項（majorityitem）算法([116,117])為基礎，使用了error-correctingcodes來處理問題。如數據的每一位設立一個計數器，再根據這些計數器的計數結果來推斷頻繁項集合。
Y.Tao等[118]實質上是對Probabilisticcounting[119](已經廣泛地用於資料庫領域的distinctcounting)在數據流處理的一種套用。
2對略圖進行擴展，以處理更複雜的查詢需求
Lin等在文獻[93]中構造了一個複雜的略圖體系，可用於滑動視窗模型（slidingwindowmodel）和n-of-N模型的分位數估計，這是簡單略圖難以做到的。
在滑動視窗模型下，文獻[93]將數據按時間順序分為多個桶，在每個桶中建立略圖（精度比要求的高），然後查詢時再將這些略圖合併（merge），其中對最後一個桶可能需要進行提升（lift）操作。維護時只刪除過期的桶，增加新的桶。
在n-of-Nmodel中，文獻[93]將數據按EHPartitioning技術分為多個大小不同的桶，在每個桶中建立略圖（精度比要求的高），然後查詢時再將其中一部分略圖合併，可以保證要求的精度，其中對最後一個同可能需要進行提升。
3與時空數據處理的進一步結合
J.Sun等在文獻[120]中雖然主要針對時空數據的歷史查詢和預測處理。然而，文章卻強調時空數據是以數據流的形式出現的，處理中也更著重於時空數據的更新性能。
Y.Tao等[118]使用數據流的方法處理時空數據，通過對動態的時空數據構造略圖，用於分辨物體是否在多個區域間運動或靜止的狀態，並估算其數量。而這種問題在原先的時空處理中是很難解決的。
