錢江波,王志杰,陳華輝,王海斌

（1.寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211；2.寧波市公安局 寧波 315040）

1 引言

傳統(tǒng)的數(shù)據(jù)處理中，數(shù)據(jù)是持久的、確定性的，而查詢是短暫、主動的。然而，隨著技術(shù)的發(fā)展，傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)、云計算等許多新的應(yīng)用領(lǐng)域產(chǎn)生的數(shù)據(jù)是時變的、不確定的、不可預(yù)測的、持續(xù)到達(dá)的，并且需要在線處理。這種數(shù)據(jù)驅(qū)動的新數(shù)據(jù)稱作不確定或概率數(shù)據(jù)流，要求系統(tǒng)能夠在線、連續(xù)、無阻塞地處理。

雖然不確定數(shù)據(jù)流是無限連續(xù)不斷的，但是用戶一般只關(guān)心最近的數(shù)據(jù)，所以可用滑動窗口進(jìn)行限定，即無限數(shù)據(jù)流中時間最近的一個有限子串。執(zhí)行窗口連接操作時，對于數(shù)據(jù)流的每個輸入元組，都要和其他的數(shù)據(jù)流滑動窗口中的元組執(zhí)行連接操作，結(jié)果以數(shù)據(jù)流形式輸出。不確定數(shù)據(jù)流窗口連接是非常重要的操作，具有廣泛的用途，如可實時監(jiān)控套牌車。目前城市中許多攝像設(shè)備(如圖1中A、B、C)監(jiān)控行駛中的車輛，每一輛經(jīng)過的車都會被拍照，并且通過圖像識別技術(shù)可以獲得該車的車牌號。一旦車輛違法，比如超速，根據(jù)車牌號等注冊信息，車主就會受到罰款。為了躲避處罰系統(tǒng)，一些不法分子將自己的沒有牌號的車(如圖1中 D)掛上偽造的其他合法車的牌子(如圖1中 E)。于是，一旦車D違法，那么根據(jù)登記信息，合法車E必將受處罰。文中稱D是套牌車。套牌車具有與真牌車相同的車輛型號、相同的車牌號碼、相同的車身顏色、相同的行駛證等，整套復(fù)制，無法根據(jù)車牌及外觀特征判斷出車輛的真假，因此套牌車的管理難度很大。不確定數(shù)據(jù)流連接可以解決該難題。所有的攝像設(shè)備將車牌、拍攝時間等信息(如圖1中F)連續(xù)地傳到數(shù)據(jù)中心，形成不確定性數(shù)據(jù)流。假設(shè)在時刻1，車輛D經(jīng)過卡口A，那么A處的攝像設(shè)備將識別出的兩個元組(車牌為12345，概率為0.9；車牌為72345，概率為0.1)送到數(shù)據(jù)中心；在時刻7，E經(jīng)過C，C將發(fā)送兩個元組(車牌號12345，概率為0.8；車牌號72345，概率為0.2)。在數(shù)據(jù)中心，A、C處傳出的數(shù)據(jù)流始終在車牌號屬性上執(zhí)行窗口連接(如圖1中 G)。這樣，在數(shù)據(jù)中心將產(chǎn)生具有時間戳之差為6，概率為0.72等屬性的連接后的元組。假設(shè)從A到C駕車最快需要30 min，D、E若是正常行駛，不可能在30 min之內(nèi)出現(xiàn)在兩地，而現(xiàn)在僅用了 6 min，所以D、E是套牌車的概率是 0.8×0.9=0.72。

圖1 利用窗口連接監(jiān)控套牌車

這種大量數(shù)據(jù)流兩兩并發(fā)連接還在傳感網(wǎng)應(yīng)用、網(wǎng)絡(luò)監(jiān)控等領(lǐng)域具有廣泛用途，而且規(guī)模越大，效果越好。但是，大規(guī)模的應(yīng)用也帶來大量的計算，影響了處理的速度。因此，不確定數(shù)據(jù)流并發(fā)連接算法非常重要。

