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