蔣森安 白 梅 王習(xí)特 李冠宇 史一民

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

Skyline查詢[1]最早是由Borzsonyi等根據(jù)最大向量問題提出的。其被廣泛應(yīng)用于多目標(biāo)決策、數(shù)據(jù)挖掘等領(lǐng)域。作為Skyline查詢的重要變種，動(dòng)態(tài)Skyline首先由Papadias等[2]提出。給定查詢點(diǎn)q，動(dòng)態(tài)Skyline是由所有不被“關(guān)于q動(dòng)態(tài)支配”的點(diǎn)構(gòu)成的集合[3]。具體地，給定查詢點(diǎn)q和兩個(gè)數(shù)據(jù)點(diǎn)p1和p2，p1關(guān)于q動(dòng)態(tài)支配p2是指：在所有的維度上，p1距離q不比p2遠(yuǎn)；同時(shí)，至少在一個(gè)維度上，p1距離q比p2近。通常，距離查詢點(diǎn)q的遠(yuǎn)近可以通過歐氏距離來衡量。

隨著科技的發(fā)展以及數(shù)據(jù)獲取方式的多樣化，數(shù)據(jù)呈爆發(fā)式增長(zhǎng)。集中式環(huán)境下的查詢算法已無法應(yīng)對(duì)處理龐大數(shù)據(jù)量的挑戰(zhàn)。因此，分布式查詢算法應(yīng)運(yùn)而生。本文關(guān)注的是分布式環(huán)境下的動(dòng)態(tài)Skyline查詢處理。

本文研究的分布式動(dòng)態(tài)Skyline查詢?cè)谏钪芯哂泻苤匾囊饬x。例如，股票交易市場(chǎng)每天都會(huì)產(chǎn)生大規(guī)模的股票信息數(shù)據(jù)，而人們想要從這些數(shù)據(jù)中選取優(yōu)質(zhì)股票時(shí)，可以通過對(duì)已知的優(yōu)質(zhì)股票q進(jìn)行動(dòng)態(tài)Skyline查詢，尋找到與q相似的股票。通過對(duì)這些股票信息的分析，可以更加準(zhǔn)確地為用戶推薦具有良好投資價(jià)值的股票。同時(shí)，借助分布式架構(gòu)可以解決集中式環(huán)境無法對(duì)大規(guī)模數(shù)據(jù)進(jìn)行計(jì)算的問題。因此，對(duì)分布式動(dòng)態(tài)Skyline查詢的研究具有很好的實(shí)際應(yīng)用價(jià)值。

在Skyline查詢研究早期，一些經(jīng)典算法已被提出，例如BNL和D&C算法[1]、Bitmap算法和Index算法[4]、NN算法[5]、SFS算法[6]、BBS算法[2]、ZSearch算法[7]等。以上經(jīng)典算法主要針對(duì)集中式環(huán)境下的Skyline查詢。

關(guān)于動(dòng)態(tài)Skyline查詢，文獻(xiàn)[8]提出了一種空間Skyline查詢算法。文獻(xiàn)[9]算法在文獻(xiàn)[8]算法的基礎(chǔ)上提出了一種度量距離函數(shù)，來完成動(dòng)態(tài)Skyline查詢。文獻(xiàn)[10]提出了一種面向海量數(shù)據(jù)的動(dòng)態(tài)Skyline查詢算法。

此外，文獻(xiàn)[11]提出了一種T-Skyline查詢算法。文獻(xiàn)[12]提出了針對(duì)不完全數(shù)據(jù)集的動(dòng)態(tài)Skyline查詢算法。文獻(xiàn)[3]提出了數(shù)據(jù)流上的動(dòng)態(tài)Skyline查詢算法。文獻(xiàn)[13]提出了子空間下的全局Skyline查詢算法。文獻(xiàn)[14]提出了動(dòng)態(tài)數(shù)據(jù)庫上的子空間全局Skyline查詢算法。

目前，分布式Skyline查詢已取得了大量的研究成果[15-17]。這些算法的思想可以歸納為以下三個(gè)步驟：1) 將全局?jǐn)?shù)據(jù)進(jìn)行分區(qū)；2) 計(jì)算各個(gè)分區(qū)的Skyline候選集；3) 合并Skyline候選集得出結(jié)果集。這些算法存在一個(gè)共同的缺點(diǎn)是當(dāng)處理的數(shù)據(jù)量足夠大時(shí)(尤其處理的數(shù)據(jù)呈反相關(guān)分布[2]時(shí))，會(huì)產(chǎn)生瓶頸節(jié)點(diǎn)。此外，文獻(xiàn)[18]提出了一種分布式數(shù)據(jù)庫上的Skyline-join查詢(DSJQ)算法。DSJQ算法利用主從分布式架構(gòu)提出了一種輪轉(zhuǎn)調(diào)度策略來合并計(jì)算各從節(jié)點(diǎn)中的候選集。該策略可以將合并計(jì)算任務(wù)均衡地分配到各從節(jié)點(diǎn)，使每一次的合并結(jié)果分布在各從節(jié)點(diǎn)中。最終，計(jì)算結(jié)束后每個(gè)從節(jié)點(diǎn)保留結(jié)果集的一個(gè)子集。該策略避免了將中間結(jié)果匯總到同一個(gè)節(jié)點(diǎn)進(jìn)行合并計(jì)算，從而解決了瓶頸節(jié)點(diǎn)的問題。