2 相關(guān)工作

數(shù)據(jù)流的連接操作需要將一條流中的每一個元組與其他流中的元組做比較。由于阻塞操作并不適用，因此無限數(shù)據(jù)流上的連接操作一般采用滑動窗口，即兩條流之間的連接只需要在當(dāng)前兩個可用窗口之間進(jìn)行。對稱散列連接算法[1]擴展了傳統(tǒng)散列連接算法，對于每個數(shù)據(jù)源A、B，在內(nèi)存中都維護M個桶。一旦接收到數(shù)據(jù)源A的新元組 T，如散列值為 Hash(T)，則將 T送到 B的 Hash(T)桶進(jìn)行探測。然后，T被存儲到A的Hash(T)桶中。對稱連接算法要求兩個關(guān)系放在內(nèi)存中，X-join算法[2,3]擴展了該算法，可處理存儲在硬盤中的數(shù)據(jù)。X-join算法在內(nèi)存中連接，這一點和對稱散列連接算法一樣。當(dāng)內(nèi)存用盡后，將數(shù)據(jù)源對應(yīng)的最大的桶寫入硬盤。當(dāng)兩個流都阻塞時，X-join算法取出以前存儲在硬盤中的數(shù)據(jù)，然后調(diào)入內(nèi)存進(jìn)行連接。雙管道散列連接算法(DPHJ)[4]是對稱散列連接算法的另一種擴展，分兩個階段執(zhí)行，第一個階段類似對稱散列連接算法和X-join算法，第二個階段稍有不同。DPHJ適合中等大小的數(shù)據(jù)塊，對較大數(shù)據(jù)塊的操作不太理想。PMJ算法[5,6]是傳統(tǒng)排序合并算法的無阻塞版本，主要思想是首先讀入內(nèi)存盡可能多的數(shù)據(jù)，然后把內(nèi)存中的數(shù)據(jù)排序并連接后寫入硬盤。當(dāng)所有數(shù)據(jù)接收后，PMJ算法允許合并的同時進(jìn)行連接操作。散列合并算法(HMJ)[7]也是一種無阻塞連接算法，分為兩個階段：散列階段和合并階段。散列階段使用基于散列的內(nèi)存連接算法，合并階段主要是當(dāng)兩條流阻塞時進(jìn)行的，這時算法從硬盤數(shù)據(jù)調(diào)入內(nèi)存產(chǎn)生連接結(jié)果。DINER算法[8]討論了異構(gòu)網(wǎng)絡(luò)環(huán)境下，數(shù)據(jù)流自適應(yīng)連接的問題，將連接結(jié)果多的數(shù)據(jù)保留在內(nèi)存中，并能快速切換內(nèi)存數(shù)據(jù)連接和磁盤數(shù)據(jù)連接過程。USJ算法[9]是針對兩條不確定數(shù)據(jù)流連接運算的，通過距離來判斷是否能連接，并集成有效剪枝算法增量維護運算結(jié)果[10]。針對不同的傳感數(shù)據(jù)，采用不確定模型描述原始數(shù)據(jù)的不確定性，給出近似的統(tǒng)計方法來獲取數(shù)據(jù)的變化，在時間和空間上都具有很好的效率。

上述文獻(xiàn)沒有討論同時多條并發(fā)數(shù)據(jù)流兩兩連接操作的問題，也沒有考慮不確定數(shù)據(jù)流連接時數(shù)據(jù)溢出時的操作問題，這些都是本文的討論目標(biāo)。

3 定義

此處引入一些概念，這對算法的說明起著很重要的作用。

定義1（不確定性元組）由元組屬性和元組存在概率組成。

