一種高效的分布式動態Skyline查詢算法

蔣森安 白 梅 王習特 李冠宇 史一民

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

0 引 言

Skyline查詢[1]最早是由Borzsonyi等根據最大向量問題提出的。其被廣泛應用于多目標決策、數據挖掘等領域。作為Skyline查詢的重要變種，動態Skyline首先由Papadias等[2]提出。給定查詢點q，動態Skyline是由所有不被“關于q動態支配”的點構成的集合[3]。具體地，給定查詢點q和兩個數據點p1和p2，p1關于q動態支配p2是指：在所有的維度上，p1距離q不比p2遠；同時，至少在一個維度上，p1距離q比p2近。通常，距離查詢點q的遠近可以通過歐氏距離來衡量。

隨著科技的發展以及數據獲取方式的多樣化，數據呈爆發式增長。集中式環境下的查詢算法已無法應對處理龐大數據量的挑戰。因此，分布式查詢算法應運而生。本文關注的是分布式環境下的動態Skyline查詢處理。

本文研究的分布式動態Skyline查詢在生活中具有很重要的意義。例如，股票交易市場每天都會產生大規模的股票信息數據，而人們想要從這些數據中選取優質股票時，可以通過對已知的優質股票q進行動態Skyline查詢，尋找到與q相似的股票。通過對這些股票信息的分析，可以更加準確地為用戶推薦具有良好投資價值的股票。同時，借助分布式架構可以解決集中式環境無法對大規模數據進行計算的問題。因此，對分布式動態Skyline查詢的研究具有很好的實際應用價值。

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

關于動態Skyline查詢，文獻[8]提出了一種空間Skyline查詢算法。文獻[9]算法在文獻[8]算法的基礎上提出了一種度量距離函數，來完成動態Skyline查詢。文獻[10]提出了一種面向海量數據的動態Skyline查詢算法。

此外，文獻[11]提出了一種T-Skyline查詢算法。文獻[12]提出了針對不完全數據集的動態Skyline查詢算法。文獻[3]提出了數據流上的動態Skyline查詢算法。文獻[13]提出了子空間下的全局Skyline查詢算法。文獻[14]提出了動態數據庫上的子空間全局Skyline查詢算法。

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

本文關注的是分布式環境下的動態Skyline查詢。為了解決此問題，提出分布式動態Skyline查詢(DDSQ)算法。DDSQ算法共分為本地計算和合并計算兩個過程。歸納起來，本文的主要貢獻如下。

1) 本地計算時，我們基于B樹索引，提出基礎掃描算法BSAB計算分布式動態Skyline候選集。BSAB借助B樹索引掃描數據，只對掃描到的數據點進行動態支配關系計算，從而快速得到候選集。

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

3) 合并計算時，我們采用分布式輪轉調度策略[18]，將計算任務平均分配到各節點，使各節點之間達到負載均衡，從而避免了瓶頸節點的產生。同時，傳輸數據時，我們將候選集和索引一起傳到指定節點，利用BSAB快速完成合并計算。

1 問題定義

給定d維數據集合D，用p[i]表示數據點p在第i維上的屬性值，且在每個維度上以小值為優。

定義1(動態支配) 給定d維數據集D中的兩個點p1和p2及查詢點q，p1關于q動態支配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(動態Skyline) 給定查詢點q和數據集D，所有不被其他點動態支配的點構成了動態Skyline，記作DSKY(q,D)。其形式化表示為DSKY(q,D)={pi|pi∈D,/?pj∈D且pj

為了表述方便，表1給出了符號及其含義。

表1 符號表示及含義

2 分布式動態Skyline查詢算法

DDSQ算法共分為兩個過程。第一個過程為本地計算。當接到查詢請求時，各節點利用本地掃描算法將本地數據集中被動態支配的點過濾，得到分布式動態Skyline候選集。第二個過程為合并計算。此過程各節點依據輪轉策略將候選集發送到指定節點完成候選集合并計算。待所有候選集合并計算之后，各節點剩下的數據點構成了分布式動態Skyline結果集。

2.1 本地計算

本小節主要介紹DDSQ算法的本地計算過程。首先，我們基于B樹索引提出了基礎掃描算法BSAB。通過BSAB可以減少掃描空間，進而提高計算效率。然后，我們在BSAB的基礎上基于分布直方圖[13]提出了優化的掃描算法OSAB。OSAB可以進一步減少掃描空間，提高本地計算的效率。

2.1.1本地基礎掃描算法

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

基于B樹索引，我們提出基礎掃描策略BScanS：1) 選擇掃描維度i：采用循環的方式掃描所有維度，即對i維掃描一次后，緊接著掃描i+1維；2) 選擇掃描數據點：掃描i維時，選擇距離q[i]最近的數據點進行掃描。值得注意的是，當距離q[i]最近的數據點有多個時，需要將這些數據點同時掃描。

在掃描過程中，用參數p.times來記錄數據點被掃描到的次數。當一個點p被掃描d次時，我們稱點p為掃描結束點，記作FSP。

