劉建邦，劉旭敏

(首都師范大學 信息工程學院,北京 100048)

?

計算與測試

Mapreduce下改進Skyline的高效算法*

劉建邦，劉旭敏

(首都師范大學 信息工程學院,北京 100048)

目前基于MapReduce的Skyline算法隨著維度增大會陷入維度災難，不能高效地解決大數(shù)據(jù)條件下的計算問題。提出高效算法MRBPS,利用數(shù)據(jù)間的互不支配特性，通過一個優(yōu)化軸點對數(shù)據(jù)集建立區(qū)域標識，在Map和Reduce階段優(yōu)先比較每個點的區(qū)域標識，將多維比較簡化為一維比較，提高了計算效率，通過系統(tǒng)實驗證明：此算法在大數(shù)據(jù)量時能夠明顯提高計算效率，與現(xiàn)有算法相比具有高效性和可靠性。

Skyline查詢;MapReduce;大數(shù)據(jù)

0 引 言

Skyline查詢又稱Pareto查詢，主要目的是找出數(shù)據(jù)集中所有不被其他點支配的數(shù)據(jù)點集，廣泛應用于多目標決策和數(shù)據(jù)挖掘等領域，是數(shù)據(jù)庫領域的一個研究熱點，同時，隨著大數(shù)據(jù)時代的到來，人們開始關注并行Skyline計算，Mapreduce隱藏了并行計算的細節(jié)，如數(shù)據(jù)的分布式存儲，任務的調度，機器間通信和容錯處理，具有良好的容錯性和可靠性，非常適用于大數(shù)據(jù)的處理。目前MapReduce下的Skyline算法有MR-BNL算法，MR-SFS算法，MR-Bitmap算法等。

但是這些算法都有一個缺點，即隨著維度增加，都會出現(xiàn)維度災難的現(xiàn)象，通過研究，維度災難是因為多維度比較導致時間開銷急劇增大所致，本文提出MRBPS算法，通過優(yōu)化軸點對數(shù)據(jù)集增加一個位串的方法，在計算時將多維比較簡化為一維比較，減少比較次數(shù)，提高計算效率，實驗證明:本文提出的算法與MR-BNL算法和MR-SFS算法相比具有高效性和可靠性。

1 Skyline算法

定義1 支配。數(shù)據(jù)集中的兩個點p和q，當任意i∈(1，d),pi≤qi,且至少存在一個i，使得pi

定義2 Skyline集。若p點不被數(shù)據(jù)集中任何點支配，就說p點是Skyline點，所有這樣的點構成Skyline集，在這個集合中，所有的點都是互相不支配的。

傳統(tǒng)的Skyline算法都是集中式算法，如塊嵌套循環(huán)(block-nested-loops,BNL)算法[1]，分治(divide and conquer,D&C)算法[1]，排序過濾(sort-filter-skyline,SFS)算法[2]，最近鄰(nearest-neighbor，NN)算法[3]，分支界限(branch and bound skyline，BBS)算法[4]，排序限定算法(sort and limit skyline algorithm,SaLSA)[5]等。其中BBS算法在維數(shù)較低(小于六維)時，是效率最高的算法。

由于數(shù)據(jù)量的增大以及數(shù)據(jù)存儲的物理源相距較遠時，傳統(tǒng)集中式算法不能滿足計算要求，并行Skyline計算成為人們關注的熱點。Balke等人提出了Web信息系統(tǒng)上的分布式Skyline計算[6]，通過對每一維數(shù)據(jù)排序，優(yōu)先比較可能性較大的點，節(jié)約了開銷，效率較高。文獻[7]提出了基于數(shù)據(jù)劃分的并行分布式Skyline算法，對劃分的各組進行并行計算。

2 Mapreduce下Skyline算法

MapReduce[8]最早由谷歌公司于2004年提出，是一種并行編程框架，簡單來說就是“任務的分解與結果的匯總”，它將任務在Map階段分為一個個子任務，然后用多臺機器并行處理鍵值對(key,value)形式的數(shù)據(jù)，最后再將結果在Reduce階段合并，從而得出最終結果。圖1是MapReduce的工作示意圖。