定義2 （不確定性數(shù)據(jù)流）不確定性數(shù)據(jù)流U（t,τ）是無限的、實時的、連續(xù)的、有序的元素的集合，其中t是一個不確定性元組，τ是時間戳。若數(shù)據(jù)流本身有序，則時間戳可省略。

定義3 （時間滑動窗口）任意的時刻c，滑動窗口T為數(shù)據(jù)流上定義的一個子集，該子集包含元組的時間戳為c′,滿足 c-c′

定義4 （連續(xù)查詢）是常設(shè)的、持久的、長期運行的、不間斷的查詢。在一段時間內(nèi)，連續(xù)查詢對數(shù)據(jù)流不停地、連續(xù)地執(zhí)行查詢，對新到來的元組執(zhí)行操作，增量式產(chǎn)生新的查詢結(jié)果。

定義5 （連接后的概率）假設(shè)有兩個不確定性元組，和，x和y是概率。如果兩個元組滿足連接條件，連接后的元組是，連接后的概率就是 xy。

定義6 （最快行車時間）若從A點到B點之間的道路距離是S，最高限速是v，那么最快行車時間就是S/v。

定義7 （時間矩陣）矩陣的元素time[x][y]的值是地點x與y之間的最快行車時間組成。

4 內(nèi)存充足情況下的連接算法

4.1 內(nèi)存充足時多線程連接算法

本文以套牌車監(jiān)控為例討論算法。算法采用由一個分發(fā)線程和n個連接線程組成，每個連接線程對應(yīng)一個探測緩沖區(qū)(probe_buffer_i)和一個索引表(ULI)。分發(fā)線程從外部緩沖區(qū)讀入數(shù)據(jù)，若數(shù)據(jù)概率小于設(shè)定概率閾值，那么連接后元組概率肯定小于閾值，則直接丟棄，否則將元組插入到連接線程的探測緩沖區(qū)。

連接線程是最耗時的操作，算法通過散列索引并按概率降序提高查找速度。同時，由于窗口需要刪除過期元組，算法采用插入時順帶(實時)刪除和批量刪除兩種方式。時間矩陣用于判斷連接后元組是否在同一時間窗口內(nèi)。i號連接線程處理其他流與i流的連接運算，因此如果是i流元組進(jìn)入，則需插入，否則需要探測并連接。算法描述如下。

算法1 順帶刪除式連接線程i。

圖2 連接線程

由于順帶刪除窗口內(nèi)過期元組，相對比較繁瑣，也可采用批量刪除。批量刪除是每間隔固定時間遍歷鏈表，刪除過期數(shù)據(jù)。

4.2 內(nèi)存數(shù)據(jù)庫算法

不確定數(shù)據(jù)流窗口連接也可用內(nèi)存數(shù)據(jù)庫實現(xiàn)。圖3是利用內(nèi)存數(shù)據(jù)庫設(shè)計的處理過程，不管規(guī)模多大，實現(xiàn)多條不確定數(shù)據(jù)流窗口連接只需設(shè)置兩張表 (local和illegal)，并通過索引提高速度。

算法描述如下。

算法2 內(nèi)存數(shù)據(jù)庫處理并發(fā)連接。

5 內(nèi)存溢出時替換算法

以上算法是在數(shù)據(jù)流到來的速度小于或等于CPU的處理速度，內(nèi)存足夠容納到來數(shù)據(jù)流的前提下設(shè)計的，若數(shù)據(jù)流速度過高，內(nèi)存容量偏小時，便會造成數(shù)據(jù)丟失，部分?jǐn)?shù)據(jù)溢出。因此當(dāng)內(nèi)存不足時，需從全內(nèi)存的算法切換到硬盤暫存數(shù)據(jù)算法，當(dāng)數(shù)據(jù)流速度降低時，內(nèi)存有富余，再將硬盤暫存數(shù)據(jù)切換回內(nèi)存。

