數(shù)據(jù)流

詞語(yǔ)解釋

數(shù)據(jù)流是指在通信中，消息的發(fā)送者和接收者之間傳輸?shù)臄?shù)據(jù)流，它是一種半雙工的數(shù)據(jù)傳輸方式，只能在一個(gè)方向上傳輸，另一個(gè)方向上不能傳輸。數(shù)據(jù)流是一種非常重要的通信方式，它可以實(shí)現(xiàn)實(shí)時(shí)的數(shù)據(jù)傳輸，可以有效地滿(mǎn)足用戶(hù)的實(shí)時(shí)通信需求。它的應(yīng)用在很多領(lǐng)域都得到了廣泛的應(yīng)用，如視頻會(huì)議、網(wǎng)絡(luò)電話(huà)、視頻監(jiān)控等。在視頻會(huì)議系統(tǒng)中，數(shù)據(jù)流的應(yīng)用可以實(shí)現(xiàn)參會(huì)者之間的實(shí)時(shí)交流，可以實(shí)現(xiàn)視頻、語(yǔ)音、文字等多種形式的實(shí)時(shí)交流，可以滿(mǎn)足不同用戶(hù)的需求。在網(wǎng)絡(luò)電話(huà)系統(tǒng)中，數(shù)據(jù)流的應(yīng)用可以實(shí)現(xiàn)用戶(hù)之間的實(shí)時(shí)通話(huà)，可以實(shí)現(xiàn)語(yǔ)音、文字等多種形式的實(shí)時(shí)交流，可以滿(mǎn)足不同用戶(hù)的需求。在視頻監(jiān)控系統(tǒng)中，數(shù)據(jù)流的應(yīng)用可以實(shí)現(xiàn)實(shí)時(shí)監(jiān)控，可以實(shí)現(xiàn)視頻、圖片等多種形式的實(shí)時(shí)監(jiān)控，可以滿(mǎn)足不同用戶(hù)的需求。總之，數(shù)據(jù)流在通信中的應(yīng)用是非常廣泛的，它可以實(shí)現(xiàn)實(shí)時(shí)的數(shù)據(jù)傳輸，可以滿(mǎn)足不同用戶(hù)的需求，是通信中不可或缺的一種重要的數(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ù)。這類(lèi)數(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ú)線(xiàn)通信網(wǎng)（通話(huà)記錄）的出現(xiàn)，產(chǎn)生了大量的數(shù)據(jù)流類(lèi)型的數(shù)據(jù)。我們注意到這類(lèi)數(shù)據(jù)大都與地理信息有一定關(guān)聯(lián)，這主要是因?yàn)榈乩硇畔⒌木S度較大，容易產(chǎn)生這類(lèi)大量的細(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ù)流是指“以非常高的速度到來(lái)的輸入數(shù)據(jù)”，因此對(duì)數(shù)據(jù)流數(shù)據(jù)的傳輸、計(jì)算和存儲(chǔ)都將變得很困難。在這種情況下，只有在數(shù)據(jù)最初到達(dá)時(shí)有機(jī)會(huì)對(duì)其進(jìn)行一次處理，其他時(shí)候很難再存取到這些數(shù)據(jù)（因?yàn)闆](méi)有也無(wú)法保存這些數(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)無(wú)法控制所處理的數(shù)據(jù)的到達(dá)順序；
　　3. 數(shù)據(jù)可能是無(wú)限多的；
　　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è)備來(lái)說(shuō)都是一個(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ù)流無(wú)法在內(nèi)存或硬盤(pán)中存儲(chǔ)的主要原因。如果維度小，即使到來(lái)的數(shù)據(jù)量很大，也可以在較小的存儲(chǔ)器中保存這些數(shù)據(jù)。例如，對(duì)于無(wú)線(xiàn)通信網(wǎng)來(lái)說(shuō)，同樣的100萬(wàn)條通話(huà)記錄，如果只有1000個(gè)用戶(hù)，那么使用1000個(gè)存儲(chǔ)單位就可以保存足夠多和足夠精確的數(shù)據(jù)來(lái)回答“某一用戶(hù)的累計(jì)通話(huà)時(shí)間有多長(zhǎng)”的問(wèn)題；而如果共有100000個(gè)用戶(hù)，要保存這些信息，就需要100000個(gè)存儲(chǔ)單位。而目前數(shù)據(jù)流數(shù)據(jù)的屬性大多與地理信息、IP地址、手機(jī)號(hào)碼等有關(guān)，而且往往與時(shí)間聯(lián)系在一起。這時(shí)，數(shù)據(jù)的維度遠(yuǎn)遠(yuǎn)超過(guò)了內(nèi)存和硬盤(pán)容量，這意味著系統(tǒng)無(wú)法完整保存這些信息，通常只能在數(shù)據(jù)到達(dá)的時(shí)候存取數(shù)據(jù)一次。
　　數(shù)據(jù)到達(dá)的時(shí)間—持續(xù) 數(shù)據(jù)的持續(xù)到達(dá)意味著數(shù)據(jù)量可能是無(wú)限的。而且，對(duì)數(shù)據(jù)進(jìn)行處理的結(jié)果不會(huì)是最終的結(jié)果，因?yàn)閿?shù)據(jù)還會(huì)不斷地到達(dá)。因此，對(duì)數(shù)據(jù)流的查詢(xún)的結(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é)果的要求從過(guò)去的“精確”改為“近似”后，實(shí)現(xiàn)數(shù)據(jù)流查詢(xún)的快速響應(yīng)也就成為了可能。
　　1.3 模型
　　我們?cè)噲D從數(shù)據(jù)集合、數(shù)據(jù)屬性和計(jì)算類(lèi)型三個(gè)不同方面對(duì)數(shù)據(jù)流的模型進(jìn)行歸納和描述。實(shí)際上，近年來(lái)很多文章提出了各種各樣的數(shù)據(jù)流模型，我們并沒(méi)有包括所有這些模型，只是將其中比較重要的和常見(jiàn)的進(jìn)行了歸納和分類(lèi)。
　　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ā)生的查詢(xún)是針對(duì)α(t)的。
　　1.3.2 數(shù)據(jù)集合
　　我們首先考慮在進(jìn)行數(shù)據(jù)流計(jì)算時(shí)，有哪些數(shù)據(jù)被包含在計(jì)算范圍之內(nèi)。關(guān)于這個(gè)問(wèn)題，主要有三種不同的模型：分別是數(shù)據(jù)流模型（data stream model）、滑動(dòng)窗口模型（sliding window model）和n-of-N模型。
　　數(shù)據(jù)流模型（data stream model）在數(shù)據(jù)流模型中，從某個(gè)特定時(shí)間開(kāi)始至今的所有數(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向量。換句話(huà)說(shuō)，要計(jì)算最近的N個(gè)數(shù)據(jù)。由于數(shù)據(jù)流的數(shù)據(jù)是不斷涌現(xiàn)的，所以直觀的看，這種模式就像用一個(gè)不變的窗口，數(shù)據(jù)隨時(shí)間的推移經(jīng)過(guò)窗口，出現(xiàn)在窗口內(nèi)的數(shù)據(jù)就是被計(jì)算的數(shù)據(jù)集合。M. Datar等[91]首先提出這一模式，隨后得到了廣泛響應(yīng)[92]。
　　n-of-N模型(計(jì)算最近的n個(gè)數(shù)據(jù)，其中0 　　1.3.3 數(shù)據(jù)屬性
　　我們?cè)趤?lái)看一下數(shù)據(jù)本身的特征。
　　時(shí)間序列（time series model）數(shù)據(jù)按照其屬性(實(shí)際上就是時(shí)間)的順序前來(lái)。在這種情況下，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來(lái)說(shuō)，αi(t)總是不小于零，而且是遞增的。實(shí)際上，這種模型被認(rèn)為是最常用的，例如可以用于對(duì)收款機(jī)（收款機(jī)模型由此得名），各個(gè)IP的網(wǎng)絡(luò)傳輸量，手機(jī)用戶(hù)的通話(huà)時(shí)長(zhǎng)的監(jiān)控等等。
　　十字轉(zhuǎn)門(mén)模型（turnstile model）同一屬性的數(shù)據(jù)相加，數(shù)據(jù)為正或負(fù)。在這種模型中，ct可以大于0也可以小于0。這是最通用的模型。S. Muthukrishnan[89]稱(chēng)其為十字轉(zhuǎn)門(mén)模型起因于這種模型的功能就象地鐵站的十字轉(zhuǎn)門(mén)，可以用來(lái)計(jì)算有多少人到達(dá)和離開(kāi)，從而得出地鐵中的人數(shù)。
　　1.3.4 計(jì)算類(lèi)型
　　對(duì)數(shù)據(jù)流數(shù)據(jù)的計(jì)算可以分為兩類(lèi)：基本計(jì)算和復(fù)雜計(jì)算。目前，基本計(jì)算主要包括對(duì)點(diǎn)查詢(xún)、范圍查詢(xún)和內(nèi)積查詢(xún)這三種查詢(xún)的計(jì)算。復(fù)雜計(jì)算包括對(duì)分位數(shù)的計(jì)算、頻繁項(xiàng)的計(jì)算以及數(shù)據(jù)挖掘等。
　　點(diǎn)查詢(xún)（Point query）返回αi(t)的值。
　　范圍查詢(xún)（Range query）對(duì)于范圍查詢(xún)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ù)集合看成樹(shù)的節(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)成了不同類(lèi)型的樹(shù)。這個(gè)框架結(jié)構(gòu)成為后來(lái)很多分位數(shù)估計(jì)算法的基礎(chǔ)。
　　頻繁項(xiàng)（Frequent items）有時(shí)也稱(chēng)Heavy hitters，即找出在數(shù)據(jù)流中頻繁出現(xiàn)的項(xiàng)。在這種計(jì)算中，實(shí)際上令ct =1。這樣，αi(t)中保存了截至t時(shí)刻，維值等于i的數(shù)據(jù)到達(dá)的頻率。對(duì)這些數(shù)據(jù)的查詢(xún)又可分為兩種：
　　找出頭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ì)算。近年來(lái)對(duì)這方面的研究包括：多維分析[96]，分類(lèi)分析[97, 98]，聚類(lèi)分析[99–102]，以及其他one-pass算法[103]。
　　2 相關(guān)工作
　　數(shù)據(jù)流處理過(guò)程中的主要難點(diǎn)在于如何將存儲(chǔ)數(shù)據(jù)所花費(fèi)的空間控制在一定范圍之內(nèi)。查詢(xún)響應(yīng)時(shí)間問(wèn)題雖然也很重要，但相對(duì)容易解決。作為近年來(lái)研究領(lǐng)域的一個(gè)熱點(diǎn)，數(shù)據(jù)流處理問(wèn)題得到了廣泛的研究，出現(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)域，問(wèn)題在于如何將它們應(yīng)用于數(shù)據(jù)流的特殊環(huán)境。
　　2.1 隨機(jī)采樣（Random sampling）
　　隨機(jī)采樣（Random sampling）可以通過(guò)抽取少量樣本來(lái)捕捉數(shù)據(jù)集合的基本特性。一個(gè)很常見(jiàn)的簡(jiǎn)單方法就是一致性采樣（uniform sample）。作為一個(gè)備選的采樣方法分層采樣（strati.ed sampling）可以減少數(shù)據(jù)的不均勻分布所帶來(lái)的誤差。不過(guò)，對(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ì)于每到來(lái)的一個(gè)數(shù)據(jù)，如果其鍵i已經(jīng)存在于S,則對(duì)應(yīng)的f加1；否則，以1 r 的概率進(jìn)行采樣，如果該項(xiàng)被選中，在S中增加一組（i,1）；每過(guò)一段時(shí)間，對(duì)S中的組進(jìn)行一遍掃描，對(duì)其中的值進(jìn)行更新。然后增加r的值；結(jié)束（或用戶(hù)要求結(jié)果）時(shí)，輸出所有f.(s-e)N的組。
　　P. Gibbons提出的distinct sampling[104]用于distinct counting ，即找出數(shù)據(jù)流中不同值的個(gè)數(shù)。它使用哈希（hash ）函數(shù)對(duì)每一個(gè)到來(lái)的不同值以2.(i+1)的概率映射到級(jí)別i上；如果i ≥內(nèi)存級(jí)別L（L的初始值為0），將其加入內(nèi)存，否則拋棄；內(nèi)存滿(mǎn)時(shí)，將內(nèi)存中級(jí)別為L(zhǎng)的值刪除，并將L加1；最終對(duì)distinct count的估計(jì)為內(nèi)存中不同的值乘以2L。distinct counting是數(shù)據(jù)庫(kù)處理中的一個(gè)老問(wèn)題，這種算法的優(yōu)點(diǎn)是，通過(guò)設(shè)置合適的參數(shù)，可應(yīng)用于帶謂詞的查詢(xún)（即對(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ù)稱(chēng)為略圖，可用于近似回答特定的查詢(xún)。不同的略圖可用于對(duì)數(shù)據(jù)流的不同Lp范數(shù)的估算，進(jìn)而這些Lp范數(shù)可用于回答其它類(lèi)型的查詢(xún)。如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 滿(mǎn)足：
　　vi >vj
　　gi = rmin(vi) . rmin(vi . 1)
　　Δi = rmax(vi) . rmin(vi)
　　隨著數(shù)據(jù)的到來(lái)，對(duì)此略圖進(jìn)行相應(yīng)的更新操作，使估算保持在一定的精度之內(nèi)。X. Lin等[93]對(duì)于這個(gè)問(wèn)題做出了更形式化的描述。
　　若令A(yù)S為一個(gè)從[1..n]中提取的隨機(jī)集合，每一個(gè)元素被提取的概率為1/2。A. Gilbert 等[106]構(gòu)造若干個(gè)AS，將每個(gè)集合中元素值的和稱(chēng)為隨機(jī)和（random sum）。多個(gè)隨機(jī)和構(gòu)成一個(gè)略圖。對(duì)αi的估算為
　　2E(||AS|| |αi ∈ AS) . ||A||，其中||A||為數(shù)據(jù)流中所有數(shù)的和。因此，這種略圖可用于估算點(diǎn)查詢(xún)的結(jié)果。使用多個(gè)這樣的略圖，可用于估算范圍查詢(xún)、分位數(shù)查詢(xún)等。略圖技術(shù)實(shí)際上是空間和精度相權(quán)衡的結(jié)果。為保證點(diǎn)查詢(xún)結(jié)果的誤差小于εN，上述略圖需要的空間通常是以ε.2作為系數(shù)的。與此相比較，G. Cormode 等提出的計(jì)數(shù)-最小略圖（Count-Min Sketch ）[19]只需要ε.1系數(shù)的空間。其思路也比較簡(jiǎn)單，使用若干個(gè)哈希函數(shù)將分別數(shù)據(jù)流投射到多個(gè)小的略圖上，回答點(diǎn)查詢(xún)時(shí)，每個(gè)略圖分別作答，并選擇值最小的作為答案。以點(diǎn)查詢(xún)?yōu)榛A(chǔ)，計(jì)數(shù)-最小略圖可以用于其它各種查詢(xún)和復(fù)雜計(jì)算。計(jì)數(shù)-最小略圖并不計(jì)算Lp范數(shù)，而是直接計(jì)算出點(diǎn)查詢(xún)的結(jié)果，這是它的時(shí)空效率比其它略圖高的原因之一。
　　2.3 直方圖（Histogram）
　　直方圖（histogram）有兩個(gè)含義：一個(gè)是普通意義上的直方圖，是一種用于顯示近似統(tǒng)計(jì)的視覺(jué)手段；另外，它還是一種捕捉數(shù)據(jù)的近似分布的數(shù)據(jù)結(jié)構(gòu)/方法。作為后者出現(xiàn)時(shí)時(shí)，直方圖是這樣構(gòu)造的：將數(shù)據(jù)按其屬性分到多個(gè)不相交的子集(稱(chēng)為桶)并用某種統(tǒng)一的方式近似表示桶中的值[107]。
　　直方圖方法主要用于信號(hào)處理、統(tǒng)計(jì)、圖像處理、計(jì)算機(jī)視覺(jué)和數(shù)據(jù)庫(kù)。在數(shù)據(jù)庫(kù)領(lǐng)域，直方圖原先主要用于選擇性估計(jì)（selectivity estimation），用于選擇查詢(xún)優(yōu)化和近似查詢(xún)處理。直方圖是一種最簡(jiǎn)單、最靈活的近似處理方法，同時(shí)也是最有效的一種。只要解決好數(shù)據(jù)更新問(wèn)題，就可以將原有的直方圖運(yùn)用到數(shù)據(jù)流處理中。這類(lèi)根據(jù)新的數(shù)據(jù)自動(dòng)調(diào)節(jié)的直方圖被稱(chēng)為動(dòng)態(tài)（或自適應(yīng)/自調(diào)節(jié)）直方圖。
　　L. Fu等[108]提出的直方圖主要用于中值函數(shù)（Median ）和其他分位數(shù)函數(shù)的計(jì)算，可用于近似計(jì)算，也可用于精確查詢(xún)。它通過(guò)確定性分桶（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)良的更新性能來(lái)實(shí)現(xiàn)數(shù)據(jù)的更新，然后從這個(gè)略圖中導(dǎo)出一個(gè)直方圖來(lái)實(shí)現(xiàn)對(duì)數(shù)據(jù)流數(shù)據(jù)的近似。由于從略圖中導(dǎo)出最佳的直方圖是一個(gè)NP-hard問(wèn)題，作者提供了一個(gè)啟發(fā)式算法(貪婪算法)來(lái)搜索一個(gè)較佳的直方圖。
　　A. Gilbert等[110]構(gòu)造了一個(gè)概要的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)使用一組與文獻(xiàn)[106]中類(lèi)似的隨機(jī)和結(jié)構(gòu)來(lái)保存不同粒度級(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]類(lèi)似的dyadic interval處理方法。略圖與直方圖有很密切的聯(lián)系，從某種方面來(lái)說(shuō)，可以認(rèn)為直方圖是略圖的一種特殊情況。
　　2.4 小波（Wavelet）
　　小波變換（wavelet transformation）常用于生成數(shù)據(jù)的概要信息。這是因?yàn)橥ǔＰ〔ㄏ禂?shù)只有很少一部分是重要的，大部分系數(shù)或者值很小，或者本身不重要。所以，如果忽略數(shù)據(jù)經(jīng)過(guò)小波變換后生成的不重要系數(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í)，通過(guò)對(duì)這些小波系數(shù)進(jìn)行更新以實(shí)現(xiàn)直方圖的更新。
　　文獻(xiàn)[113]提出的實(shí)際上是一種直方圖方法，只不過(guò)使用了小波變換。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)查詢(xún)和范圍查詢(xún)的估計(jì)。
　　2.5 新動(dòng)向
　　近年來(lái)研究人員對(duì)數(shù)據(jù)流處理的研究不斷深入，我們認(rèn)為出現(xiàn)了以下新的動(dòng)向：
　　2.5.1 引入更多多的的統(tǒng)計(jì)
　　計(jì)技技術(shù)來(lái)構(gòu)造略圖
　　G. Cormode等[115]主要處理對(duì)頻繁項(xiàng)的計(jì)算。它以前人的主項(xiàng)（majority item ）算法([116, 117])為基礎(chǔ)，使用了error-correcting codes來(lái)處理問(wèn)題。如數(shù)據(jù)的每一位設(shè)立一個(gè)計(jì)數(shù)器，再根據(jù)這些計(jì)數(shù)器的計(jì)數(shù)結(jié)果來(lái)推斷頻繁項(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ù)雜的查詢(xún)?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è)桶中建立略圖（精度比要求的高），然后查詢(xún)時(shí)再將這些略圖合并（merge），其中對(duì)最后一個(gè)桶可能需要進(jìn)行提升（lift ）操作。維護(hù)時(shí)只刪除過(guò)期的桶，增加新的桶。
　　在n-of-N model中，文獻(xiàn)[93]將數(shù)據(jù)按EH Partitioning技術(shù)分為多個(gè)大小不同的桶，在每個(gè)桶中建立略圖（精度比要求的高），然后查詢(xún)時(shí)再將其中一部分略圖合并，可以保證要求的精度，其中對(duì)最后一個(gè)同可能需要進(jìn)行提升。
　　2.5.3 與時(shí)空數(shù)據(jù)處理的進(jìn)一步結(jié)合
　　J. Sun等在文獻(xiàn)[120]中雖然主要針對(duì)時(shí)空數(shù)據(jù)的歷史查詢(xún)和預(yù)測(cè)處理。然而，文章卻強(qiáng)調(diào)時(shí)空數(shù)據(jù)是以數(shù)據(jù)流的形式出現(xiàn)的，處理中也更著重于時(shí)空數(shù)據(jù)的更新性能。
　　Y. Tao等[118]使用數(shù)據(jù)流的方法處理時(shí)空數(shù)據(jù)，通過(guò)對(duì)動(dòng)態(tài)的時(shí)空數(shù)據(jù)構(gòu)造略圖，用于分辨物體是否在多個(gè)區(qū)域間運(yùn)動(dòng)或靜止的狀態(tài)，并估算其數(shù)量。而這種問(wèn)題在原先的時(shí)空處理中是很難解決的。

掃碼付費(fèi)即可復(fù)制

數(shù)據(jù)流

數(shù)據(jù)流

相關(guān)討論貼

相關(guān)技術(shù)問(wèn)答

相關(guān)資料下載

隨機(jī)推薦詞語(yǔ)