不確定數(shù)據(jù)流自適應(yīng)并行連接算法及應(yīng)用*

錢(qián)江波,王志杰,陳華輝,王海斌

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

3 定義

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

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

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

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

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

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

定義6 （最快行車(chē)時(shí)間）若從A點(diǎn)到B點(diǎn)之間的道路距離是S，最高限速是v，那么最快行車(chē)時(shí)間就是S/v。

定義7 （時(shí)間矩陣）矩陣的元素time[x][y]的值是地點(diǎn)x與y之間的最快行車(chē)時(shí)間組成。

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

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

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

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

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

圖2 連接線程

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

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

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

算法描述如下。

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

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

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

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

5.1 窗口一半策略

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

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

圖4 窗口一半策略

算法3 將窗口數(shù)據(jù)存儲(chǔ)區(qū)一半數(shù)據(jù)寫(xiě)入硬盤(pán)算法。

5.2 小于概率策略

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

圖5 小于概率策略

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

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

6 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.4 全在內(nèi)存策略與兩種部分寫(xiě)入硬盤(pán)策略對(duì)比實(shí)驗(yàn)

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

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

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

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

7 結(jié)束語(yǔ)

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

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

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

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

·使用真實(shí)數(shù)據(jù)、均勻數(shù)據(jù)、高斯數(shù)據(jù)進(jìn)行實(shí)驗(yàn)評(píng)估，證明算法具有良好的性能，其處理速度比內(nèi)存數(shù)據(jù)庫(kù)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