針對不確定數(shù)據(jù)流特點，筆者提出當(dāng)內(nèi)存用完時，將一部分低概率數(shù)據(jù)寫入硬盤的自適應(yīng)調(diào)整策略。具體策略有兩種，期望達(dá)到這樣一個目的：通過在內(nèi)存中保留的數(shù)據(jù)使得得到連接后的數(shù)據(jù)具有較大的概率，也就是優(yōu)先輸出可能性大的數(shù)據(jù)。

5.1 窗口一半策略

第一種策略是將窗口數(shù)據(jù)存儲區(qū)的部分小概率數(shù)據(jù)寫入硬盤，判斷的標(biāo)準(zhǔn)是窗口數(shù)據(jù)存儲區(qū)的容量百分比（如將一半寫入硬盤，簡稱窗口一半策略）。如圖4所示，假設(shè)其他流元組L進(jìn)入內(nèi)存探測前，內(nèi)存已經(jīng)用盡。采用窗口一半策略，需把median指向的各鏈表以后的數(shù)據(jù)都寫入硬盤，這時鏈表中只剩下 A、B、E、F、I，當(dāng)新數(shù)據(jù) L 到來，散列運算到56號索引進(jìn)行探測連接，假設(shè)數(shù)據(jù)L與F、G滿足連接條件，則此時會輸出L、F的連接的結(jié)果，具有的概率是0.81。而G早寫入硬盤無法連接，同時L插入到它自己對應(yīng)的其他卡口的窗口存儲區(qū)。等到數(shù)據(jù)流速度降低時，把寫入硬盤的數(shù)據(jù)G調(diào)入內(nèi)存，這時L與G連接產(chǎn)生的概率為0.765。

圖3 內(nèi)存數(shù)據(jù)庫方案處理過程

圖4 窗口一半策略

算法3 將窗口數(shù)據(jù)存儲區(qū)一半數(shù)據(jù)寫入硬盤算法。

5.2 小于概率策略

數(shù)據(jù)流進(jìn)入窗口數(shù)據(jù)存儲區(qū)中，散列運算到各鏈表的概率都不同，使連接成功存在不同概率，這個概率稱為位置分布概率(prob[i])，其中，具體數(shù)值由統(tǒng)計得到。小于概率策略就是盡可能將不會連接成功的小概率元組淘汰，即將存儲區(qū)中數(shù)據(jù)具有的概率 (data.prob)與prob[i]之積小于或等于設(shè)定寫入概率閾值Probability的數(shù)據(jù)寫入硬盤。在圖5中，令Probability=0.08，那么當(dāng)內(nèi)存用盡時需將鏈表中對應(yīng)的小于或等于0.08的數(shù)據(jù)元素寫入硬盤，即將 C、D、E、F、G、H 寫入硬盤，A、B、I、J、K 留在內(nèi)存中繼續(xù)和新到數(shù)據(jù)做連接操作。

圖5 小于概率策略

由于數(shù)據(jù)是持續(xù)到來的，總是將小于寫入概率Probability的數(shù)據(jù)寫入硬盤。一段時間后，留在內(nèi)存中的數(shù)據(jù)的概率與位置概率之積越來越接近Probability，寫入硬盤的數(shù)據(jù)越來越少，導(dǎo)致內(nèi)存的可用空間越來越小。而且部分新數(shù)據(jù)因小于舊數(shù)據(jù)(甚至已過期)的概率積，無法駐留在內(nèi)存進(jìn)行連接而提前寫入硬盤。為避免這種情況，若寫入硬盤的數(shù)據(jù)量小于窗口數(shù)據(jù)存儲區(qū)的1/M(win_size/M)時，則將窗口中所有數(shù)據(jù)都寫入硬盤。至于M的取值，應(yīng)根據(jù)內(nèi)存容量、處理速度以及數(shù)據(jù)流的速度等歷史統(tǒng)計數(shù)據(jù)決定。

算法4 將小于寫入概率閾值Probability的數(shù)據(jù)寫入硬盤算法。