本文關(guān)注的是分布式環(huán)境下的動(dòng)態(tài)Skyline查詢。為了解決此問題，提出分布式動(dòng)態(tài)Skyline查詢(DDSQ)算法。DDSQ算法共分為本地計(jì)算和合并計(jì)算兩個(gè)過程。歸納起來，本文的主要貢獻(xiàn)如下。

1) 本地計(jì)算時(shí)，我們基于B樹索引，提出基礎(chǔ)掃描算法BSAB計(jì)算分布式動(dòng)態(tài)Skyline候選集。BSAB借助B樹索引掃描數(shù)據(jù)，只對(duì)掃描到的數(shù)據(jù)點(diǎn)進(jìn)行動(dòng)態(tài)支配關(guān)系計(jì)算，從而快速得到候選集。

2) 為了進(jìn)一步提高本地計(jì)算候選集的效率，我們基于分布直方圖[13]提出優(yōu)化的掃描算法OSAB，其可通過進(jìn)一步減少掃描空間來提高計(jì)算候選集的效率。

3) 合并計(jì)算時(shí)，我們采用分布式輪轉(zhuǎn)調(diào)度策略[18]，將計(jì)算任務(wù)平均分配到各節(jié)點(diǎn)，使各節(jié)點(diǎn)之間達(dá)到負(fù)載均衡，從而避免了瓶頸節(jié)點(diǎn)的產(chǎn)生。同時(shí)，傳輸數(shù)據(jù)時(shí)，我們將候選集和索引一起傳到指定節(jié)點(diǎn)，利用BSAB快速完成合并計(jì)算。

1 問題定義

給定d維數(shù)據(jù)集合D，用p[i]表示數(shù)據(jù)點(diǎn)p在第i維上的屬性值，且在每個(gè)維度上以小值為優(yōu)。

定義1(動(dòng)態(tài)支配) 給定d維數(shù)據(jù)集D中的兩個(gè)點(diǎn)p1和p2及查詢點(diǎn)q，p1關(guān)于q動(dòng)態(tài)支配p2(記作p1

1) ?i∈{1,2,…,d},|p1[i]-q[i]|≤|p2[i]-q[i]|。

2) ?j∈{1,2,…,d},|p1[j]-q[j]|<|p2[j]-q[j]|。

定義2(動(dòng)態(tài)Skyline) 給定查詢點(diǎn)q和數(shù)據(jù)集D，所有不被其他點(diǎn)動(dòng)態(tài)支配的點(diǎn)構(gòu)成了動(dòng)態(tài)Skyline，記作DSKY(q,D)。其形式化表示為DSKY(q,D)={pi|pi∈D,/?pj∈D且pj

為了表述方便，表1給出了符號(hào)及其含義。

表1 符號(hào)表示及含義

2 分布式動(dòng)態(tài)Skyline查詢算法

DDSQ算法共分為兩個(gè)過程。第一個(gè)過程為本地計(jì)算。當(dāng)接到查詢請(qǐng)求時(shí)，各節(jié)點(diǎn)利用本地掃描算法將本地?cái)?shù)據(jù)集中被動(dòng)態(tài)支配的點(diǎn)過濾，得到分布式動(dòng)態(tài)Skyline候選集。第二個(gè)過程為合并計(jì)算。此過程各節(jié)點(diǎn)依據(jù)輪轉(zhuǎn)策略將候選集發(fā)送到指定節(jié)點(diǎn)完成候選集合并計(jì)算。待所有候選集合并計(jì)算之后，各節(jié)點(diǎn)剩下的數(shù)據(jù)點(diǎn)構(gòu)成了分布式動(dòng)態(tài)Skyline結(jié)果集。

2.1 本地計(jì)算

本小節(jié)主要介紹DDSQ算法的本地計(jì)算過程。首先，我們基于B樹索引提出了基礎(chǔ)掃描算法BSAB。通過BSAB可以減少掃描空間，進(jìn)而提高計(jì)算效率。然后，我們?cè)贐SAB的基礎(chǔ)上基于分布直方圖[13]提出了優(yōu)化的掃描算法OSAB。OSAB可以進(jìn)一步減少掃描空間，提高本地計(jì)算的效率。

