數(shù)據(jù)流

　　1 背景知識(shí)
　　1.1 定義
　　數(shù)據(jù)流（data stream）最初是通信領(lǐng)域使用的概念，代表傳輸中所使用的信息的數(shù)字編碼信號(hào)序列。然而，我們所提到的數(shù)據(jù)流概念與此不同。這個(gè)概念最初在1998年由Henzinger在文獻(xiàn)[87]中提出，他將數(shù)據(jù)流定義為“只能以事先規(guī)定好的順序被讀取一次的數(shù)據(jù)的一個(gè)序列”。
　　數(shù)據(jù)流應(yīng)用的產(chǎn)生的發(fā)展是以下兩個(gè)因素的結(jié)果：
　　1. 已經(jīng)能夠持續(xù)自動(dòng)產(chǎn)生大量的細(xì)節(jié)數(shù)據(jù)。這類數(shù)據(jù)最早出現(xiàn)于傳統(tǒng)的銀行和股票交易領(lǐng)域，現(xiàn)在則也出現(xiàn)在地質(zhì)測(cè)量、氣象、天文觀測(cè)等方面。尤其是互聯(lián)網(wǎng)(網(wǎng)絡(luò)流量監(jiān)控，點(diǎn)擊流)和無線通信網(wǎng)（通話記錄）的出現(xiàn)，產(chǎn)生了大量的數(shù)據(jù)流類型的數(shù)據(jù)。我們注意到這類數(shù)據(jù)大都與地理信息有一定關(guān)聯(lián)，這主要是因?yàn)榈乩硇畔⒌木S度較大，容易產(chǎn)生這類大量的細(xì)節(jié)數(shù)據(jù)。
　　2. 需要以近實(shí)時(shí)的方式對(duì)更新流進(jìn)行復(fù)雜分析。對(duì)以上領(lǐng)域的數(shù)據(jù)進(jìn)行復(fù)雜分析（如趨勢(shì)分析，預(yù)測(cè)）以前往往是（在數(shù)據(jù)倉(cāng)庫(kù)中）脫機(jī)進(jìn)行的，然而一些新的應(yīng)用（尤其是在網(wǎng)絡(luò)安全和國(guó)家安全領(lǐng)域）對(duì)時(shí)間都非常敏感，如檢測(cè)互聯(lián)網(wǎng)上的極端事件、欺詐、入侵、異常，復(fù)雜人群監(jiān)控，趨勢(shì)監(jiān)控(track trend)，探查性分析（exploratory analyses），和諧度分析(harmonic analysis)等，都需要進(jìn)行聯(lián)機(jī)的分析。
　　在此之后，學(xué)術(shù)界基本認(rèn)可了這個(gè)定義，有的文章也在此基礎(chǔ)上對(duì)定義稍微進(jìn)行了修改。例如，S. Guha等[88]認(rèn)為，數(shù)據(jù)流是“只能被讀取一次或少數(shù)幾次的點(diǎn)的有序序列”，這里放寬了前述定義中的“一遍”限制。
　　為什么在數(shù)據(jù)流的處理中，強(qiáng)調(diào)對(duì)數(shù)據(jù)讀取次數(shù)的限制呢？S. Muthukrishnan[89]指出數(shù)據(jù)流是指“以非常高的速度到來的輸入數(shù)據(jù)”，因此對(duì)數(shù)據(jù)流數(shù)據(jù)的傳輸、計(jì)算和存儲(chǔ)都將變得很困難。在這種情況下，只有在數(shù)據(jù)最初到達(dá)時(shí)有機(jī)會(huì)對(duì)其進(jìn)行一次處理，其他時(shí)候很難再存取到這些數(shù)據(jù)（因?yàn)闆]有也無法保存這些數(shù)據(jù)）。
　　B. Babcock等[90]認(rèn)為數(shù)據(jù)流模式在以下幾個(gè)方面不同于傳統(tǒng)的關(guān)系數(shù)據(jù)模式：
　　1. 數(shù)據(jù)聯(lián)機(jī)到達(dá)；
　　2. 處理系統(tǒng)無法控制所處理的數(shù)據(jù)的到達(dá)順序；
　　3. 數(shù)據(jù)可能是無限多的；
　　4. 由于數(shù)據(jù)量的龐大，數(shù)據(jù)流中的元素被處理后將被拋棄或存檔（archive）。以后再想獲取這些數(shù)據(jù)將會(huì)很困難，除非將數(shù)據(jù)存儲(chǔ)在內(nèi)存中，但由于內(nèi)存大小通常遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)流數(shù)據(jù)的數(shù)量，因此實(shí)際上通常只能在數(shù)據(jù)第一次到達(dá)時(shí)獲取數(shù)據(jù)。
　　1.2 特征
　　我們認(rèn)為，當(dāng)前所研究的數(shù)據(jù)流計(jì)算之所以不同于傳統(tǒng)的計(jì)算模式，關(guān)鍵在于這些數(shù)據(jù)流數(shù)據(jù)本身具有如下三個(gè)特點(diǎn)：
　　數(shù)據(jù)的到達(dá)—快速 這意味著短時(shí)間內(nèi)可能會(huì)有大量的輸入數(shù)據(jù)需要處理。這對(duì)處理器和輸入輸出設(shè)備來說都是一個(gè)較大的負(fù)擔(dān)，因此對(duì)數(shù)據(jù)流的處理應(yīng)盡可能簡(jiǎn)單。
　　數(shù)據(jù)的范圍—廣域 這是指數(shù)據(jù)屬性（維）的取值范圍非常大，可能取的值非常多，如地域、手機(jī)號(hào)碼、人、網(wǎng)絡(luò)節(jié)點(diǎn)等。這才是導(dǎo)致數(shù)據(jù)流無法在內(nèi)存或硬盤中存儲(chǔ)的主要原因。如果維度小，即使到來的數(shù)據(jù)量很大，也可以在較小的存儲(chǔ)器中保存這些數(shù)據(jù)。例如，對(duì)于無線通信網(wǎng)來說，同樣的100萬條通話記錄，如果只有1000個(gè)用戶，那么使用1000個(gè)存儲(chǔ)單位就可以保存足夠多和足夠精確的數(shù)據(jù)來回答“某一用戶的累計(jì)通話時(shí)間有多長(zhǎng)”的問題；而如果共有100000個(gè)用戶，要保存這些信息，就需要100000個(gè)存儲(chǔ)單位。而目前數(shù)據(jù)流數(shù)據(jù)的屬性大多與地理信息、IP地址、手機(jī)號(hào)碼等有關(guān)，而且往往與時(shí)間聯(lián)系在一起。這時(shí)，數(shù)據(jù)的維度遠(yuǎn)遠(yuǎn)超過了內(nèi)存和硬盤容量，這意味著系統(tǒng)無法完整保存這些信息，通常只能在數(shù)據(jù)到達(dá)的時(shí)候存取數(shù)據(jù)一次。
　　數(shù)據(jù)到達(dá)的時(shí)間—持續(xù) 數(shù)據(jù)的持續(xù)到達(dá)意味著數(shù)據(jù)量可能是無限的。而且，對(duì)數(shù)據(jù)進(jìn)行處理的結(jié)果不會(huì)是最終的結(jié)果，因?yàn)閿?shù)據(jù)還會(huì)不斷地到達(dá)。因此，對(duì)數(shù)據(jù)流的查詢的結(jié)果往往不是一次性而是持續(xù)的，即隨著底層數(shù)據(jù)的到達(dá)而不斷返回最新的結(jié)果。
　　以上數(shù)據(jù)流的特點(diǎn)決定了數(shù)據(jù)流處理的特點(diǎn)一次存取，持續(xù)處理，有限存儲(chǔ)， 近似結(jié)果，快速響應(yīng)。
　　近似結(jié)果是在前三個(gè)條件限制下產(chǎn)生的必然結(jié)果。由于只能存取數(shù)據(jù)一次，而且只有相對(duì)較小的有限空間存儲(chǔ)數(shù)據(jù)，因此產(chǎn)生精確的計(jì)算結(jié)果通常是不可能的。而將對(duì)結(jié)果的要求從過去的“精確”改為“近似”后，實(shí)現(xiàn)數(shù)據(jù)流查詢的快速響應(yīng)也就成為了可能。
　　1.3 模型
　　我們?cè)噲D從數(shù)據(jù)集合、數(shù)據(jù)屬性和計(jì)算類型三個(gè)不同方面對(duì)數(shù)據(jù)流的模型進(jìn)行歸納和描述。實(shí)際上，近年來很多文章提出了各種各樣的數(shù)據(jù)流模型，我們并沒有包括所有這些模型，只是將其中比較重要的和常見的進(jìn)行了歸納和分類。
　　1.3.1 形式化描述
　　以下是對(duì)數(shù)據(jù)流的一個(gè)形式化描述。
　　考慮向量α，其屬性的域?yàn)閇1..n](秩為n)，而且向量α在時(shí)間t的狀態(tài)
　　α(t)=<α1(t), ...αi(t), ...αn(t) >
　　。在時(shí)刻s，α是0向量，即對(duì)于所有i，αi(s)=0。對(duì)向量的各個(gè)分量的更新是以二元組流的形式出現(xiàn)的。即，第t個(gè)更新為(i, ct)，意味著αi(t)= αi(t . 1) + ct，且對(duì)于i. =.i，αi. (t)= αi. (t . 1)。在時(shí)刻t發(fā)生的查詢是針對(duì)α(t)的。
　　1.3.2 數(shù)據(jù)集合
　　我們首先考慮在進(jìn)行數(shù)據(jù)流計(jì)算時(shí)，有哪些數(shù)據(jù)被包含在計(jì)算范圍之內(nèi)。關(guān)于這個(gè)問題，主要有三種不同的模型：分別是數(shù)據(jù)流模型（data stream model）、滑動(dòng)窗口模型（sliding window model）和n-of-N模型。
　　數(shù)據(jù)流模型（data stream model）在數(shù)據(jù)流模型中，從某個(gè)特定時(shí)間開始至今的所有數(shù)據(jù)都要被納入計(jì)算范圍。此時(shí)，s=0，即在時(shí)刻0，α是0向量。即這是數(shù)據(jù)流最初和最普遍的模型。
　　滑動(dòng)窗口模型（sliding window model ，計(jì)算最近的N個(gè)數(shù)據(jù)）滑動(dòng)窗口模型是指，從計(jì)算時(shí)算起，向前追溯的N個(gè)數(shù)據(jù)要被納入計(jì)算范圍。此時(shí)，s = t . N，即在時(shí)刻t . N，α是0向量。換句話說，要計(jì)算最近的N個(gè)數(shù)據(jù)。由于數(shù)據(jù)流的數(shù)據(jù)是不斷涌現(xiàn)的，所以直觀的看，這種模式就像用一個(gè)不變的窗口，數(shù)據(jù)隨時(shí)間的推移經(jīng)過窗口，出現(xiàn)在窗口內(nèi)的數(shù)據(jù)就是被計(jì)算的數(shù)據(jù)集合。M. Datar等[91]首先提出這一模式，隨后得到了廣泛響應(yīng)[92]。
　　n-of-N模型(計(jì)算最近的n個(gè)數(shù)據(jù)，其中0 <n ≤ N) 文獻(xiàn)[93] 提出的這種模型建立在滑動(dòng)窗口模型的基礎(chǔ)之上，比滑動(dòng)窗口模型更為靈活：被納入計(jì)算范圍的是從計(jì)算時(shí)算起，向前追溯的n個(gè)數(shù)據(jù)。此時(shí)，s = t . n，即在時(shí)刻t . n，α是0向量。注意，其中n ≤ N，而且是可以隨查詢要求變化的。而在滑動(dòng)窗口模型中，n = N而且是固定不變的。對(duì)于數(shù)據(jù)流處理系統(tǒng)來說，要能夠回答所有長(zhǎng)度小于等于N的滑動(dòng)窗口問題。
　　1.3.3 數(shù)據(jù)屬性
　　我們?cè)趤砜匆幌聰?shù)據(jù)本身的特征。
　　時(shí)間序列（time series model） 數(shù)據(jù)按照其屬性(實(shí)際上就是時(shí)間)的順序前來。在這種情況下，i = t，即一個(gè)t時(shí)刻的更新為(t, ct)。此時(shí)對(duì)α的更新操作為αt(t)= ct， 且對(duì)于i. =.t，αi. (t)= αi. (t . 1)。這種模型適用于時(shí)序數(shù)據(jù)，如某特定IP的傳出的數(shù)據(jù)，或股票的定期更新數(shù)據(jù)等。
　　收款機(jī)模型（cash register model） 同一屬性的數(shù)據(jù)相加，數(shù)據(jù)為正。在這種模型中，ct >=0。這意味著對(duì)于所有的i和t來說，αi(t)總是不小于零，而且是遞增的。實(shí)際上，這種模型被認(rèn)為是最常用的，例如可以用于對(duì)收款機(jī)（收款機(jī)模型由此得名），各個(gè)IP的網(wǎng)絡(luò)傳輸量，手機(jī)用戶的通話時(shí)長(zhǎng)的監(jiān)控等等。
　　十字轉(zhuǎn)門模型（turnstile model） 同一屬性的數(shù)據(jù)相加，數(shù)據(jù)為正或負(fù)。在這種模型中，ct可以大于0也可以小于0。這是最通用的模型。S. Muthukrishnan[89]稱其為十字轉(zhuǎn)門模型起因于這種模型的功能就象地鐵站的十字轉(zhuǎn)門，可以用來計(jì)算有多少人到達(dá)和離開，從而得出地鐵中的人數(shù)。
　　1.3.4 計(jì)算類型
　　對(duì)數(shù)據(jù)流數(shù)據(jù)的計(jì)算可以分為兩類：基本計(jì)算和復(fù)雜計(jì)算。目前，基本計(jì)算主要包括對(duì)點(diǎn)查詢、范圍查詢和內(nèi)積查詢這三種查詢的計(jì)算。復(fù)雜計(jì)算包括對(duì)分位數(shù)的計(jì)算、頻繁項(xiàng)的計(jì)算以及數(shù)據(jù)挖掘等。
　　點(diǎn)查詢（Point query） 返回αi(t)的值。
　　范圍查詢（Range query） 對(duì)于范圍查詢Q(f, t)，返回
　　t
　　. αi(t)
　　i=f
　　內(nèi)積（Inner product） 對(duì)于向量β，α與β的內(nèi)積
　　α . β =Σni=1αi(t)βi
　　分位數(shù)（Quantile） 給定一個(gè)序號(hào)r，返回值v，并確保v在α中的真實(shí)排序r.符合以下要求：
　　r . εN ≤ r. ≤ r + εN
　　其中，ε是精度，N =Σni=1αi(t)。
　　G. S. Manku等[94]提供了對(duì)分位數(shù)進(jìn)行一遍掃描進(jìn)行近似估計(jì)的框架結(jié)構(gòu)，將數(shù)據(jù)集合看成樹的節(jié)點(diǎn)，這些節(jié)點(diǎn)擁有不同的權(quán)重（如節(jié)點(diǎn)中包含的數(shù)據(jù)個(gè)數(shù)）。認(rèn)為所有的分位數(shù)的估計(jì)算法都可以被認(rèn)為由三個(gè)對(duì)節(jié)點(diǎn)的操作組成產(chǎn)生新節(jié)點(diǎn)（NEW） 、合并（COLLAPSE）和輸出（OUTPUT）。不同的策略構(gòu)成了不同類型的樹。這個(gè)框架結(jié)構(gòu)成為后來很多分位數(shù)估計(jì)算法的基礎(chǔ)。
　　頻繁項(xiàng)（Frequent items）有時(shí)也稱Heavy hitters，即找出在數(shù)據(jù)流中頻繁出現(xiàn)的項(xiàng)。在這種計(jì)算中，實(shí)際上令ct =1。這樣，αi(t)中保存了截至t時(shí)刻，維值等于i的數(shù)據(jù)到達(dá)的頻率。對(duì)這些數(shù)據(jù)的查詢又可分為兩種：
　　找出頭k個(gè)最頻繁出現(xiàn)的項(xiàng)
　　.
　　找出所有出現(xiàn)頻率大于1/k的項(xiàng)
　　目前對(duì)頻率項(xiàng)的研究主要集中在后一種計(jì)算[95]。
　　挖掘?qū)��?shù)據(jù)流數(shù)據(jù)進(jìn)行挖掘涉及更復(fù)雜的計(jì)算。近年來對(duì)這方面的研究包括：多維分析[96]，分類分析[97, 98]，聚類分析[99–102]，以及其他one-pass算法[103]。
　　2 相關(guān)工作
　　數(shù)據(jù)流處理過程中的主要難點(diǎn)在于如何將存儲(chǔ)數(shù)據(jù)所花費(fèi)的空間控制在一定范圍之內(nèi)。查詢響應(yīng)時(shí)間問題雖然也很重要，但相對(duì)容易解決。作為近年來研究領(lǐng)域的一個(gè)熱點(diǎn)，數(shù)據(jù)流處理問題得到了廣泛的研究，出現(xiàn)了很多算法。
　　解決數(shù)據(jù)流龐大的數(shù)據(jù)量與有限的存儲(chǔ)空間之間的矛盾的一個(gè)思路是使用采樣，另一個(gè)思路是，構(gòu)造一個(gè)小的、能提供近似結(jié)果的數(shù)據(jù)結(jié)構(gòu)存放壓縮的數(shù)據(jù)流數(shù)據(jù)，這個(gè)結(jié)構(gòu)能存放在存儲(chǔ)器中。略圖（Sketch）、直方圖（histogram）和小波（wavelet）實(shí)際上就都是這樣的數(shù)據(jù)結(jié)構(gòu)中最重要的三種。
　　以上方法實(shí)際上大都已用于傳統(tǒng)數(shù)據(jù)庫(kù)領(lǐng)域，問題在于如何將它們應(yīng)用于數(shù)據(jù)流的特殊環(huán)境。
　　2.1 隨機(jī)采樣（Random sampling）
　　隨機(jī)采樣（Random sampling）可以通過抽取少量樣本來捕捉數(shù)據(jù)集合的基本特性。一個(gè)很常見的簡(jiǎn)單方法就是一致性采樣（uniform sample）。作為一個(gè)備選的采樣方法分層采樣（strati.ed sampling）可以減少數(shù)據(jù)的不均勻分布所帶來的誤差。不過，對(duì)于復(fù)雜的分析，普通的采樣算法還是需要太大的空間。
　　對(duì)于數(shù)據(jù)流的一些特殊計(jì)算，已經(jīng)出現(xiàn)了一些有趣的采樣算法。粘采樣（Sticky sampling）[95]用于頻繁項(xiàng)（frequent items）的計(jì)算。粘采樣使用的方法是，在內(nèi)存中存放二元組(i,f)所構(gòu)成的集合S，對(duì)于每到來的一個(gè)數(shù)據(jù)，如果其鍵i已經(jīng)存在于S,則對(duì)應(yīng)的f加1；否則，以1 r 的概率進(jìn)行采樣，如果該項(xiàng)被選中，在S中增加一組（i,1）；每過一段時(shí)間，對(duì)S中的組進(jìn)行一遍掃描，對(duì)其中的值進(jìn)行更新。然后增加r的值；結(jié)束（或用戶要求結(jié)果）時(shí)，輸出所有f.(s-e)N的組。
　　P. Gibbons提出的distinct sampling[104]用于distinct counting ，即找出數(shù)據(jù)流中不同值的個(gè)數(shù)。它使用哈希（hash ）函數(shù)對(duì)每一個(gè)到來的不同值以2.(i+1)的概率映射到級(jí)別i上；如果i ≥內(nèi)存級(jí)別L（L的初始值為0），將其加入內(nèi)存，否則拋棄；內(nèi)存滿時(shí)，將內(nèi)存中級(jí)別為L(zhǎng)的值刪除，并將L加1；最終對(duì)distinct count的估計(jì)為內(nèi)存中不同的值乘以2L。distinct counting是數(shù)據(jù)庫(kù)處理中的一個(gè)老問題，這種算法的優(yōu)點(diǎn)是，通過設(shè)置合適的參數(shù)，可應(yīng)用于帶謂詞的查詢（即對(duì)數(shù)據(jù)流的一個(gè)子集進(jìn)行distinct counting）。
　　采樣算法的缺點(diǎn)是：它們對(duì)異常數(shù)據(jù)不夠敏感。而且，即使它們可以很好的應(yīng)用于普通的數(shù)據(jù)流模型，但如果要用于滑動(dòng)窗口模型（sliding window model）[91] 或n-of-N模型[93]，還需要進(jìn)行較大的修改。
　　2.2 略圖（sketch）
　　構(gòu)造略圖（sketching）是指使用隨機(jī)映射（Random projections）將數(shù)據(jù)流投射在一個(gè)小的存儲(chǔ)空間內(nèi)作為整個(gè)數(shù)據(jù)流的概要，這個(gè)小空間存儲(chǔ)的概要數(shù)據(jù)稱為略圖，可用于近似回答特定的查詢。不同的略圖可用于對(duì)數(shù)據(jù)流的不同Lp范數(shù)的估算，進(jìn)而這些Lp范數(shù)可用于回答其它類型的查詢。如L0范數(shù)可用于估算數(shù)據(jù)流的不同值(distinct count)；L1范數(shù)可用于計(jì)算分位數(shù)（quantile）和頻繁項(xiàng)（frequent items）；L2范數(shù)可用于估算自連接的長(zhǎng)度等等。
　　略圖的概念最早由N. Alon在[105]中提出，從此不斷涌現(xiàn)出各種略圖及其構(gòu)造算法。
　　N. Alon 在[105]中提出的隨機(jī)略圖構(gòu)造（randomized steching）可以用于對(duì)不同Lp范數(shù)的估算，最多需要O(n 1. lg n)的空間。該文更重要的貢獻(xiàn)在于，它還可以以O(shè)(log n + log t)的空間需求估算L2。它的主要思路是，使用哈希函數(shù)，將數(shù)據(jù)屬性的域D中的每一個(gè)元素一致地隨機(jī)映射到zi ∈ {.1+ 1}上，令隨機(jī)變量X = .i αizi，X2就可作為對(duì)L2范數(shù)的估計(jì)。
　　p1
　　S. Guha 等[88]提出的分位數(shù)略圖(quantile sketch) 保持一組形如（vi,gi, Δi）的數(shù)據(jù)結(jié)構(gòu)，rmax(vi) 和rmin(vi)分別是vi可能的排位的最大和最小值。對(duì)于i>j 滿足：
　　vi >vj
　　gi = rmin(vi) . rmin(vi . 1)
　　Δi = rmax(vi) . rmin(vi)
　　隨著數(shù)據(jù)的到來，對(duì)此略圖進(jìn)行相應(yīng)的更新操作，使估算保持在一定的精度之內(nèi)。X. Lin等[93]對(duì)于這個(gè)問題做出了更形式化的描述。
　　若令A(yù)S為一個(gè)從[1..n]中提取的隨機(jī)集合，每一個(gè)元素被提取的概率為1/2。A. Gilbert 等[106]構(gòu)造若干個(gè)AS，將每個(gè)集合中元素值的和稱為隨機(jī)和（random sum）。多個(gè)隨機(jī)和構(gòu)成一個(gè)略圖。對(duì)αi的估算為
　　2E(||AS|| |αi ∈ AS) . ||A||， 其中||A||為數(shù)據(jù)流中所有數(shù)的和。因此，這種略圖可用于估算點(diǎn)查詢的結(jié)果。使用多個(gè)這樣的略圖，可用于估算范圍查詢、分位數(shù)查詢等。略圖技術(shù)實(shí)際上是空間和精度相權(quán)衡的結(jié)果。為保證點(diǎn)查詢結(jié)果的誤差小于εN， 上述略圖需要的空間通常是以ε.2作為系數(shù)的。與此相比較，G. Cormode 等提出的計(jì)數(shù)-最小略圖（Count-Min Sketch ）[19]只需要ε.1系數(shù)的空間。其思路也比較簡(jiǎn)單，使用若干個(gè)哈希函數(shù)將分別數(shù)據(jù)流投射到多個(gè)小的略圖上，回答點(diǎn)查詢時(shí)，每個(gè)略圖分別作答，并選擇值最小的作為答案。以點(diǎn)查詢?yōu)榛�礎(chǔ)，計(jì)數(shù)-最小略圖可以用于其它各種查詢和復(fù)雜計(jì)算。計(jì)數(shù)-最小略圖并不計(jì)算Lp范數(shù)，而是直接計(jì)算出點(diǎn)查詢的結(jié)果，這是它的時(shí)空效率比其它略圖高的原因之一。
　　2.3 直方圖（Histogram）
　　直方圖（histogram）有兩個(gè)含義：一個(gè)是普通意義上的直方圖，是一種用于顯示近似統(tǒng)計(jì)的視覺手段；另外，它還是一種捕捉數(shù)據(jù)的近似分布的數(shù)據(jù)結(jié)構(gòu)/方法。作為后者出現(xiàn)時(shí)時(shí)，直方圖是這樣構(gòu)造的：將數(shù)據(jù)按其屬性分到多個(gè)不相交的子集(稱為桶)并用某種統(tǒng)一的方式近似表示桶中的值[107]。
　　直方圖方法主要用于信號(hào)處理、統(tǒng)計(jì)、圖像處理、計(jì)算機(jī)視覺和數(shù)據(jù)庫(kù)。在數(shù)據(jù)庫(kù)領(lǐng)域，直方圖原先主要用于選擇性估計(jì)（selectivity estimation），用于選擇查詢優(yōu)化和近似查詢處理。直方圖是一種最簡(jiǎn)單、最靈活的近似處理方法，同時(shí)也是最有效的一種。只要解決好數(shù)據(jù)更新問題，就可以將原有的直方圖運(yùn)用到數(shù)據(jù)流處理中。這類根據(jù)新的數(shù)據(jù)自動(dòng)調(diào)節(jié)的直方圖被稱為動(dòng)態(tài)（或自適應(yīng)/自調(diào)節(jié)）直方圖。
　　L. Fu等[108]提出的直方圖主要用于中值函數(shù)（Median ）和其他分位數(shù)函數(shù)的計(jì)算，可用于近似計(jì)算，也可用于精確查詢。它通過確定性分桶（Deterministic Bucketing ）和隨機(jī)分桶（Randomized Bucketing ）技術(shù)，構(gòu)造多個(gè)不同精度的桶（buckets），然后將輸入數(shù)據(jù)逐級(jí)分到這些桶中，從而完成了動(dòng)態(tài)直方圖的構(gòu)造。
　　由于將靜態(tài)直方圖直接應(yīng)用到數(shù)據(jù)流處理比較困難。S. Guha等[88]雖然可以動(dòng)態(tài)地構(gòu)造近最優(yōu)的V-optimal 直方圖，但只能應(yīng)用于時(shí)間序列模型（time series model） 下的數(shù)據(jù)流。
　　一個(gè)常采用的方法是將整個(gè)算法分為兩步：首先構(gòu)造一個(gè)數(shù)據(jù)流數(shù)據(jù)的略圖；然后從這個(gè)略圖中構(gòu)造合適的直方圖。這種方法可以利用略圖數(shù)據(jù)易于更新的特點(diǎn)，又能實(shí)現(xiàn)直方圖的動(dòng)態(tài)化。N. Thaper等[109]首先是構(gòu)造一個(gè)近似反映數(shù)據(jù)流數(shù)據(jù)的略圖，利用略圖的優(yōu)良的更新性能來實(shí)現(xiàn)數(shù)據(jù)的更新，然后從這個(gè)略圖中導(dǎo)出一個(gè)直方圖來實(shí)現(xiàn)對(duì)數(shù)據(jù)流數(shù)據(jù)的近似。由于從略圖中導(dǎo)出最佳的直方圖是一個(gè)NP-hard問題，作者提供了一個(gè)啟發(fā)式算法(貪婪算法)來搜索一個(gè)較佳的直方圖。
　　A. Gilbert等[110]構(gòu)造了一個(gè)概要的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)使用一組與文獻(xiàn)[106]中類似的隨機(jī)和結(jié)構(gòu)來保存不同粒度級(jí)別的dyadic interval的值。隨后，將不同粒度級(jí)別的dyadic interval（[111]）從大到小地加入所要構(gòu)造的直方圖中，這樣就將近似誤差降到最低（求精）。
　　A. Gilbert等在文獻(xiàn)[112]中主要考慮的是如何降低對(duì)數(shù)據(jù)流中每個(gè)輸入數(shù)據(jù)的處理復(fù)雜度。他們先將輸入數(shù)據(jù)轉(zhuǎn)化為小波系數(shù)（利用小波系數(shù)是信號(hào)與基向量的內(nèi)積），然后采用了與文獻(xiàn)[110]類似的dyadic interval處理方法。略圖與直方圖有很密切的聯(lián)系，從某種方面來說，可以認(rèn)為直方圖是略圖的一種特殊情況。
　　2.4 小波（Wavelet）
　　小波變換（wavelet transformation）常用于生成數(shù)據(jù)的概要信息。這是因?yàn)橥ǔＰ〔ㄏ禂?shù)只有很少一部分是重要的，大部分系數(shù)或者值很小，或者本身不重要。所以，如果忽略數(shù)據(jù)經(jīng)過小波變換后生成的不重要系數(shù)，就可以使用很少的空間完成對(duì)原數(shù)據(jù)的近似。
　　Y. Matias等[113] 首先針對(duì)數(shù)據(jù)流數(shù)據(jù)構(gòu)造一個(gè)直方圖，使用小波對(duì)其進(jìn)行模擬。隨后保留若干最重要的小波系數(shù)實(shí)現(xiàn)對(duì)直方圖的模擬。當(dāng)新的數(shù)據(jù)出現(xiàn)時(shí)，通過對(duì)這些小波系數(shù)進(jìn)行更新以實(shí)現(xiàn)直方圖的更新。
　　文獻(xiàn)[113]提出的實(shí)際上是一種直方圖方法，只不過使用了小波變換。A. Gilbert等[114]指出小波變換可以認(rèn)為是信號(hào)與一組正交的長(zhǎng)度為N的向量集合所作的內(nèi)積，因此構(gòu)造一組數(shù)據(jù)流數(shù)據(jù)的略圖，由于略圖可以相當(dāng)容易和準(zhǔn)確地計(jì)算信號(hào)與一組向量的內(nèi)積，則可以從略圖計(jì)算出小波系數(shù)，從而用于點(diǎn)查詢和范圍查詢的估計(jì)。
　　2.5 新動(dòng)向
　　近年來研究人員對(duì)數(shù)據(jù)流處理的研究不斷深入，我們認(rèn)為出現(xiàn)了以下新的動(dòng)向：
　　2.5.1 引入更多多的的統(tǒng)計(jì)
　　計(jì)技技術(shù)來構(gòu)造略圖
　　G. Cormode等[115]主要處理對(duì)頻繁項(xiàng)的計(jì)算。它以前人的主項(xiàng)（majority item ） 算法([116, 117])為基礎(chǔ)，使用了error-correcting codes來處理問題。如數(shù)據(jù)的每一位設(shè)立一個(gè)計(jì)數(shù)器，再根據(jù)這些計(jì)數(shù)器的計(jì)數(shù)結(jié)果來推斷頻繁項(xiàng)集合。
　　Y. Tao等[118]實(shí)質(zhì)上是對(duì)Probabilistic counting [119] (已經(jīng)廣泛地用于數(shù)據(jù)庫(kù)領(lǐng)域的distinct counting)在數(shù)據(jù)流處理的一種應(yīng)用。
　　2.5.2 對(duì)略圖進(jìn)行擴(kuò)展，以處理更更復(fù)復(fù)雜的查詢?cè)冃栊枨?BR> 　　Lin等在文獻(xiàn)[93]中構(gòu)造了一個(gè)復(fù)雜的略圖體系，可用于滑動(dòng)窗口模型（sliding window model ）和n-of-N模型的分位數(shù)估計(jì)，這是簡(jiǎn)單略圖難以做到的。
　　在滑動(dòng)窗口模型下，文獻(xiàn)[93]將數(shù)據(jù)按時(shí)間順序分為多個(gè)桶，在每個(gè)桶中建立略圖（精度比要求的高），然后查詢時(shí)再將這些略圖合并（merge），其中對(duì)最后一個(gè)桶可能需要進(jìn)行提升（lift ）操作。維護(hù)時(shí)只刪除過期的桶，增加新的桶。
　　在n-of-N model中，文獻(xiàn)[93]將數(shù)據(jù)按EH Partitioning技術(shù)分為多個(gè)大小不同的桶，在每個(gè)桶中建立略圖（精度比要求的高），然后查詢時(shí)再將其中一部分略圖合并，可以保證要求的精度，其中對(duì)最后一個(gè)同可能需要進(jìn)行提升。
　　2.5.3 與時(shí)空數(shù)據(jù)處理的進(jìn)一步結(jié)合
　　J. Sun等在文獻(xiàn)[120]中雖然主要針對(duì)時(shí)空數(shù)據(jù)的歷史查詢和預(yù)測(cè)處理。然而，文章卻強(qiáng)調(diào)時(shí)空數(shù)據(jù)是以數(shù)據(jù)流的形式出現(xiàn)的，處理中也更著重于時(shí)空數(shù)據(jù)的更新性能。
　　Y. Tao等[118]使用數(shù)據(jù)流的方法處理時(shí)空數(shù)據(jù)，通過對(duì)動(dòng)態(tài)的時(shí)空數(shù)據(jù)構(gòu)造略圖，用于分辨物體是否在多個(gè)區(qū)域間運(yùn)動(dòng)或靜止的狀態(tài)，并估算其數(shù)量。而這種問題在原先的時(shí)空處理中是很難解決的。

• 通信詞典解釋