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

◆羅 云 陳佳瑜

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

◆羅 云 陳佳瑜

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

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

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

0 前言

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

在Skyline查詢(xún)計(jì)算中采用了Map-Reduce并行計(jì)算框架，使兩者結(jié)合起來(lái)處理海量數(shù)據(jù)查詢(xún)等問(wèn)題。在Map-Reduce框架下采用基于角度數(shù)據(jù)劃分的方法，提出了Cirl-Skyline查詢(xún)算法。為了在Map任務(wù)前刪除某些不能成為Skyline最終結(jié)果集的點(diǎn)，提高算法的執(zhí)行效率，在Cirl-Skyline查詢(xún)算法的基礎(chǔ)上給出Restrict-Skyline查詢(xún)優(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）表示某時(shí)間的屬性。Skyline結(jié)果集就是從某個(gè)數(shù)據(jù)庫(kù)中抽取不被其它任何數(shù)據(jù)對(duì)象支配的數(shù)據(jù)對(duì)象的集合。

定義1（支配[10]）給定d維的數(shù)據(jù)集D上的兩個(gè)數(shù)據(jù)點(diǎn)pi，qj，在任意一維度上pi（1≤i≤d）的取值都不小于數(shù)據(jù)點(diǎn)qj（1≤j≤d），且至少在某一維度上的取值pi比qj要大,稱(chēng)數(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)展

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

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

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

2 Map-Reduce框架下的Skyline查詢(xún)算法

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

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

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

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

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

Skyline查詢(xún)計(jì)算采用Map-Reduce“分而治之”的重要特征，將原有數(shù)據(jù)集劃分多個(gè)子數(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個(gè)分區(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查詢(xún)算法

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

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

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

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

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

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

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

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

Restrict-Skyline查詢(xún)算法分為兩部分:預(yù)處理和后序處理。首先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，對(duì)N個(gè)數(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è)置局部過(guò)濾值，在Map任務(wù)未執(zhí)行前，首先刪除一些Skyline結(jié)果集的點(diǎn)，使得Reduce輸入有所減少。數(shù)據(jù)點(diǎn)遞增排序之后隨機(jī)選取每個(gè)數(shù)據(jù)塊中局部過(guò)濾值。合并局部Skyline結(jié)果集，根據(jù)F（P）再次將合并后的局部Skyline結(jié)果集進(jìn)行排序，選取局部過(guò)濾值，刪除部分局部Skyline結(jié)果集。通過(guò)減少局部Skyline結(jié)果集，提高合并效率和算法的運(yùn)行時(shí)間。

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

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

本文的實(shí)驗(yàn)在4臺(tái)高配置的PC機(jī)組成的集群上運(yùn)行且配置相同。處理器為Intel Core i7 4790GHZ，內(nèi)存為4GB，操作系統(tǒng)為Windows 7。Hadoop版本為0.20.2，JDK的版本1.6。其中一臺(tái)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ù)類(lèi)型為浮點(diǎn)數(shù)，節(jié)點(diǎn)個(gè)數(shù)為6。三種數(shù)據(jù)集[1]如下:

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

⑵ 相關(guān):數(shù)據(jù)的某一維屬性的數(shù)值大（小），則數(shù)據(jù)的其它維屬性隨之也大（小）。

⑶ 反相關(guān):數(shù)據(jù)的某一維屬性的數(shù)值大（?。瑒t數(shù)據(jù)的另一維或其它所有維屬性都變?。ù螅?/p>

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

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

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

3.2.1 維度變化對(duì)Skyline算法時(shí)間性能的影響

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

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

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

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

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

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

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

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

4 總結(jié)

本文針對(duì)海量數(shù)據(jù)的查詢(xún)問(wèn)題，將Skyline與Map-Reduce并行框架結(jié)合，實(shí)現(xiàn)了Cirl-Skyline查詢(xún)算法和Restrict-Skyline查詢(xún)算法。兩種算法采用基于角度的劃分方法，有效的過(guò)濾重復(fù)計(jì)算Skyline點(diǎn)，Restrict-Skyline查詢(xún)算法設(shè)置約束范圍和全局過(guò)濾值，減少M(fèi)ap任務(wù)的輸入量，從而提高算法的運(yùn)行效率。通過(guò)數(shù)據(jù)集對(duì)兩種算法與MR-BNL算法進(jìn)行比較，分別改變數(shù)據(jù)規(guī)模，節(jié)點(diǎn)個(gè)數(shù)和維度驗(yàn)證Skyline查詢(xún)、Restrict-Skyline和MR-BNL算法在不同數(shù)據(jù)分布上運(yùn)行時(shí)間的性能。實(shí)驗(yàn)結(jié)果表明，本文提出的Restrict-Skyline算法在不部分情況下運(yùn)行效率高于Cirl-Skyline和MR-BNL算法，總體上提高了Skyline查詢(xún)時(shí)間和計(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]丁琳琳，信俊昌，王國(guó)仁等.基于Map-Reduce的海量數(shù)據(jù)高效 Skyline查詢(xún)處理[J].計(jì)算機(jī)學(xué)報(bào)，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.