2.1.1本地基礎(chǔ)掃描算法

對(duì)于給定d維的數(shù)據(jù)集D和查詢點(diǎn)q，本文對(duì)每個(gè)維度i構(gòu)建一個(gè)B樹索引(記作BTi)。對(duì)數(shù)據(jù)集D構(gòu)建的B樹索引集合表示為BTSet(D)={BT1,BT2,…,BTd}。利用BTi可以快速確定查詢點(diǎn)q在i維上的初始掃描位置。同時(shí)，可以雙向掃描BTi中的葉子節(jié)點(diǎn)。

基于B樹索引，我們提出基礎(chǔ)掃描策略BScanS：1) 選擇掃描維度i：采用循環(huán)的方式掃描所有維度，即對(duì)i維掃描一次后，緊接著掃描i+1維；2) 選擇掃描數(shù)據(jù)點(diǎn)：掃描i維時(shí)，選擇距離q[i]最近的數(shù)據(jù)點(diǎn)進(jìn)行掃描。值得注意的是，當(dāng)距離q[i]最近的數(shù)據(jù)點(diǎn)有多個(gè)時(shí)，需要將這些數(shù)據(jù)點(diǎn)同時(shí)掃描。

在掃描過程中，用參數(shù)p.times來記錄數(shù)據(jù)點(diǎn)被掃描到的次數(shù)。當(dāng)一個(gè)點(diǎn)p被掃描d次時(shí)，我們稱點(diǎn)p為掃描結(jié)束點(diǎn)，記作FSP。

引理1[13]給定數(shù)據(jù)集D中的三個(gè)數(shù)據(jù)點(diǎn)p1、p2、p3，若p1

定理1給定數(shù)據(jù)集D中的點(diǎn)p，對(duì)于掃描維度i，p只可能被在BTi上先于p掃描到的數(shù)據(jù)點(diǎn)動(dòng)態(tài)支配，而p無法動(dòng)態(tài)支配這些點(diǎn)。

證明依據(jù)動(dòng)態(tài)支配的定義很容易證得。

定理2數(shù)據(jù)集D及索引集BTSet(D)，按照BScanS策略掃描BTSet(D)，若找到一個(gè)FSP，則D中所有的動(dòng)態(tài)Skyline點(diǎn)都已被掃描到，掃描策略結(jié)束。

證明假設(shè)存在一個(gè)動(dòng)態(tài)Skyline點(diǎn)p，當(dāng)找到FSP時(shí)沒有被掃描到。而根據(jù)動(dòng)態(tài)支配定義，必定存在一個(gè)維度，p先于FSP被掃描，這與假設(shè)矛盾。定理2得證。

用符號(hào)DSKYi表示i維上掃描到的動(dòng)態(tài)Skyline點(diǎn)集。依據(jù)定理2，當(dāng)掃描策略結(jié)束時(shí)，所有被掃描到的數(shù)據(jù)點(diǎn)構(gòu)成查詢點(diǎn)q的掃描空間，記作ScanS(q)。

算法1給出了BSAB的具體過程。

算法1BSAB

輸入：d維數(shù)據(jù)集D，查詢點(diǎn)q，索引集BTSet(D)。

輸出：動(dòng)態(tài)Skyline結(jié)果集DSKY(q,D)。

1.EndFlag=false；

//算法結(jié)束標(biāo)志

2. 確定q在各個(gè)維度的初始掃描位置；

3. While(True)

4. 依據(jù)BScanS策略選擇維度i，掃描BTi，得數(shù)據(jù)集DSet；

5. For 依次處理DSet中的數(shù)據(jù)點(diǎn)p

6.p.times++；

//統(tǒng)計(jì)點(diǎn)p被掃描的次數(shù)

7. Ifp.times==1

8. 將點(diǎn)p加入ScanS(q)；

//記錄掃描空間

9. Ifp.isDom(q,DSKYi)==false &&p.isDom(q,DSet)==false

//p不被DSKYi和DSet中的點(diǎn)動(dòng)態(tài)支配

10. 將點(diǎn)p加入DSKYi；

11. Ifp.times==d

12.EndFlag=true；

//掃描結(jié)束

13. IfEndFlag==true

14. break；

//結(jié)束循環(huán)，算法結(jié)束

15.DSKY(q,D)=∪i=[1,d]DSKYi；

//得出結(jié)果集

例1如圖1(a)所示，q[x]的初始掃描位置指向p6和p5之間，q[y]的初始掃描位置指向p7和p4之間。依據(jù)BScanS策略，圖1(b)給出了掃描過程。當(dāng)?shù)诙螔呙鑩維時(shí)，同時(shí)掃描到p3、p7，p7被p3動(dòng)態(tài)支配，刪除p7。此時(shí)，p3.times=2，依據(jù)定理2，算法結(jié)束。得到動(dòng)態(tài)Skyline結(jié)果集為DSKY(q,D)=DSKYx∪DSKYy={p3,p4,p6}。