圖1 MapReduce工作示意圖Fig 1 MapReduce framework

目前在MapReduce框架下對Skyline計算的研究比較有限，主要有MR-BNL算法[9,10]，MR-SFS算法[9,10]和MR-Bitmap算法[9,10]。MR-BNL算法通過對數(shù)據(jù)分塊，首先計算出部分數(shù)據(jù)集的Skyline結果，然后在對部分Skyline結果進行合并計算，得出最終Skyline集合。MR-SFS算法對數(shù)據(jù)增加了一個預排序環(huán)節(jié)，可以看做MR-BNL算法的改進。MR-Bitmap算法首先對每一個數(shù)據(jù)建立Bitmap，第二階段再進行Skyline計算，當Bitmap較小時算法效率較高，但當Bitmap太大無法放入內存時，算法性能下降顯著，因此MR-Bitmap算法應用較少。隨著維度增大，MR-BNL算法和MR-SFS算法會陷入維度災難的陷阱中，開銷較高。

3 MRBPS算法

3.1 算法基本思想

MR-BNL算法和MR-SFS算法在大數(shù)據(jù)情況下，隨著維度增加，點和點之間的比較次數(shù)增加太快，需要花費很多開銷，導致兩種算法效果并不好。目前的改進算法都是采用過濾的方法排除部分非Skyline點，如文獻[11]和文獻[12]。本文采用一種新穎的方法，利用數(shù)據(jù)之間的互不支配特性來提高MapReduce下Skyline計算的效率，用一維比較確定兩個數(shù)據(jù)的互不支配關系，減少比較次數(shù)，從而提高計算效率。

文獻[13]討論了數(shù)據(jù)集中最大化互不支配對數(shù)的軸點的計算方法Slectpivotpoint算法，為了盡可能增加劃分后數(shù)據(jù)的互不支配對數(shù)，本文采用效率較高的滿足平衡條件(各維度值相差最小)的Skyline點作為區(qū)域劃分的軸點。Slectpivotpoint算法步驟：初始化BP點為第一個點，cur=2，minscore=score(BP);While(cur≤n),如果BP支配S[cur],cur=cur+1;如果S[cur]支配BP，BP=S[cur]，minscore=score(BP),cur=2;如果BP和S[cur]互不支配，curscore=score(S[cur]),當curscore

3.2 算法流程

MapReduce在Map階段將數(shù)據(jù)劃分成64 MB的小塊，這樣的數(shù)據(jù)可以直接放入內存中處理，本文第二階段計算Skyline點時采用文獻[18]提出的內存算法sskyline進行計算，比MR-BNL算法和MR-SFS算法所采用的外存算法效率要高。sskyline算法步驟如下：

1)head=1,tail=n,While(head

2)While(i≤tail),if S[head]支配S[i]，S[i]=S[tail]，tail=tail-1;if S[i]支配S[head],S[head]=S[i],S[i]=S[tail],tail=tail-1,i=head+1;如果S[head]和S[i]互相不支配，i=i+1；

3)內循環(huán)結束時,當head

4)外循環(huán)結束時，輸出S[1,……,head]，即為Skyline集。

MRBPS算法的步驟共分兩個階段的MapReduce計算，第一階段先利用橫向劃分在第一階段并行運行Slectpivotpoint算法得到部分localBP點，在MapReduce中是用(N，localBP)這樣的鍵值對來處理的，N代表每一個子節(jié)點的編號。然后通過Reduce得到最終的BP點，存放在Distri-butedCache中等待第二階段調用(算法1的第1～8行)。第二階段利用BP點對每個點進行區(qū)域標識，為每個數(shù)據(jù)增加一個長度為d的位串D(算法1的第12行)，具體實現(xiàn)方法為：數(shù)據(jù)集中每一個點p，i∈(1,d)，若pi

算法1 MRBPS算法

Input:Dataset S

Output:Skyline(S)

Description:

1.Prepare Job

