數據流（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）。以後再想獲取這些數據將會很困難，除非將數據存儲在記憶體中，但由於記憶體大小通常遠遠小於數據流數據的數量，因此實際上通常只能在數據第一次到達時獲取數據。
三個特點
我們認為，當前所研究的數據流計算之所以不同於傳統的計算模式，關鍵在於這些數據流數據本身具有如下三個特點：
數據的到達—快速
酷睿2處理器數據的範圍—廣域
這是指數據屬性（維）的取值範圍非常大，可能取的值非常多，如地域、手機號碼、人、網路節點等。這才是導致數據流無法在記憶體或硬碟中存儲的主要原因。如果維度小，即使到來的數據量很大，也可以在較小的存儲器中保存這些數據。例如，對於無線通信網來說，同樣的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等首先針對數據流數據構造一個直方圖，使用小波對其進行模擬。隨後保留若干最重要的小波係數實現對直方圖的模擬。當新的數據出現時，通過對這些小波係數進行更新以實現直方圖的更新。
文獻提出的實際上是一種直方圖方法，只不過使用了小波變換。A. Gilbert等指出小波變換可以認為是信號與一組正交的長度為N的向量集合所作的內積，因此構造一組數據流數據的略圖，由於略圖可以相當容易和準確地計算信號與一組向量的內積，則可以從略圖計算出小波係數，從而用於點查詢和範圍查詢的估計。
新動向
研究人員對數據流處理的研究不斷深入，我們認為出現了以下新的動向：
未來略圖
引入更多多的的統計
計技技術來構造略圖
G. Cormode等主要處理對頻繁項的計算。它以前人的主項（majority item ） 算法([116, 117])為基礎，使用了error-correcting codes來處理問題。如數據的每一位設立一個計數器，再根據這些計數器的計數結果來推斷頻繁項集合。
Y. Tao等[118]實質上是對Probabilistic counting (已經廣泛地用於資料庫領域的distinct counting)在數據流處理的一種套用。
擴展略圖
對略圖進行擴展，以處理更更復複雜的查詢詢需需求
Lin等在文獻[93]中構造了一個複雜的略圖體系，可用於滑動視窗模型（sliding window model ）和n-of-N模型的分位數估計，這是簡單略圖難以做到的。
在滑動視窗模型下，文獻[93]將數據按時間順序分為多個桶，在每個桶中建立略圖（精度比要求的高），然後查詢時再將這些略圖合併（merge），其中對最後一個桶可能需要進行提升（lift ）操作。維護時只刪除過期的桶，增加新的桶。
在n-of-N model中，文獻[93]將數據按EH Partitioning技術分為多個大小不同的桶，在每個桶中建立略圖（精度比要求的高），然後查詢時再將其中一部分略圖合併，可以保證要求的精度，其中對最後一個同可能需要進行提升。
結合時空數據
與時空數據處理的進一步結合：
Y. Tao等[118]使用數據流的方法處理時空數據，通過對動態的時空數據構造略圖，用於分辨物體是否在多個區域間運動或靜止的狀態，並估算其數量。而這種問題在原先的時空處理中是很難解決的。
小說流派
網路小說數據流是新興流派，意思是小說主角實力數據化，和網遊屬性欄一樣的數據顯示。