圖1 本地基礎(chǔ)掃描算法BSAB示例

2.1.2本地優(yōu)化掃描算法

BSAB通過循環(huán)掃描各維度的B樹索引，直到找到掃描結(jié)束點(diǎn)。由于BScanS掃描策略會(huì)有部分無須掃描的點(diǎn)被掃描到，因此計(jì)算效率不高。針對(duì)上述問題，我們對(duì)每個(gè)維度分別構(gòu)建一個(gè)分布直方圖[13]來優(yōu)化BScanS掃描策略。共需構(gòu)建d個(gè)分布直方圖，其構(gòu)成的集合表示為H(D)={h1,h2,…,hd}。

圖2 數(shù)據(jù)集及索引

基于區(qū)間密度，我們可以利用式(1)[13]估算出維度i上，分布在x[i]和y[i]之間的數(shù)據(jù)點(diǎn)數(shù)。

(1)

式中：x[i]和y[i]需滿足：x[i]≤y[i]，x[i]∈rm，y[i]∈rn(m≤n)。

對(duì)于掃描到的數(shù)據(jù)點(diǎn)可得到一個(gè)Alldif值，我們將具有最小Alldif值的點(diǎn)稱為最快掃描結(jié)束點(diǎn)，記作pfast。具體地，優(yōu)化后的掃描策略O(shè)ScanS如下。

1) 選擇掃描維度：取pfast.difi最小值對(duì)應(yīng)的維度i作為掃描維度；2) 選擇掃描數(shù)據(jù)點(diǎn)：掃描i維時(shí)，選擇距離q[i]最近的數(shù)據(jù)點(diǎn)進(jìn)行掃描。

算法2給出了優(yōu)化掃描算法OSAB的具體過程。

算法2OSAB

輸入：d維數(shù)據(jù)集D，查詢點(diǎn)q，索引集BTSet(D)。

輸出：動(dòng)態(tài)Skyline結(jié)果集DSKY(q,D)。

1. 初始化pfast=null；

2. 確定q在各個(gè)維度的初始掃描位置；

3. 初始掃描第1維并處理數(shù)據(jù)點(diǎn)，選擇pfast；

4. While(True)

5. 依據(jù)OScanS策略選擇維度i，掃描BTi，得數(shù)據(jù)集DSet；

6. 采用算法1中第5到第13行的過程處理DSet中的數(shù)據(jù)點(diǎn)p，返回算法結(jié)束標(biāo)志符EndFlag；

7. IfEndFlag== true

8. break；

//終止循環(huán)，算法結(jié)束

9. Ifp.Alldif

10. 更新pfast為點(diǎn)p；

11.DSKY(q,D)=∪i=[1,d]DSKYi；

//得到結(jié)果集

值得注意的是，根據(jù)pfast.difi確定掃描維度i后，只有當(dāng)掃描到新的動(dòng)態(tài)Skyline點(diǎn)(第一次掃描且不被動(dòng)態(tài)支配的點(diǎn))，才可能更新pfast。否則，將一直掃描i維，直到當(dāng)前pfast被更新，或者掃描到當(dāng)前pfast(此時(shí)算法結(jié)束)。

例2如圖2(a)給定數(shù)據(jù)集D及查詢點(diǎn)q(8,8)，圖2(b)是x、y維對(duì)應(yīng)的分布直方圖。按照OScanS策略掃描D，其過程如圖3所示。具體地，首先選擇x維掃描得到{p5,p14}，p5被動(dòng)態(tài)支配，此時(shí)pfast=p14，DSKYx={p14}。

圖3 OSAB掃描過程

之后，由pfast確定的掃描維度為y，掃描y維得{p8}，此時(shí)pfast=p14，DSKYy={p8}。按照此方式繼續(xù)掃描，當(dāng)?shù)诙螔呙璧絰維時(shí)，得到{p10,p13}(p13被動(dòng)態(tài)支配)，pfast=p4，DSKYx={p14,p10}。此后，繼續(xù)掃描y維得到{p10,p16}，DSKYy={p8,p9,p4,p10}。此時(shí)p10.times=2，依據(jù)定理2，算法結(jié)束。得到動(dòng)態(tài)Skyline結(jié)果集為DSKY={p4,p8,p9,p10,p14}。

圖3的掃描過程可以得到例2中OSAB的掃描空間為{p4,p5,p8,p9,p10p13,p14,p16}，而BSAB的掃描空間為{p1,p3,…,p10,p12,…,p16}。與BSAB相比，OSAB的掃描空間減小了，從而提高了計(jì)算效率。