引理1[13]給定數據集D中的三個數據點p1、p2、p3，若p1

定理1給定數據集D中的點p，對于掃描維度i，p只可能被在BTi上先于p掃描到的數據點動態支配，而p無法動態支配這些點。

證明依據動態支配的定義很容易證得。

定理2數據集D及索引集BTSet(D)，按照BScanS策略掃描BTSet(D)，若找到一個FSP，則D中所有的動態Skyline點都已被掃描到，掃描策略結束。

證明假設存在一個動態Skyline點p，當找到FSP時沒有被掃描到。而根據動態支配定義，必定存在一個維度，p先于FSP被掃描，這與假設矛盾。定理2得證。

用符號DSKYi表示i維上掃描到的動態Skyline點集。依據定理2，當掃描策略結束時，所有被掃描到的數據點構成查詢點q的掃描空間，記作ScanS(q)。

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

算法1BSAB

輸入：d維數據集D，查詢點q，索引集BTSet(D)。

輸出：動態Skyline結果集DSKY(q,D)。

1.EndFlag=false；

//算法結束標志

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

3. While(True)

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

5. For 依次處理DSet中的數據點p

6.p.times++；

//統計點p被掃描的次數

7. Ifp.times==1

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

//記錄掃描空間

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

//p不被DSKYi和DSet中的點動態支配

10. 將點p加入DSKYi；

11. Ifp.times==d

12.EndFlag=true；

//掃描結束

13. IfEndFlag==true

14. break；

//結束循環，算法結束

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

//得出結果集

例1如圖1(a)所示，q[x]的初始掃描位置指向p6和p5之間，q[y]的初始掃描位置指向p7和p4之間。依據BScanS策略，圖1(b)給出了掃描過程。當第二次掃描y維時，同時掃描到p3、p7，p7被p3動態支配，刪除p7。此時，p3.times=2，依據定理2，算法結束。得到動態Skyline結果集為DSKY(q,D)=DSKYx∪DSKYy={p3,p4,p6}。

圖1 本地基礎掃描算法BSAB示例

2.1.2本地優化掃描算法

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

圖2 數據集及索引

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

(1)

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

對于掃描到的數據點可得到一個Alldif值，我們將具有最小Alldif值的點稱為最快掃描結束點，記作pfast。具體地，優化后的掃描策略OScanS如下。

1) 選擇掃描維度：取pfast.difi最小值對應的維度i作為掃描維度；2) 選擇掃描數據點：掃描i維時，選擇距離q[i]最近的數據點進行掃描。

算法2給出了優化掃描算法OSAB的具體過程。

算法2OSAB

輸入：d維數據集D，查詢點q，索引集BTSet(D)。

輸出：動態Skyline結果集DSKY(q,D)。

1. 初始化pfast=null；

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

3. 初始掃描第1維并處理數據點，選擇pfast；

4. While(True)

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

6. 采用算法1中第5到第13行的過程處理DSet中的數據點p，返回算法結束標志符EndFlag；

7. IfEndFlag== true

8. break；

//終止循環，算法結束

9. Ifp.Alldif

10. 更新pfast為點p；

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

//得到結果集

值得注意的是，根據pfast.difi確定掃描維度i后，只有當掃描到新的動態Skyline點(第一次掃描且不被動態支配的點)，才可能更新pfast。否則，將一直掃描i維，直到當前pfast被更新，或者掃描到當前pfast(此時算法結束)。

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

圖3 OSAB掃描過程

之后，由pfast確定的掃描維度為y，掃描y維得{p8}，此時pfast=p14，DSKYy={p8}。按照此方式繼續掃描，當第二次掃描到x維時，得到{p10,p13}(p13被動態支配)，pfast=p4，DSKYx={p14,p10}。此后，繼續掃描y維得到{p10,p16}，DSKYy={p8,p9,p4,p10}。此時p10.times=2，依據定理2，算法結束。得到動態Skyline結果集為DSKY={p4,p8,p9,p10,p14}。

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

2.2 合并計算

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

圖4 分布式調度策略

2.2.1輪轉策略

本節對輪轉策略進行簡單描述，具體過程可查看文獻[18]。

定義3(輪轉) 給定一個偏移量offset，節點Nu上的候選集CSu將被傳輸到節點Nv上。其中，v=(u+offset)%|N|。

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

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

依據引理2，合并候選集時，我們只需統計與CS0完成合并計算的候選集。當CS0完成與其他候選集合并計算時，候選集合并計算結束。此時，每個節點存儲分布式動態Skyline結果集的一個子集。

2.2.2基于輪轉策略合并候選集

當接到查詢請求后，各節點首先進行本地計算得到候選集，之后按照輪轉策略中的輪轉偏移量將候選集發送到指定節點，完成候選集合并計算。

算法3候選集合并過程描述—DDSQ合并計算

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

輸出：分布式動態Skyline結果集DDSKY(q,Du(v))。

1. For循環掃描每個維度i，進行如下操作

3. 對數據集DSetu(v)進行如下操作：

6. 若掃描到點p且p.times==d時，則：

