Map-Reduce并行計算框架下的Skyline查詢及優化算法

◆羅 云 陳佳瑜

Map-Reduce并行計算框架下的Skyline查詢及優化算法

◆羅 云 陳佳瑜

（重慶理工大學 重慶 404100）

近幾年來，Skyline查詢處理在許多應用領域具有潛在的實用價值。在Map-Reduce框架下采用基于角度數據劃分的方法，本文提出Cirl-Skyline查詢算法。進一步提高算法的查詢效率，為了更好的解決重復計算局部沒有發生變化Skyline查詢點的問題，在Cirl-Skyline算法的基礎上提出Restrict-Skyline算法。理論分析和實驗證實，該算法具有高效性和可擴展性。

Map-Reduce；Skyline查詢；數據劃分

0 前言

隨著互聯網的迅速發展，數據正在以前所未有的規模急劇增長，往往需要對海量數據進行挖掘分析才能得到真正有用的信息。Skyline查詢[9]在近幾年來迅速成為信息檢索領域研究熱點之一，且在數據的可視化方面有著廣泛的應用。Skyline計算[8]就是從給定的數據庫中搜索不被其它數據對象支配的數據對象集合。這里的支配[10]指的是一個數據對象p在任一維上都不比其它數據對象q“差”并且至少存在在某個維度上比q更“優”（“優”和“差”是根據用戶個人偏好決定的）。

在Skyline查詢計算中采用了Map-Reduce并行計算框架，使兩者結合起來處理海量數據查詢等問題。在Map-Reduce框架下采用基于角度數據劃分的方法，提出了Cirl-Skyline查詢算法。為了在Map任務前刪除某些不能成為Skyline最終結果集的點，提高算法的執行效率，在Cirl-Skyline查詢算法的基礎上給出Restrict-Skyline查詢優化算法。

1 相關概念及研究進展

1.1 相關概念

在數據空間P上定義d維的數據集D=（D1，D2，D3……Dd），其中Di（1≤i≤d）表示某時間的屬性。Skyline結果集就是從某個數據庫中抽取不被其它任何數據對象支配的數據對象的集合。

定義1（支配[10]）給定d維的數據集D上的兩個數據點pi，qj，在任意一維度上pi（1≤i≤d）的取值都不小于數據點qj（1≤j≤d），且至少在某一維度上的取值pi比qj要大,稱數據點p支配數據點q。

定義2（Skyline點[11]）在d維數據空間P上，數據集D中的任意點p∈D，則p為D的Skyline點；數據集D所有不被其它數據點支配的數據點集合，記為S，則S構成Skyline最終結果集。

1.2 研究進展

近年來，Skyline計算在數據挖掘等方面得到越來越多的關注。2001年，對Skyline計算用于數據庫領域最早由Borzsonyi[1]等人提出。Borzsonyi提出了BNL和D&C算法。Tan K-L[2]提出了bitmap和Index算法。

由于數據規模超出了單機系統的計算能力，因此分布式Skyline計算用于解決指數級數據查詢的問題得到研究者的關注。Balke[3]等人提出了BDS和IDS算法。Z.Huang[4]等人提出了在MANET上的第一個Skyline計算算法，將所有的移動設配組織成一個樹狀結構，并以發出查詢的設備作為樹的根節點。

面對指數級增長的海量數據，如何在現有算法基礎之上提高Skyline查詢效率，是一項長期的任務。

2 Map-Reduce框架下的Skyline查詢算法

本節主要介紹Map-Reduce并行框架下的Skyline查詢算法，給出具體Skyline查詢算法-Cirl-Skyline查詢算法，在Cirl-Skyline查詢算法的基礎上給出Restrict-Skyline查詢優化算法。

2.1 數據區域劃分方法

Map-Reduce以鍵值對對數據輸入方式處理數據，能自動完成數據的劃分。它包含Map和Reduce兩個階段并行處理模型和過程，Map負責把任務分解成多個任務，Reduce負責把分解后多任務處理的結果匯總起來。Map-Reduce模型如下方式表示:

Map:（k1，v1）→list（k2，v2）

Reduce:（k1，list（v2））→list（v3）

Skyline查詢計算采用Map-Reduce“分而治之”的重要特征，將原有數據集劃分多個子數據集進行并行計算。將數據點進行橫、縱方向分割成若干部分。本文將采用基于角度的劃分方法[10]。

基于角度的劃分方法，采用文獻[10]的劃分方法。首先將數據點的笛卡爾積坐標映射到坐標上，然后根據球坐標將數據空間分成N個分區。球坐標計算公式如（1）所示，其中數據點P={P1，P2，P3，…Pn}，Pn為數據點的第n維屬性；半徑為r；維度為dk（1≤k≤n-1）的取值范圍為［0］π，。