2.2 合并計(jì)算

本節(jié)將介紹DDSQ算法的合并計(jì)算過程。關(guān)于候選集合并計(jì)算，目前多數(shù)算法都是按圖4(a)所示的網(wǎng)絡(luò)架構(gòu)將候選集按節(jié)點(diǎn)分組進(jìn)行合并，最終在節(jié)點(diǎn)N0上計(jì)算并存儲(chǔ)分布式動(dòng)態(tài)Skyline結(jié)果集。那么，當(dāng)數(shù)據(jù)規(guī)模足夠大時(shí)，N0將成為瓶頸節(jié)點(diǎn)(將無法計(jì)算并存儲(chǔ)結(jié)果集)。本文采用分布式輪轉(zhuǎn)調(diào)度策略[18]可以將計(jì)算任務(wù)平均地分配到各節(jié)點(diǎn)，以達(dá)到負(fù)載均衡，從而有效避免瓶頸節(jié)點(diǎn)的產(chǎn)生。合并計(jì)算時(shí)我們采用輪轉(zhuǎn)策略來完成節(jié)點(diǎn)之間的數(shù)據(jù)及索引(B樹)的傳輸，并采用2.1.1節(jié)中提出的BSAB完成合并計(jì)算。由于BSAB可以減少掃描空間，因此可提高合并計(jì)算效率。接下來我們將介紹合并計(jì)算過程。

圖4 分布式調(diào)度策略

2.2.1輪轉(zhuǎn)策略

本節(jié)對(duì)輪轉(zhuǎn)策略進(jìn)行簡(jiǎn)單描述，具體過程可查看文獻(xiàn)[18]。

定義3(輪轉(zhuǎn)) 給定一個(gè)偏移量offset，節(jié)點(diǎn)Nu上的候選集CSu將被傳輸?shù)焦?jié)點(diǎn)Nv上。其中，v=(u+offset)%|N|。

如圖4(b)所示，第一次輪轉(zhuǎn)時(shí)，偏移量offset=1，則CS0被傳到節(jié)點(diǎn)N1，CS1被傳到節(jié)點(diǎn)N2，以此類推，CS4被傳到N0。每一次輪轉(zhuǎn)后，需要將計(jì)算結(jié)果原路返回，進(jìn)行數(shù)據(jù)更新。

引理2[18]經(jīng)過多次輪轉(zhuǎn)后，若候選集CSu與其他所有候選集完成合并計(jì)算，則任意候選集CSv，?v∈[0,|N|-1]，完成與其他候選集的合并計(jì)算。

依據(jù)引理2，合并候選集時(shí)，我們只需統(tǒng)計(jì)與CS0完成合并計(jì)算的候選集。當(dāng)CS0完成與其他候選集合并計(jì)算時(shí)，候選集合并計(jì)算結(jié)束。此時(shí)，每個(gè)節(jié)點(diǎn)存儲(chǔ)分布式動(dòng)態(tài)Skyline結(jié)果集的一個(gè)子集。

2.2.2基于輪轉(zhuǎn)策略合并候選集

當(dāng)接到查詢請(qǐng)求后，各節(jié)點(diǎn)首先進(jìn)行本地計(jì)算得到候選集，之后按照輪轉(zhuǎn)策略中的輪轉(zhuǎn)偏移量將候選集發(fā)送到指定節(jié)點(diǎn)，完成候選集合并計(jì)算。

算法3候選集合并過程描述—DDSQ合并計(jì)算

輸入：候選集CSu(v)，查詢點(diǎn)q，索引集BTSetu(v)，維度。

輸出：分布式動(dòng)態(tài)Skyline結(jié)果集DDSKY(q,Du(v))。

1. For循環(huán)掃描每個(gè)維度i，進(jìn)行如下操作

3. 對(duì)數(shù)據(jù)集DSetu(v)進(jìn)行如下操作：

6. 若掃描到點(diǎn)p且p.times==d時(shí)，則：

7. break；

//算法結(jié)束

8. 否則：

9. 繼續(xù)掃描i+1維；

10. 若i==d-1，則：

11. 進(jìn)行下一次循環(huán)掃描；

//從第1維開始

圖5 節(jié)點(diǎn)N0、N1上的候選集CS0、CS1

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)使用Java語言實(shí)現(xiàn)了分布式動(dòng)態(tài)Skyline查詢算法。其中，分布式架構(gòu)共有9個(gè)節(jié)點(diǎn)(包含1個(gè)主節(jié)點(diǎn)和8個(gè)數(shù)據(jù)節(jié)點(diǎn))。每一個(gè)節(jié)點(diǎn)的配置為Intel i5-8400@2.8 GHz；8 GB DDR3內(nèi)存；1 TB硬盤和Windows 10操作系統(tǒng)。