6 實驗結(jié)果

對上述方案進(jìn)行評估，實驗數(shù)據(jù)分別取真實數(shù)據(jù)、均勻數(shù)據(jù)和高斯數(shù)據(jù)，同時考慮刪除時間間隔、概率閾值、線程數(shù)量3個主要因素。其中真實數(shù)據(jù)是某市24 h交通卡口監(jiān)控數(shù)據(jù)；均勻數(shù)據(jù)利用MATLAB 2008a生成，散列運算到索引后使各個鏈表長度相同，均值為5 000；高斯數(shù)據(jù)也是MATLAB 2008a生成的，散列運算到索引后能使各個鏈表長度滿足高斯曲線形狀，均值為5 000，方差為 50。

實驗用多核計算機的配置為 Intel?CoreTM2 Quad CPU Q8400/2.66 GHz/4 GB/250 GB。內(nèi)存數(shù)據(jù)庫方案的實驗環(huán)境是 Windows XP Professional、Timesten 11內(nèi)存數(shù)據(jù)庫、VC6.0；多線程方案的環(huán)境是 Fedora 13、GCC編譯。

6.1 線程數(shù)量的變化對數(shù)據(jù)處理速度的影響

設(shè)概率閾值為0.7，時間矩陣的元素為60 min，各個處理線程對應(yīng)的探測緩沖區(qū)為300 KB，每個線程的索引表為10 000個索引號，刪除時間間隔為60 min。分別使用均勻、高斯、真實3種數(shù)據(jù)，一個分發(fā)線程，討論分別采用30、60、90、120、150 個處理線程時情況。

從圖6～8可以看出，無論是多線程實時數(shù)據(jù)處理方案還是多線程批量數(shù)據(jù)處理方案，總的趨勢都是隨著卡口數(shù)量（卡口數(shù)量等于處理線程數(shù)量）的增多，數(shù)據(jù)的處理速度降低。這主要是由于線程的運行受硬件配置的影響，在某一段時間內(nèi)，卡口數(shù)量少時，處理線程的數(shù)量也必然少，各個線程運行的次數(shù)相對較多，而卡口數(shù)量增加時，處理線程增加，在同樣的時間段內(nèi)，每個線程獲得的運行次數(shù)就相對減少，但每個線程處理的數(shù)據(jù)量又不會減少，故導(dǎo)致單位時間內(nèi)處理的數(shù)據(jù)量減少，即速度減小。對于Timesten內(nèi)存數(shù)據(jù)庫來說，由算法2可知與卡口數(shù)量無關(guān)，故保持恒定的速度。從圖6～8可以看出，在150個卡口以內(nèi)，多線程方案的處理速度是內(nèi)存數(shù)據(jù)庫方案速度的2～8倍。

圖6 均勻數(shù)據(jù)下卡口數(shù)量變化對數(shù)據(jù)處理速度的影響

圖7 高斯數(shù)據(jù)下卡口數(shù)量變化對數(shù)據(jù)處理速度的影響

圖8 真實數(shù)據(jù)下卡口數(shù)量變化對數(shù)據(jù)處理速度的影響

6.2 刪除時間間隔對數(shù)據(jù)處理速度的影響

設(shè)概率閾值為0.7，時間矩陣的元素為60 min，各個處理線程對應(yīng)的探測緩沖區(qū)為300 KB，每個線程的索引表為10 000個索引號。分別使用均勻、高斯、真實3種數(shù)據(jù)，一個分發(fā)線程，60個處理線程，討論刪除時間間隔分別采用 30、60、90、120、150 min 的情況。

圖9 均勻數(shù)據(jù)下刪除時間間隔變化對數(shù)據(jù)處理速度的影響

圖10 高斯數(shù)據(jù)下刪除時間間隔變化對數(shù)據(jù)處理速度的影響

圖11 真實數(shù)據(jù)下刪除時間間隔變化對數(shù)據(jù)處理速度的影響