2.2 Cirl-Skyline查詢算法

Map-Reduce將待處理的數據集分解成許多小的數據集，可以并行處理。Skyline計算由N個子任務串聯而成，對于Skyline計算的最終數據集可以先計算局部Skyline結果集，并行計算數據塊中的Skyline結果集合并形成局部的Skyline結果集，不斷地重復上述操作，形成最終的Skyline結果集。

Cirl-Skyline查詢算法的基本原理:根據角度劃分的方法，將笛卡爾坐標空間映射到球面的空間，然后根據公式（1）的計算方法，計算數據點是屬于某個區域，將數據點空間分成N個數據塊。不斷計算N個數據塊的局部Skyline結果集，合并局部結果集，最后計算出全局Skyline結果集。

根據基本原理的介紹可以用Map-Reduce執行過程對Cirl-Skyline查詢算法的實現。

（1）在Map階段實現對數據區域分塊操作。依次讀取每一個數據點，采用基于角度劃分方法，然后確定每個數據點屬于某個區域塊。

（2）將N個數據塊的局部Skyline結果集合并。Reduce階段根據BNL[1]算法進行過濾，最后計算出全局結果集。

根據角度劃分方法與Map-Reduce下的Skyline執行過程，首先根據公式⑴計算出每個數據點坐標，在Reduce階段使用BNL過濾算法，求出局部Skyline結果集。

以上簡單的介紹了Map-Reduce下的Cirl-Skyline查詢算法，通過采用BNL過濾算法減少Map輸出。過濾階段采用BNL過濾算法，采用兩兩比較方法。為了提高算法的運行效率，提出Restrict-Skyline查詢優化算法，提高算法的剪枝能力。

2.3 Restrict-Skyline查詢優化算法

Restrict-Skyline查詢算法分為兩部分:預處理和后序處理。首先對數據集進行預處理，對N個數據塊中的數據點進行排序，采用SFS[7]算法中的F（P）值進行升值排序。設P（x1，x2，x3，…xn），F（P）隨著維度的遞增而遞增，則F（P）是遞增函數。

F（P）=a1×x1+a2×x2+…+an×xn，（ai>0，1≤i≤d）

數據塊中的數據點根據F（P）成遞增排序，設置局部過濾值，在Map任務未執行前，首先刪除一些Skyline結果集的點，使得Reduce輸入有所減少。數據點遞增排序之后隨機選取每個數據塊中局部過濾值。合并局部Skyline結果集，根據F（P）再次將合并后的局部Skyline結果集進行排序，選取局部過濾值，刪除部分局部Skyline結果集。通過減少局部Skyline結果集，提高合并效率和算法的運行時間。

3 實驗驗證與評估

3.1 實驗環境

本文的實驗在4臺高配置的PC機組成的集群上運行且配置相同。處理器為Intel Core i7 4790GHZ，內存為4GB，操作系統為Windows 7。Hadoop版本為0.20.2，JDK的版本1.6。其中一臺PC機為Master管理節點服務器，其余PC機為Slave節點。

實驗數據是使用文獻[1]中標準的數據，獨立、相關和反相關數據集。數據集為2×105～2×106，數據維度是2～10，數據類型為浮點數，節點個數為6。三種數據集[1]如下:

⑴ 獨立:數據的各維屬性是相互獨立且是均勻分布的。

⑵ 相關:數據的某一維屬性的數值大（小），則數據的其它維屬性隨之也大（小）。

⑶ 反相關:數據的某一維屬性的數值大（?。?，則數據的另一維或其它所有維屬性都變小（大）。

為了直觀看出，實驗中的三種算法分別標記為MR-BNL、MR-CS、MR-RS。三種數據集分布對算法進行測試。

3.2 實驗評估

本文提出了MR-CS和MR-RS查詢算法與文獻[11]提出的MR-BNL塊嵌套循環算法進行相互比較，根據不同的數據集分布、維度變化以及節點個數、規模大小對算法運行時間進行比較從而驗證算法的高效性。

3.2.1 維度變化對Skyline算法時間性能的影響

圖1 維度變化對運行時間的影響

對于三種數據集分布，數據規模為2×106，節點個數為6。通過改變數據的維度，得到維度變化對Skyline查詢運行時間的影響。如圖1所示，圖中表示數據服從三種數據集分布。對于獨立和反相關分布，Skyline查詢算法的運行時間在維度d∈[3，5]時，Skyline算法的運行時間呈現指數級增長。隨著維度的增加，數據間的支配關系越少，從而在合并局部Skyline結果集時耗費大量的時間，同時影響算法的響應時間。但本文的兩個算法運行時間仍小于MR-BNL運行時間，因為減少Map的輸入量，從而提高運行效率。MR-RS采用角度劃分方法和設置局部過濾值，刪除局部Skyline結果集，待處理的數據點減少，因此減少處理時間，所以在三種數據分布下，MR-RS的運行時間較短。