本節(jié)將本文算法與DSJQ算法[18]進(jìn)行對(duì)比。由于DSJQ解決的問題與本文的問題不同且本文提出的是基于索引的算法，為了保證實(shí)驗(yàn)的合理性，因此我們將基于R樹[2]索引完成DSJQ的本地計(jì)算；此外，基于輪轉(zhuǎn)策略進(jìn)行合并計(jì)算時(shí)，DSJQ無法傳輸R樹索引(代價(jià)太大)，因此DSJQ合并計(jì)算過程基于BNL算法[1]進(jìn)行。具體實(shí)驗(yàn)設(shè)置如下。

DDSQ：本地計(jì)算：BSAB或OSAB；合并計(jì)算：輪轉(zhuǎn)策略(Rotation)+BSAB。

DSJQ：本地計(jì)算：基于R樹的算法；合并計(jì)算：輪轉(zhuǎn)策略+BNL算法。

本實(shí)驗(yàn)共分為三組：本地計(jì)算、合并計(jì)算、算法整體。具體的實(shí)驗(yàn)過程如下。

本地計(jì)算：本組實(shí)驗(yàn)從處理時(shí)間以及掃描空間兩個(gè)方面將本文算法與R樹算法進(jìn)行了對(duì)比。

合并計(jì)算：本組實(shí)驗(yàn)完成算法合并計(jì)算過程效率的對(duì)比，實(shí)驗(yàn)中我們只記錄了合并計(jì)算的時(shí)間。Rotation(BSAB)表示DDSQ算法合并計(jì)算過程；Rotation(BNL)表示DSJQ算法合并計(jì)算過程。

整體對(duì)比：本組實(shí)驗(yàn)結(jié)合本地計(jì)算和合并計(jì)算兩個(gè)過程對(duì)各算法整體從查詢時(shí)間的角度進(jìn)行了對(duì)比。

本實(shí)驗(yàn)采用的數(shù)據(jù)集是文獻(xiàn)[2]提出的兩種模擬數(shù)據(jù)集：獨(dú)立分布數(shù)據(jù)集和反相關(guān)分布數(shù)據(jù)集。相關(guān)參數(shù)的默認(rèn)值和變化范圍如表2所示。

表2 實(shí)驗(yàn)參數(shù)

3.2 本地計(jì)算實(shí)驗(yàn)對(duì)比

本節(jié)將本文算法與R樹算法進(jìn)行對(duì)比，以驗(yàn)證本地算法BSAB和OSAB的正確性和有效性。為了更加穩(wěn)定地測(cè)試算法的性能，實(shí)驗(yàn)中我們隨機(jī)生成了100個(gè)查詢點(diǎn)，記錄了100次查詢的平均處理時(shí)間和平均掃描空間，對(duì)比了數(shù)據(jù)維度以及數(shù)據(jù)量對(duì)查詢時(shí)間和掃描空間的影響。

3.2.1數(shù)據(jù)維度的影響

圖6描述了在獨(dú)立分布和反相關(guān)分布數(shù)據(jù)集上，數(shù)據(jù)維度的變化對(duì)本地算法掃描空間的影響。|CS|表示本地計(jì)算的結(jié)果集大小(及候選集的大小)。由于結(jié)果集的大小與掃描空間相差較大，因此圖中使用主次坐標(biāo)軸進(jìn)行統(tǒng)計(jì)。對(duì)于R樹，只有當(dāng)最小矩形框(MBR)被完全動(dòng)態(tài)支配時(shí)，才能過濾掉。越多的MBR被過濾，參與動(dòng)態(tài)支配關(guān)系計(jì)算的點(diǎn)就越少，掃描空間也就越小。而隨著數(shù)據(jù)維度的增加，能被完全動(dòng)態(tài)支配的MBR數(shù)量減少，因此掃描空間在不斷增加。BSAB和OSAB的掃描策略在各個(gè)維度上從查詢點(diǎn)開始由近及遠(yuǎn)的方式掃描，可以在很小的掃描空間中得到結(jié)果集。因此BSAB和OSAB的掃描空間小于R樹算法的掃描空間。其中OSAB的掃描空間最小。

(a) 獨(dú)立分布

(b) 反相關(guān)分布圖6 數(shù)據(jù)維度對(duì)本地算法掃描空間的影響

圖7描述了數(shù)據(jù)維度的變化對(duì)本地計(jì)算處理時(shí)間的影響。實(shí)驗(yàn)顯示隨著數(shù)據(jù)維度的增加，所有算法的處理時(shí)間都在不斷增加。由于本地結(jié)果集(如圖6所示)隨維度的增加而增大，參與動(dòng)態(tài)支配關(guān)系計(jì)算的數(shù)據(jù)量也就不斷增加，因此算法的處理時(shí)間也在增加。BSAB的掃描空間小于R樹算法的掃描空間，因此其處理時(shí)間小于R樹算法的處理時(shí)間。OSAB在BSAB基礎(chǔ)上進(jìn)一步縮小掃描空間，因此OSAB處理時(shí)間最小，算法性能最優(yōu)。