從圖9～11可以看出，多線程方案的處理速度都是先增大后減小，其中對真實數(shù)據(jù)和高斯數(shù)據(jù)而言，它們在刪除間隔等于60 min左右時出現(xiàn)速度最高點，對均勻數(shù)據(jù)而言在刪除間隔等于90 min左右時出現(xiàn)速度最高點。多線程批量數(shù)據(jù)處理方案和內(nèi)存數(shù)據(jù)庫方案進(jìn)行過期清理都是掃描全部數(shù)據(jù)，刪除間隔較小時，造成了程序運行過程中頻繁掃描所有數(shù)據(jù)，增大了系統(tǒng)的開銷。隨著刪除間隔的增大，這種系統(tǒng)開銷會相對降低，速度逐漸提高。但是當(dāng)刪除間隔變得很大時，從緩沖區(qū)讀出的新數(shù)據(jù)需要和本地鏈表或存儲表中大量積累的數(shù)據(jù)做比較，這樣無效比較次數(shù)必然增多，故速度又會降低。所以總的速度趨勢就是先增大后減小。但是刪除時間間隔對內(nèi)存數(shù)據(jù)庫影響明顯小于多線程批量數(shù)據(jù)處理方案。對于實時數(shù)據(jù)處理方案而言，它本身就是在插入和探測比較操作前，先判斷插入或比較位置處的數(shù)據(jù)是否過期，即時進(jìn)行過期清理，故和實驗中設(shè)置的刪除間隔大小沒有必然關(guān)系，所以大小一直恒定不變。從這3幅圖可以看出兩種多線程方案明顯優(yōu)于內(nèi)存數(shù)據(jù)庫方案，并且多線程實時數(shù)據(jù)處理方案要略勝于批量數(shù)據(jù)處理方案。

6.3 概率閾值的變化對數(shù)據(jù)處理速度的影響

設(shè)時間矩陣的元素為60 min，各個處理線程對應(yīng)的探測緩沖區(qū)為300 KB，每個線程的索引表為10 000個索引號，刪除時間間隔為60 min。分別使用均勻、高斯、真實3種數(shù)據(jù)，一個分發(fā)線程，60個處理線程，討論概率閾值分別采用 0.7、0.8、0.9 時的情況。

從圖12～14可以看出，3種方案的數(shù)據(jù)處理速度都是隨著概率閾值的增大而升高，這是由于概率閾值越大，程序運行過程中丟棄的數(shù)據(jù)就越多，實際需要進(jìn)一步深入處理的數(shù)據(jù)量減少，于是單位時間內(nèi)數(shù)據(jù)處理讀入數(shù)據(jù)的數(shù)據(jù)量增大，即處理速度提高。兩種多線程方案的處理速度隨著概率閾值的增大，處理速度的增幅要比內(nèi)存數(shù)據(jù)庫方案的增幅要大，并且多線程實時數(shù)據(jù)處理方案比批量數(shù)據(jù)處理方案速度稍高，多線程數(shù)據(jù)處理方案比內(nèi)存數(shù)據(jù)庫處理速度要高。

圖12 均勻數(shù)據(jù)下概率變化對數(shù)據(jù)處理速度的影響

圖13 高斯數(shù)據(jù)下概率變化對數(shù)據(jù)處理速度的影響

圖14 真實數(shù)據(jù)下概率變化對數(shù)據(jù)處理速度的影響