3.2.2 規模變化對Skyline算法時間性能的影響

對于三種數據集分布，數據規模為2、4、6、8、10×105數據點，節點個數為6，維度為4的情況下的運行時間。隨著數據規模以指數級增長時，Map-Reduce處理的任務量也在增加。MR-RS查詢算法根據預先處理機制刪除了局部Skyline結果集的點，從而減少了Map的輸入量，因此MR-RS查詢算法運行時間最短。對于反相關數據分布來說，反相關的數據彼此不支配的可能性增大，在合并Skyline結果集中耗費時間，從而運行開銷也隨之增加。從圖2中可見，在三種數據分布下，MR-RS的性能最優，而MR-BNL算法的運行時間高于本文的兩個算法，因為MR-RS在Map任務前刪除不可能成為Skyline結果集的點，從而運行時間最短。

圖2 數據規模對運行時間的影響

3.2.3 節點變化對Skyline算法時間性能的影響

對于三種數據集分布，測試節點數量對算法時間性能的影響。節點數設置成2、4、6、8。其他參數保持不變。并行計算的運行時間開銷與節點數成反比，則算法的運行時間隨著計算節點數增加反而減少。在獨立和反相關數據分布情況下更加明顯，MR-RS的時間開銷隨著節點個數的增加而減少，顯然，隨著計算節點增加到一定程度，算法的總體運行時間呈下降趨勢，如圖3所示。因此增加節點個數在一定程度上可以提高數據處理的能力，MR-RS的時間性能與預期的一致。

圖3 計算節點對運行時間的影響

4 總結

本文針對海量數據的查詢問題，將Skyline與Map-Reduce并行框架結合，實現了Cirl-Skyline查詢算法和Restrict-Skyline查詢算法。兩種算法采用基于角度的劃分方法，有效的過濾重復計算Skyline點，Restrict-Skyline查詢算法設置約束范圍和全局過濾值，減少Map任務的輸入量，從而提高算法的運行效率。通過數據集對兩種算法與MR-BNL算法進行比較，分別改變數據規模，節點個數和維度驗證Skyline查詢、Restrict-Skyline和MR-BNL算法在不同數據分布上運行時間的性能。實驗結果表明，本文提出的Restrict-Skyline算法在不部分情況下運行效率高于Cirl-Skyline和MR-BNL算法，總體上提高了Skyline查詢時間和計算效率。驗證該算法的有效性和準確性。

[1]Borzsonyi S,Kossmann D,Stocker K.The Skyline operat or[C]//Proceedings of the 17th International Conference on Data Engineering（ICDE），2001.Washington，DC，USA:IEEE Computer Society，2001.

[2]Tan K L,Eng P K,Ooi B C.Efficient progressive Skyli ne computation[C]//Proceedings of the 27th International Co nference on Very Large Data Bases(VLDB),2001.San Francisco, CA,USA:Morgan Kaufmann.2001.

[3]Balke W T,Guntzer U,Zheng J X.Efficient distributed skylining for Web information systems[C]//Proc of EDBT,200 4.

[4]Huang Z,Jensen C S,Lu H,et al.Skyline queries against mobile lightweight devices in manets[C]//Proc of ICDE,200 6.

[5]Dean J,Ghemawat S.MapReduce:Sim plifi ed dat- a p roces sing on l arge clust er.Comm unications of the ACM, 2005.

[6]Kung H T,Luccio F,Preparata F P.On finding the ma xima of a set of vectors[J].J ACM,1975.

[7]丁琳琳，信俊昌，王國仁等.基于Map-Reduce的海量數據高效 Skyline查詢處理[J].計算機學報，2011.

[8]張波良，周水庚，關佶紅.MapReduce框架下的Skyl-i ne計算[J].計算機科學與索，2011.

[9]王淑艷，楊鑫，李克秋.MapReduce框架下基于超平面投影劃分的Skyline計算[J].計算機研究與發展，2014.

[10]Chen L,Hwang K,Wu J.MapReduce Skyline query processing with a new angular partitioning approach.Proceedin gs of Parallel and Distributed Processing Symposium Worksh ops & PhD Forum（IPDPSW）,Sha-nghai，China，2012.

[11]Zhang Bo-Li ang,Zhou S hui-Geng,Guan JiHong.Ad apting Skyline com put at ion to the MapReduce framework: Algorithms and experiment s//Proceeding s of the DASFAA Workshop s.Hong Kong,China,2011.