(a) 獨(dú)立分布

(b) 反相關(guān)分布圖7 數(shù)據(jù)維度對(duì)本地計(jì)算處理時(shí)間的影響

3.2.2數(shù)據(jù)量的影響

本節(jié)描述了隨著數(shù)據(jù)量的變化對(duì)BSAB、OSAB和R樹算法性能的影響。圖8描述的是在獨(dú)立分布和反相關(guān)分布數(shù)據(jù)集上，數(shù)據(jù)量的變化對(duì)算法掃描空間的影響。圖9描述的是數(shù)據(jù)量的變化對(duì)算法處理時(shí)間的影響。隨著數(shù)據(jù)量的增加，有更多的數(shù)據(jù)點(diǎn)參與計(jì)算，因此掃描空間不斷增加，同時(shí)處理時(shí)間也相應(yīng)地增加。由于數(shù)據(jù)分布的特性，在獨(dú)立分布數(shù)據(jù)集上，所有算法的性能優(yōu)于在反相關(guān)分布數(shù)據(jù)集上的性能。但是，無論數(shù)據(jù)量怎么變化或何種數(shù)據(jù)分布，本文算法性能都是最優(yōu)的。

(a) 獨(dú)立分布

(b) 反相關(guān)分布圖8 數(shù)據(jù)量對(duì)本地算法掃描空間的影響

(a) 獨(dú)立分布

(b) 反相關(guān)分布圖9 數(shù)據(jù)量對(duì)本地計(jì)算處理時(shí)間的影響

3.3 合并計(jì)算實(shí)驗(yàn)對(duì)比

本節(jié)描述了DDSQ合并計(jì)算算法與DSJQ合并計(jì)算算法的性能對(duì)比。由于OSAB需要維護(hù)一個(gè)分布直方圖，若在合并計(jì)算時(shí)采用OSAB，則需要對(duì)不同節(jié)點(diǎn)上的分布直方圖進(jìn)行合并更新，這將降低合并計(jì)算的性能。而通過本地計(jì)算的實(shí)驗(yàn)對(duì)比可以看出，OSAB和BSAB性能相差不大，因此在合并計(jì)算時(shí)我們采用了BSAB，用Rotation(BSAB)表示；而DSJQ算法合并計(jì)算時(shí)采用BNL算法，用Rotation(BNL)表示。實(shí)驗(yàn)過程中，我們共使用6個(gè)計(jì)算節(jié)點(diǎn)完成合并計(jì)算，并記錄了合并計(jì)算的時(shí)間。為了節(jié)省空間，在不影響實(shí)驗(yàn)圖可觀性的情況下，將獨(dú)立分布和反相關(guān)分布數(shù)據(jù)集上的實(shí)驗(yàn)圖進(jìn)行了合并。

圖10描述了數(shù)據(jù)量的變化對(duì)合并計(jì)算處理時(shí)間的影響。隨著數(shù)據(jù)量的增加，各節(jié)點(diǎn)候選集中的數(shù)據(jù)量緩慢增長(zhǎng)，因此處理時(shí)間緩慢增加。對(duì)于獨(dú)立分布數(shù)據(jù)集，本文合并算法略優(yōu)于DSJQ算法。而對(duì)于反相關(guān)分布數(shù)據(jù)集，本文合并算法明顯優(yōu)于DSJQ算法。原因是反相關(guān)分布數(shù)據(jù)集產(chǎn)生的候選集的數(shù)據(jù)量遠(yuǎn)大于獨(dú)立分布數(shù)據(jù)集的。但無論數(shù)據(jù)量怎樣變化，本文合并算法都優(yōu)于DSJQ算法。

圖10 數(shù)據(jù)量對(duì)合并計(jì)算處理時(shí)間的影響

圖11描述了數(shù)據(jù)維度的變化對(duì)處理時(shí)間的影響。隨著數(shù)據(jù)維度的增加，各節(jié)點(diǎn)候選集的數(shù)據(jù)量呈指數(shù)增加，因此兩個(gè)算法的處理時(shí)間都迅速地增加。由于BNL算法需要對(duì)每一個(gè)數(shù)據(jù)點(diǎn)都進(jìn)行至少一次的動(dòng)態(tài)支配關(guān)系計(jì)算，而BSAB只需對(duì)掃描到的數(shù)據(jù)進(jìn)行計(jì)算，因此BSAB優(yōu)于BNL算法。而對(duì)于合并計(jì)算，BSAB和BNL算法計(jì)算的中間結(jié)果都是精確的且數(shù)據(jù)量相同，因此輪轉(zhuǎn)調(diào)度中網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量也是相同的。通過理論分析可以確定合并計(jì)算時(shí)本文算法優(yōu)于DSJQ算法，而通過實(shí)驗(yàn)數(shù)據(jù)也證明了理論分析的正確性。