從上述3種實驗的9幅圖可以看出，3種數(shù)據(jù)對內(nèi)存數(shù)據(jù)庫方案的速度基本沒有什么影響，這是由于內(nèi)存數(shù)據(jù)庫將所有的數(shù)據(jù)都存儲在一個本地存儲表中，凡是從緩沖區(qū)讀入的新數(shù)據(jù)，經(jīng)過過濾后，都要按車牌號形成的索引搜索整個表格，數(shù)據(jù)的種類已經(jīng)不會對其產(chǎn)生太大影響。對兩種多線程策略而言，均勻數(shù)據(jù)的處理速度最快，高斯數(shù)據(jù)的處理速度最慢。這是由于多線程的數(shù)據(jù)處理方式是當(dāng)數(shù)據(jù)到來時，首先要根據(jù)對應(yīng)的索引號去確定特定的鏈表，當(dāng)確定了鏈表后，所有的操作僅在該鏈表中進(jìn)行，對于均勻數(shù)據(jù)而言，它形成的所有鏈表的長度基本相同，而高斯數(shù)據(jù)形成的鏈表長度不一，其中間部分偏長，兩端較短，這樣，均勻數(shù)據(jù)在鏈表中進(jìn)行數(shù)據(jù)處理掃描的鏈表平均長度，就明顯比高斯數(shù)據(jù)到來時處理的平均鏈表長度要短，所以說均勻數(shù)據(jù)的處理速度高，高斯的要低。正是因為這個原因，在第二種實驗中均勻數(shù)據(jù)要到達(dá)速度最高點的時刻要稍晚于高斯數(shù)據(jù)。真實數(shù)據(jù)介于均勻數(shù)據(jù)和高斯數(shù)據(jù)之間，所以處理速度也介于兩者之間。

6.4 全在內(nèi)存策略與兩種部分寫入硬盤策略對比實驗

為了能夠使實驗結(jié)果更加明顯，本部分的評估僅使用均勻數(shù)據(jù)作為實驗數(shù)據(jù)，車牌號均勻數(shù)據(jù)是利用MATLAB 2008a生成的、散列運算到索引后能使各個鏈表長度相同的數(shù)據(jù)，均值為1 500，范圍是1 000～1 999，概率數(shù)據(jù)均勻分布在0.5～0.99。時間矩陣的元素為60 min，探測緩沖區(qū)為1 500，每個線程的索引表為1 000個索引號。概率閾值設(shè)為0.7。對于算法3，窗口存儲區(qū)滿后將一半寫入硬盤；對于算法4，因為車牌數(shù)據(jù)是均勻的，每個數(shù)據(jù)散列運算到各個鏈表的概率相同，所以簡化位置概率prob[i]=1,寫入概率閾值Probability=prob[i]×data→prob=data→prob=0.8，N=M=3。

圖15 不同方法在不同時間段輸出結(jié)果平均概率分布

圖16 不同方法在不同時間段輸出結(jié)果數(shù)據(jù)分量分布

從圖15、16可以看出，數(shù)據(jù)全在內(nèi)存的方法最快，因為內(nèi)存充足，所有的操作數(shù)據(jù)均在內(nèi)存，不需要任何的硬盤I/O操作，節(jié)省了大量時間。對于窗口一半算法，內(nèi)存用盡時，一半具有較低概率的數(shù)據(jù)寫入硬盤，留在內(nèi)存的都是具有較大概率的數(shù)據(jù)，通過與它們進(jìn)行連接操作得出的數(shù)據(jù)具有的概率要偏高，圖15中顯示與內(nèi)存中駐留的數(shù)據(jù)發(fā)生連接操作得出的結(jié)果具有較大概率，通過以后調(diào)入硬盤中的數(shù)據(jù)得出的結(jié)果具有較小概率。對于小于概率算法，也得到類似的結(jié)果。但是兩者相比，窗口一半算法中留在內(nèi)存數(shù)據(jù)執(zhí)行連接操作用的時間偏短，這是由于概率均勻分布在0.5～0.99，而0.5～0.7的數(shù)據(jù)已被分發(fā)線程丟棄，這樣進(jìn)入內(nèi)存的數(shù)據(jù)的概率就分布在0.7～0.99，Probability=0.8，也就是說，窗口一半算法留在內(nèi)存的數(shù)據(jù)的概率最小在0.85左右，小于概率算法留在內(nèi)存的數(shù)據(jù)具有的最小概率稍大于0.8，這樣其新數(shù)據(jù)到達(dá)內(nèi)存連接時，和窗口一半算法留在內(nèi)存中的數(shù)據(jù)比較的次數(shù)要少，所以用時偏少，同時得出的違法結(jié)果也少。當(dāng)然，無論是內(nèi)存方法還是硬盤策略，得出的違法結(jié)果是相同的，只是發(fā)現(xiàn)的時間不同，這樣窗口一半算法在硬盤得出的數(shù)據(jù)就比小于概率方法得出的偏多，這分別在圖15、16中可以看出。由于硬盤兩種策略寫入硬盤的數(shù)據(jù)量大致相同，所以它們總時間基本相同，而小于概率算法提前得出的數(shù)據(jù)值偏多，所以推薦使用此方法。

