◆羅 云 陳佳瑜

Map-Reduce并行計(jì)算框架下的Skyline查詢及優(yōu)化算法

◆羅 云 陳佳瑜

（重慶理工大學(xué) 重慶 404100）

近幾年來，Skyline查詢處理在許多應(yīng)用領(lǐng)域具有潛在的實(shí)用價值。在Map-Reduce框架下采用基于角度數(shù)據(jù)劃分的方法，本文提出Cirl-Skyline查詢算法。進(jìn)一步提高算法的查詢效率，為了更好的解決重復(fù)計(jì)算局部沒有發(fā)生變化Skyline查詢點(diǎn)的問題，在Cirl-Skyline算法的基礎(chǔ)上提出Restrict-Skyline算法。理論分析和實(shí)驗(yàn)證實(shí)，該算法具有高效性和可擴(kuò)展性。

Map-Reduce；Skyline查詢；數(shù)據(jù)劃分

0 前言

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

在Skyline查詢計(jì)算中采用了Map-Reduce并行計(jì)算框架，使兩者結(jié)合起來處理海量數(shù)據(jù)查詢等問題。在Map-Reduce框架下采用基于角度數(shù)據(jù)劃分的方法，提出了Cirl-Skyline查詢算法。為了在Map任務(wù)前刪除某些不能成為Skyline最終結(jié)果集的點(diǎn)，提高算法的執(zhí)行效率，在Cirl-Skyline查詢算法的基礎(chǔ)上給出Restrict-Skyline查詢優(yōu)化算法。

1 相關(guān)概念及研究進(jìn)展

1.1 相關(guān)概念

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

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

定義2（Skyline點(diǎn)[11]）在d維數(shù)據(jù)空間P上，數(shù)據(jù)集D中的任意點(diǎn)p∈D，則p為D的Skyline點(diǎn)；數(shù)據(jù)集D所有不被其它數(shù)據(jù)點(diǎn)支配的數(shù)據(jù)點(diǎn)集合，記為S，則S構(gòu)成Skyline最終結(jié)果集。

1.2 研究進(jìn)展

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

由于數(shù)據(jù)規(guī)模超出了單機(jī)系統(tǒng)的計(jì)算能力，因此分布式Skyline計(jì)算用于解決指數(shù)級數(shù)據(jù)查詢的問題得到研究者的關(guān)注。Balke[3]等人提出了BDS和IDS算法。Z.Huang[4]等人提出了在MANET上的第一個Skyline計(jì)算算法，將所有的移動設(shè)配組織成一個樹狀結(jié)構(gòu)，并以發(fā)出查詢的設(shè)備作為樹的根節(jié)點(diǎn)。

面對指數(shù)級增長的海量數(shù)據(jù)，如何在現(xiàn)有算法基礎(chǔ)之上提高Skyline查詢效率，是一項(xiàng)長期的任務(wù)。

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

本節(jié)主要介紹Map-Reduce并行框架下的Skyline查詢算法，給出具體Skyline查詢算法-Cirl-Skyline查詢算法，在Cirl-Skyline查詢算法的基礎(chǔ)上給出Restrict-Skyline查詢優(yōu)化算法。

2.1 數(shù)據(jù)區(qū)域劃分方法

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

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

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

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

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

2.2 Cirl-Skyline查詢算法

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

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

根據(jù)基本原理的介紹可以用Map-Reduce執(zhí)行過程對Cirl-Skyline查詢算法的實(shí)現(xiàn)。

（1）在Map階段實(shí)現(xiàn)對數(shù)據(jù)區(qū)域分塊操作。依次讀取每一個數(shù)據(jù)點(diǎn)，采用基于角度劃分方法，然后確定每個數(shù)據(jù)點(diǎn)屬于某個區(qū)域塊。

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

根據(jù)角度劃分方法與Map-Reduce下的Skyline執(zhí)行過程，首先根據(jù)公式⑴計(jì)算出每個數(shù)據(jù)點(diǎn)坐標(biāo)，在Reduce階段使用BNL過濾算法，求出局部Skyline結(jié)果集。

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

2.3 Restrict-Skyline查詢優(yōu)化算法

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

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

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

3 實(shí)驗(yàn)驗(yàn)證與評估

3.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)在4臺高配置的PC機(jī)組成的集群上運(yùn)行且配置相同。處理器為Intel Core i7 4790GHZ，內(nèi)存為4GB，操作系統(tǒng)為Windows 7。Hadoop版本為0.20.2，JDK的版本1.6。其中一臺PC機(jī)為Master管理節(jié)點(diǎn)服務(wù)器，其余PC機(jī)為Slave節(jié)點(diǎn)。

實(shí)驗(yàn)數(shù)據(jù)是使用文獻(xiàn)[1]中標(biāo)準(zhǔn)的數(shù)據(jù)，獨(dú)立、相關(guān)和反相關(guān)數(shù)據(jù)集。數(shù)據(jù)集為2×105～2×106，數(shù)據(jù)維度是2～10，數(shù)據(jù)類型為浮點(diǎn)數(shù)，節(jié)點(diǎn)個數(shù)為6。三種數(shù)據(jù)集[1]如下:

⑴ 獨(dú)立:數(shù)據(jù)的各維屬性是相互獨(dú)立且是均勻分布的。

⑵ 相關(guān):數(shù)據(jù)的某一維屬性的數(shù)值大（?。瑒t數(shù)據(jù)的其它維屬性隨之也大（?。?/p>

⑶ 反相關(guān):數(shù)據(jù)的某一維屬性的數(shù)值大（?。?，則數(shù)據(jù)的另一維或其它所有維屬性都變小（大）。

為了直觀看出，實(shí)驗(yàn)中的三種算法分別標(biāo)記為MR-BNL、MR-CS、MR-RS。三種數(shù)據(jù)集分布對算法進(jìn)行測試。

3.2 實(shí)驗(yàn)評估

本文提出了MR-CS和MR-RS查詢算法與文獻(xiàn)[11]提出的MR-BNL塊嵌套循環(huán)算法進(jìn)行相互比較，根據(jù)不同的數(shù)據(jù)集分布、維度變化以及節(jié)點(diǎn)個數(shù)、規(guī)模大小對算法運(yùn)行時間進(jìn)行比較從而驗(yàn)證算法的高效性。

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

圖1 維度變化對運(yùn)行時間的影響

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

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

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

圖2 數(shù)據(jù)規(guī)模對運(yùn)行時間的影響

3.2.3 節(jié)點(diǎn)變化對Skyline算法時間性能的影響

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

圖3 計(jì)算節(jié)點(diǎn)對運(yùn)行時間的影響

4 總結(jié)

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

[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的海量數(shù)據(jù)高效 Skyline查詢處理[J].計(jì)算機(jī)學(xué)報，2011.

[8]張波良，周水庚，關(guān)佶紅.MapReduce框架下的Skyl-i ne計(jì)算[J].計(jì)算機(jī)科學(xué)與索，2011.

[9]王淑艷，楊鑫，李克秋.MapReduce框架下基于超平面投影劃分的Skyline計(jì)算[J].計(jì)算機(jī)研究與發(fā)展，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.