圖11 數(shù)據(jù)維度對(duì)合并計(jì)算處理時(shí)間的影響

3.4 算法整體實(shí)驗(yàn)對(duì)比

本節(jié)描述的是DDSQ和DSJQ算法整體性能的實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)中DSJQ算法本地采用R樹計(jì)算候選集，基于BNL算法完成合并計(jì)算。實(shí)驗(yàn)中我們僅記錄了處理時(shí)間。為了節(jié)省空間，在不影響實(shí)驗(yàn)圖可觀性的情況下，我們將獨(dú)立分布和反相關(guān)分布數(shù)據(jù)集上的實(shí)驗(yàn)圖進(jìn)行了合并。

圖12和圖13分別描述了數(shù)據(jù)量和數(shù)據(jù)維度的變化對(duì)算法DDSQ和DSJQ性能的影響。根據(jù)本地計(jì)算實(shí)驗(yàn)和合并計(jì)算實(shí)驗(yàn)的對(duì)比與分析可以得出，無論實(shí)驗(yàn)參數(shù)和數(shù)據(jù)分布如何變化，本文算法在兩個(gè)計(jì)算過程中都是最優(yōu)的，而對(duì)于算法整體也是如此。尤其對(duì)于反相關(guān)分布數(shù)據(jù)集，本文算法明顯優(yōu)于DSJQ算法。

圖12 數(shù)據(jù)量對(duì)算法整體處理時(shí)間的影響

圖13 數(shù)據(jù)維度對(duì)算法整體處理時(shí)間的影響

3.5 節(jié)點(diǎn)數(shù)量對(duì)查詢處理的影響

為了實(shí)驗(yàn)的完整性，本節(jié)描述了計(jì)算節(jié)點(diǎn)數(shù)量的變化對(duì)DDSQ算法的影響,如圖14所示。實(shí)驗(yàn)時(shí)數(shù)據(jù)維度為5，數(shù)據(jù)量為3 000 000(6×5×105)。由圖14觀察得，無論何種數(shù)據(jù)分布，隨著節(jié)點(diǎn)數(shù)量的增加，DDSQ算法的處理時(shí)間在不斷減少。其原因是計(jì)算任務(wù)被分配到更多的節(jié)點(diǎn)中完成，使得平均的處理時(shí)間減少了。

圖14 節(jié)點(diǎn)數(shù)量對(duì)算法整體處理時(shí)間的影響

通過上述對(duì)實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)與觀察，無論實(shí)驗(yàn)參數(shù)怎樣變化，本文算法總體上性能最佳。同時(shí)，上述實(shí)驗(yàn)也驗(yàn)證了本文算法的正確性和有效性，進(jìn)而驗(yàn)證了本文算法可以有效解決分布式環(huán)境下的動(dòng)態(tài)Skyline查詢問題。

4 結(jié) 語

作為Skyline的一個(gè)重要變種，動(dòng)態(tài)Skyline可以根據(jù)不同的查詢請(qǐng)求給出相應(yīng)的查詢結(jié)果。本文提出一種分布式環(huán)境下的動(dòng)態(tài)Skyline查詢算法，目的是為了解決集中式環(huán)境下處理大規(guī)模數(shù)據(jù)會(huì)產(chǎn)生瓶頸節(jié)點(diǎn)的問題。為了解決上述問題，首先，在本地計(jì)算中，基于B樹索引的基礎(chǔ)掃描算法BSAB只對(duì)掃描到的數(shù)據(jù)點(diǎn)進(jìn)行支配關(guān)系計(jì)算，從而快速得到分布式動(dòng)態(tài)Skyline候選集。然后，在BSAB基礎(chǔ)上提出的優(yōu)化算法OSAB通過改變掃描維度，來快速找到掃描結(jié)束點(diǎn)，以此進(jìn)一步減少掃描空間，從而進(jìn)一步加速得到候選集。之后，在合并計(jì)算中，通過輪轉(zhuǎn)策略將合并候選集的計(jì)算任務(wù)盡可能平均分配到各節(jié)點(diǎn)，從而達(dá)到負(fù)載均衡，避免了瓶頸節(jié)點(diǎn)的產(chǎn)生。最后，通過大量的實(shí)驗(yàn)驗(yàn)證了本文DDSQ算法的正確性和高效性。

在未來的工作中，我們將繼續(xù)研究處理多個(gè)查詢點(diǎn)以及數(shù)據(jù)流環(huán)境下的動(dòng)態(tài)Skyline等問題。