7 結(jié)束語

針對大規(guī)模不確定數(shù)據(jù)流的并發(fā)連接，本文提出了一系列高速在線處理的算法。主要貢獻(xiàn)有：

·提出監(jiān)控套牌車的方法，解決目前無法發(fā)現(xiàn)套牌車的難題；

·設(shè)計實現(xiàn)大規(guī)模并發(fā)連接的算法，為大規(guī)模監(jiān)控套牌車提供基礎(chǔ)；

·提出不確定數(shù)據(jù)流連接操作時，內(nèi)存溢出情況下的數(shù)據(jù)調(diào)度策略，確保概率高的運算結(jié)果及時輸出；

·使用真實數(shù)據(jù)、均勻數(shù)據(jù)、高斯數(shù)據(jù)進(jìn)行實驗評估，證明算法具有良好的性能，其處理速度比內(nèi)存數(shù)據(jù)庫Timesten速度提高2～8倍。

1 Wilschut A N,Apers P M G.Dataflow query execution in a parallel main-memoryenvironment.ProceedingsoftheFirst International Conference on Parallel and Distributed Information Systems,PDIS,Miami,Florida,1991

2 Urhan T,Franklin M J.XJoin:Getting Fast Answers From Slow and Burst Networks. Technical Report CS-TR-3994,UMIACS-TR-99-13,Computer Science Department,University of Maryland,1999

3 Urhan T and Franklin M J.XJoin:a reactively-scheduled pipelined join operator.IEEE Data Engineering Bulletin,2000,23(2):27～33

4 Ives Z G,Florescu D,Friedman M,et al.An adaptive query execution system for data integration.Proceedings of the ACM International Conference on Management of Data,SIGMOD,Philadelphia,PA,1999

5 Dittrich J P,Seeger B,Taylor D S,et al.Progressive merge Join:a generic and non-blocking sort-based Join algorithm.Proceedings of the International Conference on Very Large Data Bases,VLDB,Hong Kong,2002

6 Dittrich J P,Seeger B,Taylor D S,et al.On producing join results early.Proceedings of the ACM Symposium on Principles of Database Systems,PODS,San Diego,CA,2003

7 Mohamed F Mokbel,Ming Lu,Walid G Aref.Hash-merge Join:a non-blocking Join algorithm for producing fast and early Join results.Proceedings of the 20th International Conference on Data Engineering,Boston,MA,USA,2004

8 Mihaela A Bornea,Vasilis Vassalos,Yannis Kotidis,et al.Adaptive Join operators for result rate optimization on streaming inputs.IEEE Transactions on Knowledge and Data Engineering,2010,22(8):1 110～1 125

9 Xiang Lian,Lei Chen.Similarity Join processing on uncertain data streams.IEEE Transactionson Knowledge and Data Engineering,2010,22(10):1 312～1 319

10 Diao Y,Li B,Liu A,et al.Capturing data uncertainty in high-volume stream processing.Proc Conf on Innovative Data Systems Research,Asilomar,CA,USA,2009