7. break；

//算法結束

8. 否則：

9. 繼續掃描i+1維；

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

11. 進行下一次循環掃描；

//從第1維開始

圖5 節點N0、N1上的候選集CS0、CS1

3 實驗分析

3.1 實驗設置

實驗使用Java語言實現了分布式動態Skyline查詢算法。其中，分布式架構共有9個節點(包含1個主節點和8個數據節點)。每一個節點的配置為Intel i5-8400@2.8 GHz；8 GB DDR3內存；1 TB硬盤和Windows 10操作系統。

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

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

DSJQ：本地計算：基于R樹的算法；合并計算：輪轉策略+BNL算法。

本實驗共分為三組：本地計算、合并計算、算法整體。具體的實驗過程如下。

本地計算：本組實驗從處理時間以及掃描空間兩個方面將本文算法與R樹算法進行了對比。

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

整體對比：本組實驗結合本地計算和合并計算兩個過程對各算法整體從查詢時間的角度進行了對比。

本實驗采用的數據集是文獻[2]提出的兩種模擬數據集：獨立分布數據集和反相關分布數據集。相關參數的默認值和變化范圍如表2所示。

表2 實驗參數

3.2 本地計算實驗對比

本節將本文算法與R樹算法進行對比，以驗證本地算法BSAB和OSAB的正確性和有效性。為了更加穩定地測試算法的性能，實驗中我們隨機生成了100個查詢點，記錄了100次查詢的平均處理時間和平均掃描空間，對比了數據維度以及數據量對查詢時間和掃描空間的影響。

3.2.1數據維度的影響

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

(a) 獨立分布

(b) 反相關分布圖6 數據維度對本地算法掃描空間的影響

圖7描述了數據維度的變化對本地計算處理時間的影響。實驗顯示隨著數據維度的增加，所有算法的處理時間都在不斷增加。由于本地結果集(如圖6所示)隨維度的增加而增大，參與動態支配關系計算的數據量也就不斷增加，因此算法的處理時間也在增加。BSAB的掃描空間小于R樹算法的掃描空間，因此其處理時間小于R樹算法的處理時間。OSAB在BSAB基礎上進一步縮小掃描空間，因此OSAB處理時間最小，算法性能最優。

(a) 獨立分布

(b) 反相關分布圖7 數據維度對本地計算處理時間的影響

3.2.2數據量的影響

本節描述了隨著數據量的變化對BSAB、OSAB和R樹算法性能的影響。圖8描述的是在獨立分布和反相關分布數據集上，數據量的變化對算法掃描空間的影響。圖9描述的是數據量的變化對算法處理時間的影響。隨著數據量的增加，有更多的數據點參與計算，因此掃描空間不斷增加，同時處理時間也相應地增加。由于數據分布的特性，在獨立分布數據集上，所有算法的性能優于在反相關分布數據集上的性能。但是，無論數據量怎么變化或何種數據分布，本文算法性能都是最優的。

(a) 獨立分布

(b) 反相關分布圖8 數據量對本地算法掃描空間的影響

(a) 獨立分布

(b) 反相關分布圖9 數據量對本地計算處理時間的影響

3.3 合并計算實驗對比

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

圖10描述了數據量的變化對合并計算處理時間的影響。隨著數據量的增加，各節點候選集中的數據量緩慢增長，因此處理時間緩慢增加。對于獨立分布數據集，本文合并算法略優于DSJQ算法。而對于反相關分布數據集，本文合并算法明顯優于DSJQ算法。原因是反相關分布數據集產生的候選集的數據量遠大于獨立分布數據集的。但無論數據量怎樣變化，本文合并算法都優于DSJQ算法。

圖10 數據量對合并計算處理時間的影響

圖11描述了數據維度的變化對處理時間的影響。隨著數據維度的增加，各節點候選集的數據量呈指數增加，因此兩個算法的處理時間都迅速地增加。由于BNL算法需要對每一個數據點都進行至少一次的動態支配關系計算，而BSAB只需對掃描到的數據進行計算，因此BSAB優于BNL算法。而對于合并計算，BSAB和BNL算法計算的中間結果都是精確的且數據量相同，因此輪轉調度中網絡傳輸的數據量也是相同的。通過理論分析可以確定合并計算時本文算法優于DSJQ算法，而通過實驗數據也證明了理論分析的正確性。

圖11 數據維度對合并計算處理時間的影響

3.4 算法整體實驗對比

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

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

圖12 數據量對算法整體處理時間的影響

圖13 數據維度對算法整體處理時間的影響

3.5 節點數量對查詢處理的影響

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

圖14 節點數量對算法整體處理時間的影響

通過上述對實驗結果的統計與觀察，無論實驗參數怎樣變化，本文算法總體上性能最佳。同時，上述實驗也驗證了本文算法的正確性和有效性，進而驗證了本文算法可以有效解決分布式環境下的動態Skyline查詢問題。

4 結 語

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

在未來的工作中，我們將繼續研究處理多個查詢點以及數據流環境下的動態Skyline等問題。