2.Map Task

3.compute localBP using Slectpivotpoint

4.output (N,localBP)

5.

6.Reduce Task

7.compute globalBP using Slectpivotpoint

8.output globalBP in Distributed Cache

9.

10.Processing Job

11.Map Task

12.compute regionID by BP

13.compute localSkyline with precompare using sskyline

14.output(N,localSkyline)

15.

16.Reduce Task

17.compute globalSkyline with precompare using sskyline

18.output(pj&BP,null)

4 實驗評估

4.1 實驗環(huán)境

本文實驗采用五臺機器，配置相同：處理器Intel(R)Core(TM)i3-3220，CPU @3.3 GHz，4 GB內存，500 G硬盤；操作系統(tǒng)windows 7；Hadoop版本為0.20.2，在JDK1.7環(huán)境下編程實現(xiàn)。

實驗數(shù)據(jù)集采用文獻[1]的方法，每維值域在[0，1]，數(shù)據(jù)集大小為200～1 000 K，默認為400 K。默認維度為4維。分為相關分布、獨立分布、反相關分布三種。獨立分布的數(shù)據(jù)每一維都是相互獨立的，相關分布的數(shù)據(jù)在某一維度較好則其他維度也較好，反相關分布的數(shù)據(jù)在某一維度較好而其他維度較差。實驗指標為不同維度下和不同數(shù)據(jù)量下算法的運行時間。圖2顯示了二維下100個點的相關分布、獨立分布、反相關分布情況。

圖2 三種數(shù)據(jù)集分布Fig 2 Distribution of three kinds of dataset

從圖2可以看出，相關數(shù)據(jù)集Skyline點結果比較小，獨立分布數(shù)據(jù)集次之，反相關數(shù)據(jù)集Skyline點結果最多。故只選取獨立和反相關數(shù)據(jù)集進行實驗比較。

4.2 實驗結果與分析

4.2.1 Skyline查詢性能隨數(shù)據(jù)維度變化情況

圖3顯示了維度變化時，運行三種算法耗費的時間情況，從獨立分布的結果可以看出，隨著維度的增大，三種算法耗費的時間都有所增加，這是因為隨著維度的增大，互不支配的點增多，運算時間也會增加，而MRBPS算法因為在互不支配點時節(jié)約了比較次數(shù)，時間效率上要優(yōu)于前兩種算法，從反相關分布的結果可以看出，當維度增大到四維以上時，MR-SFS算法和MR-BNL算法運行時間都出現(xiàn)急劇的增大，產(chǎn)生了“維度災難”現(xiàn)象，而MRBPS算法因為需要較少的比較次數(shù)，“維度災難”影響較小。

圖3 不同維度下三種算法運行時間Fig 3 Runtime of three kinds of algorithms with different dimensions

4.2.2 Skyline查詢性能隨數(shù)據(jù)量變化情況

從圖4可以看出，隨著數(shù)據(jù)量的增大，三種算法運行時間都增加，MR-SFS算法和MR-BNL算法相差不多，這是因為MR-SFS算法可以看做是MR-BNL算法的改進，而前一種算法需要一個預排序過程，比較耗費時間。MRBPS算法比前兩種算法都要快，這是因為使用軸點劃分區(qū)域后，在Map和Reduce階段將多維比較簡化為一維比較，減少了比較次數(shù)，節(jié)約了運算時間。

圖4 不同數(shù)據(jù)量下三種算法運行時間Fig 4 Runtime of three algorithms of different data quatities

5 結束語

本文對大量數(shù)據(jù)下，現(xiàn)有的基于MapReduce的Skyline算法隨著維度增加陷入維度災難，造成計算效率低的問題，提出MRBPS算法，利用軸點劃分區(qū)域，在MapReduce計算時將多維比較簡化為一維比較，減少比較次數(shù)，經(jīng)過系統(tǒng)實驗驗證，本文提出的算法具有高效性和可靠性。

[1] Borzsonyi S,Kossmann D,Stocker K.The skyline operator[C]∥Proceedings of 2001 the 17th International Conference on Data Engineering(ICDE),Washington DC,USA:IEEE Computer Society,2001:421-430.

[2] Chomicki J,Godfrey P,Gryz J,et al.Skyline with presor-ting[C]∥Proceedings of 2003 the 19th International Conference on Data Engineering(ICDE),Los Alamitos,CA,USA,Washington DC,USA:IEEE Computer Society,2003:717-719.

[3] Kossmann D,Ramsak F,Rost S.Shooting stars in the sky:An online algorithm for Skyline queries[C]∥Proceedings of 2002 the 28th International Conference on Very Large Data Bases(VLDB),Hong Kong,China,San Francisco,CA,USA:Morgan Kaufmann,2002:275-286.

[4] Papadias D,Tao Y,Fu G,et,al.Progressive computation in database systems[J].ACM Transactions on Database Systems,2005,30(1):41-28.

[5] Bartolini I,Ciaccia P,Patella M.Efficient sort-based Skyline evaluation[J].ACM Transactions on Database Systems,2008,33(4):31-79.

[6] Balke W T,Guntzer U,Zheng J X.Efficient distributed skylining for Web information systems[C]∥Proceedings of 2004 the 9th International Conference on Extending Data-base Technology(EDBT),Heraklion,Crete,Greece:Springer,2004:256-273.

[7] Cui Bin,Lu Hua,Xu Quanqing,et al.Parallel distributed processing of constrained Skyline queries by filtering[C]∥Procee-dings of 2008 the 24th International Conference on Data Engineering,ICDE’08,Cancun,Mexico,Washington,DC,USA:IEEE Computer Society,2008:546-555.

[8] Dean J,Ghemawat S.MapReduce:Simplified data processing on large cluster[C]∥Proceedings of 2004 the 6th Conference on Operating Systems Design &Implementation(OSDI),Berkeley,CA,USA:USENIX Association,2004:137-150.

[9] Zhang Boliang,Zhou Shuigeng,Guan Jihong.Adapting Skyline computation to the MapReduce framework:Algorithms and experiments[C]∥Proceedings of DASFAA Workshops,Hong Kong,China:Springer,2011:403-414.

[10] 張波良,周水庚,關佶紅.Mapreduce框架下的Skyline計算[J].計算機科學與探索,2011,5(5):385-397.

[11] 丁琳琳,信俊昌,王國仁,等.基于Map-Reduce的海量數(shù)據(jù)高效Skyline查詢處理[J].計算機學報,2011，34(10)：1785-1796.

[12] 李文俊,張大方,李 瑋.基于MapReduce的預處理高效Skyline算法[J].計算機應用與軟件,2015,32(3):243-246.

[13] Lee J,Hwang S.Scalable Skyline computation using a balanced pivot selection technique[J].Information Systems,2014,39(1)1-21.

[14] Park S,Kim T,Park J,et al.Parallel Skyline on multicore architectures[C]∥Proceedings of 2009 the 25th International Con-ference on Data Engineering,ICDE’09,Shanghai:IEEE,2009:760-771.

劉建邦(1988-)，山東濰坊人，碩士，主要研究方向為數(shù)據(jù)挖掘，大數(shù)據(jù)處理。

Improved efficient skyline algorithm based on Mapreduce*

LIU Jian-bang,LIU Xu-min

(College of Information Engineering,Capital Normal University,Beijing 100048,China)

Existing Mapreduce-based Skyline algorithms is inefficient facing large scale database,to solve this problem,an MapReduce with balanced point skyline(MRBPS)algorithm is proposed,using incomparability of dataset,map points to different regions with a computed balanced point,simplified multi-dimensional comparison to one dimensional comparison，reduce number of tests in Map and Reduce Task.Systematic experiments prove that the algorithm is efficient in large scale database,and more efficient and reliable than existing algorithms.

Skyline query;MapReduce;big data

10.13873/J.1000—9787(2016)11—0116—04

2016—01—22

國家自然科學基金資助項目(61272029)

TP 311

A

1000—9787(2016)11—0116—04