馬學森, 王曉潔, 韓江洪, 王營冠

(1.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009;2.中國科學院 上海微系統(tǒng)與信息技術研究所 無線傳感網(wǎng)絡與通信重點實驗室,上海 200050)

MapReduce框架下的Skyline結(jié)果優(yōu)化算法*

馬學森1,2, 王曉潔1, 韓江洪1, 王營冠2

(1.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009;2.中國科學院 上海微系統(tǒng)與信息技術研究所 無線傳感網(wǎng)絡與通信重點實驗室,上海 200050)

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)量和數(shù)據(jù)復雜度急劇提高，Skyline查詢結(jié)果集規(guī)模巨大，無法為用戶提供精確的信息。MapReduce作為并行計算框架，已廣泛應用于大數(shù)據(jù)處理中。本文提出了MapReduce框架下基于支配個數(shù)的結(jié)果優(yōu)化算法(MR-DMN)，解決了大數(shù)據(jù)環(huán)境下的Skyline結(jié)果集優(yōu)化問題。大量的實驗表明：算法具有良好的時間和空間效率。

大數(shù)據(jù); MapReduce; Skyline; 支配個數(shù)

0 引 言

Skyline查詢[1]是指從給定數(shù)據(jù)集中選擇一組不被其他數(shù)據(jù)支配的數(shù)據(jù)，所謂支配是指一個數(shù)據(jù)在所有維度上都不比其他數(shù)據(jù)差，且至少在一個維度上優(yōu)于其他數(shù)據(jù)。典型的Skyline查詢例子是業(yè)務選擇問題，由于經(jīng)營調(diào)整，企業(yè)需要保留一些銷量高且單件利潤高的業(yè)務，Skyline查詢的結(jié)果集是銷量和利潤上都不比其他業(yè)務差，且至少在一個屬性上優(yōu)于其他的業(yè)務。Skyline查詢廣泛應用于用戶推薦、決策支持以及數(shù)據(jù)可視化等領域。

在現(xiàn)實生活中，數(shù)據(jù)在各個維度上的取值是有優(yōu)有劣的，隨著數(shù)據(jù)維度的增大，支配的條件越來越難滿足，一個點支配另一個點的可能性越來越小，因此,結(jié)果集中將包含很多互不支配的數(shù)據(jù)點。隨著大數(shù)據(jù)環(huán)境下數(shù)據(jù)量和數(shù)據(jù)復雜度的提高，Skyline查詢結(jié)果集的規(guī)模急劇增大。在隨機數(shù)據(jù)集中，Skyline結(jié)果集數(shù)量為Θ(lnd-1n/(d-1)!)[2]。

如何為用戶選取規(guī)模較小，更具有代表性的結(jié)果集，提高大數(shù)據(jù)下Skyline結(jié)果集的質(zhì)量，成為急需解決的問題。近年來興起的MapReduce并行計算框架[3]廣泛應用于大數(shù)據(jù)及云計算[4]處理中，本文將Skyline結(jié)果集優(yōu)化算法與MapReduce框架相結(jié)合，提出了大數(shù)據(jù)下Skyline結(jié)果集優(yōu)化算法。提出了MapReduce框架下的基于支配個數(shù)的算法(MapReduce dominant number-based algorithm,MR-DMN)。實驗結(jié)果表明：MR-DMN具有良好的時間和空間性能。

1 相關工作

1.1 基本概念

Skyline查詢是指從給定的一個d維空間數(shù)據(jù)點集合D中選擇一個子集，該子集中的任意一個點都不能被D中其他點所支配。具體來說，給定d維數(shù)據(jù)空間S={s1,s2,…,sd}(d∈N*)上的數(shù)據(jù)集合D={P1,P2,…,Pn}(n∈N*)，D中的每一個數(shù)據(jù)點Pi是S空間中的一個d維數(shù)據(jù)點，Pi.sj表示數(shù)據(jù)點Pi的第j維度的值。為了簡便，不失一般性，本文中假設數(shù)據(jù)點越大越優(yōu)。

定義1支配(dominate)：給定數(shù)據(jù)集D中的兩點Pi,Pj(i,j∈[1,n])，稱Pi支配Pj,當且僅當對于?si∈S(i∈[1,d])，都有Pi·si≥Pj·si，并且?t∈[1,d]，使得Pi·st>Pj·st。

定義2Skyline集(Skyline(D))：對于?Pi∈D，稱Pi為D中的Skyline點, 當且僅當在D中不存在支配Pi的數(shù)據(jù)點。D中所有Skyline數(shù)據(jù)點構(gòu)成了D上的Skyline數(shù)據(jù)集，記作Skyline(D)。

1.2 Skyline結(jié)果集優(yōu)化算法

為了對Skyline查詢結(jié)果集進行優(yōu)化，為用戶返回更具有代表性的結(jié)果集。有學者提出返回k個最具有代表性的結(jié)果點代表整個結(jié)果集，該算法主要分為以下三類：

1)Top-k查詢算法

Top-k查詢算法[5]利用單調(diào)打分函數(shù)對每個數(shù)據(jù)的維度值進行聚集，得到單一的打分值，按照打分值對所有數(shù)據(jù)進行排序，選出前k個數(shù)據(jù)作為最終結(jié)果返回給用戶。例如在圖1的示例中，假設打分函數(shù)為F=x+y，則top-3查詢結(jié)果為B(6,9),C(7,8),D(9,7)三點。top-k查詢的優(yōu)勢是用戶可以通過參數(shù)k控制返回結(jié)果的數(shù)量，由于結(jié)果對象的選取依賴于打分函數(shù)，因此,適當?shù)剡x取打分函數(shù)成為解決問題的關鍵。同時，Top-k查詢的結(jié)果是根據(jù)打分函數(shù)選擇的，數(shù)據(jù)點之間沒有進行支配比較，因此,其結(jié)果不一定是Skyline點。

圖1 原始數(shù)據(jù)集示例

2)Top-k支配

同樣為了有效地返回k個具有代表性的結(jié)果點，top-k支配(top-k dominating)查詢[6]的主要思想是，一個點的重要程度可以用該點所支配的其他點個數(shù)μ(p)來衡量。top-k支配查詢根據(jù)μ(p)值對數(shù)據(jù)集排序，返回μ(p)值最高的k個點作為查詢結(jié)果。例如，圖2示例中top-4支配查詢的結(jié)果是B(6,9),C(7,8),D(9,7),E(9,5)。

文獻[6]提出了計算top-k支配查詢的基本方法，即先計算原始數(shù)據(jù)集的Skyline集，找到top-1支配Skyline點p，之后將p移出數(shù)據(jù)集D，迭代查找下一個點，直到找到k個點。文獻[7]對傳統(tǒng)的R-tree算法改進，得到聚合R-tree，該算法可以并行計算數(shù)據(jù)點的打分值，依據(jù)打分值優(yōu)先級遍歷搜索所有樹節(jié)點。當數(shù)據(jù)量很大時，構(gòu)建索引的代價將非常大。文獻[8]提出了分布式環(huán)境下的top-k支配查詢，避免了多余的通信開銷和延遲。

3)k個最具有代表性的Skyline點查詢算法

在top-k支配查詢算法中仍存在一些問題，該算法的結(jié)果可能包含非Skyline點，如在上述例子中，top-4支配查詢結(jié)果中的E(9,5)不是Skyline點。這也反映出Skyline查詢的特點：在Skyline計算中，盡管一個點支配了很多非Skyline點，最終仍可能被其他Skyline點支配掉，無法成為Skyline點。相反可能有些點支配其他點的個數(shù)并不多，它仍是Skyline點，如圖2中的點A(1,10)。

為了解決top-k支配存在的問題，Lin X M等人提出從Skyline結(jié)果集中選擇k個最有代表性的Skyline點(top-krepresentative skyline points,top-kRSP)查詢算法[9]。給定一個數(shù)據(jù)集D和參數(shù)k，得到包含k個Skyline點的集合S，使得|D(S)|取得最大值，|D(S)|表示所有被S中的點支配的點的數(shù)量。Top-kRSP算法兼具了Skyline查詢和Top-k查詢的優(yōu)點，不需要依賴具體的打分函數(shù)，且有效控制了Skyline查詢結(jié)果集數(shù)量。

作者提出了針對二維數(shù)據(jù)Top-kRSP查詢的動態(tài)編程算法，該算法的內(nèi)存開銷為O(m2)(m為Skyline點數(shù)量)。作者證明三維及以上數(shù)據(jù)的top-kRSP算法是NP-hard問題，提出貪婪算法(greedy algorithm,GDY)[9]，算法首先計算出所有Skyline結(jié)果，接著再次掃描數(shù)據(jù)集計算出每個Skyline點的支配個數(shù)，得到支配個數(shù)最多的k個點。為了保存每個Skyline點支配數(shù)據(jù)點的內(nèi)存開銷為O(mn)(n為數(shù)據(jù)集D的大小)，當維度達到5維時，45 %的被支配點會被寫入內(nèi)存中，將產(chǎn)生很大的I/O開銷。

1.3 MapReduce并行計算框架

MapReduce是一個分布式并行計算框架，已廣泛應用于大數(shù)據(jù)的計算中。它的基本思想是分治法，主要由兩個階段的任務組成：Map Task和Reduce Task。對于具有較少依賴關系的數(shù)據(jù)，用一定的數(shù)據(jù)劃分方法對數(shù)據(jù)進行劃分，每個數(shù)據(jù)分片交給一個Map Task處理，Reduce Task負責對Map的結(jié)果進行匯總整理和輸出。Map Task將讀取的數(shù)據(jù)分片解析為(key，value)對，調(diào)用用戶自定義的map()函數(shù)進行處理，并將結(jié)果映射成新的(key，value)對存放在本地磁盤上；Reduce Task讀取Map Task的結(jié)果，調(diào)用reduce()函數(shù)處理，最后按照(key，value)對的形式輸出到HDFS文件系統(tǒng)上。Map和Reduce任務在輸出數(shù)據(jù)時，會按照key值對數(shù)據(jù)記錄排序輸出。

2 MapReduce下的top-k RSP算法

傳統(tǒng)的top-kRSP算法通常采用索引結(jié)構(gòu)，數(shù)據(jù)點建立索引將產(chǎn)生巨大的內(nèi)存和I/O開銷，無法應用于大數(shù)據(jù)環(huán)境。GDY不需要構(gòu)建索引，但需要多次遍歷整個數(shù)據(jù)集求出每個Skyline點支配的其他點，需要大量額外的內(nèi)存空間保存被支配的點，其時間和空間效率還有待提高。本文將GDY算法應用到MapReduce框架下，并對MR-GDY算法(MapReduce-based greedy algorithm, MR-GDY)進行改進，首次提出了大數(shù)據(jù)環(huán)境下的top-kRSP算法中的MR-DMN算法在進行數(shù)據(jù)支配比較的同時，記錄每個點的支配個數(shù)，從而為用戶返回支配個數(shù)最多的k個Skyline點。

2.1 MR-DMN算法原理

根據(jù)top-kRSP查詢的定義，該算法返回Skyline結(jié)果集中k個支配個數(shù)最多的Skyline點。因此，MR-DMN算法在進行數(shù)據(jù)點間的支配比較時，記錄每個數(shù)據(jù)點的支配個數(shù)。具體來說：窗口隊列w用于保存暫時的Skyline點，進入窗口的數(shù)據(jù)點p將被附加一個標記位num(p)，用于標記該點支配的數(shù)據(jù)點個數(shù)。第一個數(shù)據(jù)點將被放入窗口中，num(p)置為0。接下來，每讀取一個新的數(shù)據(jù)點q都會與窗口中的所有點進行比較，將會出現(xiàn)以下三種情況(新數(shù)據(jù)點q的初始num值為0)：

1)若窗口中存在點p支配q，則將q刪除，由于支配具有傳遞性，p可以支配q支配的所有點，并且可以支配q，因此,更新num(p)，num(p)=num(p)+num(q)+1。

2)若點q支配窗口中的點p,則將p從窗口中刪除,同時將q加入窗口隊列。若q支配p，則q可以支配p所支配的所有點，并可以支配p,因此,num(q)=num(q)+num(p)+1。

3)若q與窗口中的所有點比較后，與所有數(shù)據(jù)點均互不支配，原來窗口中的點num值不變，將q加入窗口中，num(q)置為0。

MR-DMN算法的難點在于計算每個Skyline點的支配個數(shù)，在上述比較中，若點q被支配，則將它直接刪除。然而可能其他點也會支配該點，由于失去了與該點比較的機會，其他點的num值可能會產(chǎn)生偏差。例如圖2中的點G(3，8)，它同時被兩個點B(6,9),C(7,8)支配，若G被B支配后被直接刪除，那么G無法與C比較，C的支配個數(shù)將會比實際結(jié)果小1。因此，在MR-DMN算法中，若一個新點q被支配，不應立即將它刪除，而將它與臨時窗口中的所有點進行比較后再刪除。與此同時產(chǎn)生另一個問題，即若此時C點還沒有進入臨時窗口中，C點也無法與G點進行比較，從而導致C的num值計算不準確。如果將支配能力[10]較強的點優(yōu)先放在窗口中，那么它們與每個被支配的點都會有比較的機會，這樣計算得出的num(p)會更準確。同時，若將支配能力強的點放在隊列前面，可以避免后面的點支配前面的點，避免了數(shù)據(jù)的換入換出，從而加快Skyline結(jié)果的計算。因此，算法引入?yún)⒖嘉墨I[10]中數(shù)據(jù)點支配能力的計算方法

(1)

在MR-DMN算法中，Map階段首先對數(shù)據(jù)點按照支配能力大小進行排序，再進行數(shù)據(jù)點間的支配比較，在數(shù)據(jù)點支配比較的過程中記錄每個數(shù)據(jù)點的num值，最后按照num值大小降序輸出到Reduce階段。在Reduce階段，匯總所有Map階段的輸出結(jié)果，對所有數(shù)據(jù)點再進行一次支配比較，最終返回支配個數(shù)最大的k個Skyline點。

2.2 MR-DMN算法流程

1)Map階段：整個數(shù)據(jù)集被劃分到2個Map任務中，在每個Map任務中數(shù)據(jù)點進行排序后，開始數(shù)據(jù)點間的支配比較。在第一個Map任務中，數(shù)據(jù)點(7,8)分別支配數(shù)據(jù)點(5,6),(4,7),(3,8),(4,6),(5,4),(6,3),(3,2)，共7個數(shù)據(jù)點，因此,num(7,8)=7。同理,num(6,9)=7，(1,10)由于未支配任何數(shù)據(jù)點，num(1,10)=0。在第二個Map任務中，數(shù)據(jù)點(8,7)支配點(7,7),(6,7),(8,5),(7,4),(6,4),(4,5)，num(8,7)=6，(9,6)支配了點(8,5),(9,4),(7,4),(6,4),(4,5)，num(9,6)=5,num(10,2)=0。當所有數(shù)據(jù)點比較結(jié)束后，每個Map任務的結(jié)果按照num(p)值降序輸出到Reduce階段。

2)Reduce階段：匯總所有Map任務的輸出結(jié)果，對所有數(shù)據(jù)點再進行一次支配比較。數(shù)據(jù)點(8,8)支配點(7,8)，因此,num(8,8)=num(8,8)+num(7,8)+1=6+7+1=14。所有數(shù)據(jù)點比較結(jié)束后，輸出k個num(p)值最大的Skyline點，本例中取k值為3，最終結(jié)果為(8,8),(6,9), (9,6)。MR-DMN算法流程如圖2所示。

圖2 MR-DMN算法流程

3 MR-DMN算法實驗

3.1 實驗環(huán)境

本文實驗用機的配置為：內(nèi)存4GB，操作系統(tǒng)為Windows7，處理器為Intel(R)Core(TM)i5-3210MCPU@ 2.50GHz。在Ubuntu環(huán)境下模擬了Hadoop偽分布式環(huán)境，算法全部用Java實現(xiàn)，Eclipse的版本為3.3.2，在JDK1.6環(huán)境下編譯，Hadoop的版本為0.20.2。

本文實驗利用文獻[1]中的標準數(shù)據(jù)生成工具生成了正相關、反相關和獨立分布的實驗數(shù)據(jù)。每個數(shù)據(jù)集的數(shù)據(jù)量為2～10M，數(shù)據(jù)維度從2～8變化，默認維度是5。將本文中提出的MR-DMN算法與MR-GDY算法進行比較。由于正相關分布下算法查詢性能與獨立分布下相似，因此,本次實驗主要分析獨立分布和反相關分布下的算法性能。

3.2 時間效率分析

1)本次實驗測試了算法運行時間與數(shù)據(jù)量之間的關系，分別測試了反相關分布及獨立分布下的4維數(shù)據(jù)，數(shù)據(jù)量從2M變化到10M的運行時間，實驗結(jié)果如圖3(a)和3(b)所示。隨著數(shù)據(jù)量的增大，算法時間增加，獨立分布數(shù)據(jù)集的運行時間遠小于反相關分布下的運行時間。這主要是由于反相關分布數(shù)據(jù)各維度取值相異，在進行支配判斷時需進行大量比較，因此算法運行時間較長。由于MR-GDY算法需要進行多輪全局的比較才能得出結(jié)果，而MR-DMN算法只需訪問一次數(shù)據(jù)集即可求得結(jié)果，因此,MR-DMN算法運行時間有明顯縮減。

圖3 反相關及獨立數(shù)據(jù)集運行時間與數(shù)據(jù)量關系

2)本次實驗測試了算法運行時間與維數(shù)之間的關系，測試了在2M數(shù)據(jù)集下，反相關以及獨立分布下數(shù)據(jù)維數(shù)由2變化到8的運行時間，實驗結(jié)果分別如圖4(a)和4(b)所示。從實驗結(jié)果看，反相關分布的運行時間對維度比較敏感，當維度增大時，數(shù)據(jù)點間不相互支配的情況增多，從而導致結(jié)果集變大，運行時間增加。而獨立分布下，結(jié)果集隨維度增加變化不大，因此，算法運行時間的增加沒有反相關分布下明顯。

圖4 反相關及獨立數(shù)據(jù)集運算時間與維數(shù)關系

3)本次實驗測試了算法運行時間與k值之間的關系。分別測試了反相關分布以及獨立分布下，k值從10變化到50的運行時間變化，實驗結(jié)果分別如圖5(a)和5(b)所示。由于MR-GDY算法中需要不斷合并新的數(shù)據(jù)點，因此,當k值增大時算法時間變長。

圖5 反相關及獨立數(shù)據(jù)集運行時間與k值關系

3.3 空間效率分析

由于MR-GDY算法需要保存所有Skyline點支配的點，因此將產(chǎn)生較大的內(nèi)存開銷。在二維數(shù)據(jù)集上，MR-GDY所需的內(nèi)存空間為整個數(shù)據(jù)集的2倍，而當數(shù)據(jù)維度為5時，MR-GDY所需要的內(nèi)存空間為整個數(shù)據(jù)集的數(shù)十倍以上。MR-DMN算法僅需要增加一位用于存儲該數(shù)據(jù)點的支配個數(shù)，除此之外不需要額外的存儲空間，所需內(nèi)存空間最大為原始數(shù)據(jù)集的1+1/d倍(d為數(shù)據(jù)維數(shù))，因此,MR-DMN具有良好的空間效率。

4 結(jié) 論

本文在分析了傳統(tǒng)Skyline結(jié)果優(yōu)化算法的基礎上，針對大數(shù)據(jù)環(huán)境下的Skyline結(jié)果集優(yōu)化問題，提出了MapReduce框架下基于支配能力的優(yōu)化算法MR-DMN。MR-DMN在進行支配比較的同時，計算每個Skyline點的支配個數(shù)，選取支配個數(shù)最大的k個點作為返回結(jié)果。實驗結(jié)果表明:MR-DMN算法在大數(shù)據(jù)環(huán)境下，相對于傳統(tǒng)的MR-GDY算法，時間效率和空間效率有了明顯的提高。

[1]BorzsonyiS,KossmannD,StockerK.TheSkylineoperator[C]∥Proceedingsofthe17thInternationalConferenceonDataEngineering(ICDE),2001:421-430.

[2]ChanC,JagadishHV,TianKL,etal.Onhighdimensionalskylines[C]∥AdvancesinDatabaseTechnology,2006:478-495.

[3] 張建平,李 斌,劉學軍,等.基于Hadoop的異常傳感數(shù)據(jù)時間序列檢測[J].傳感技術學報,2014,27(12):1660-1665.

[4] 劉東平,馬利亞,楊 軍.云環(huán)境下異構(gòu)無線傳感器網(wǎng)絡節(jié)點調(diào)度改進算法[J].傳感器與微系統(tǒng),2015,34(10):128-132.

[5]TaoY,XiaoP．Efficientskylineandtop-kretrievalinsubspace-s[J].TransactionsonKnowledgeandDataEngineering,2007,19(8):1072-1088.

[6]YiuML,MamoulisN.Multi-dimensionaltop-kdominatingqueries[J].VLDBJournal,2009,18(3):695-718.

[7] 韓希先,楊東華.TKEP:海量數(shù)據(jù)上一種有效的Top-kDominating查詢處理算法[J].計算機學報,2010,33(8):1405-1417.

[8]AmagataD,SasakiY.Efficientprocessingoftop-kdominatingqueriesindistributedenvironments[C]∥WorldWideWeb,2015:1-33.

[9]LinXM,YuanYD,ZhangQ,etal.Selectingstars-thekmostrepresentativeskylineoperator[C]∥The23rdInternationalConferenceonDataEngineering(ICDE),2007:86-95.

[10] 印 鑒,姚樹宇,薛少鍔,等.一種基于索引的高效k—支配Skyline算法[J].計算機學報,2010,33(7):1237-1245.

作者簡介:

馬學森(1977-)，男，博士，副教授，主要從事網(wǎng)絡與信息安全、物聯(lián)網(wǎng)研究工作。

Skyline result optimization algorithm based on MapReduce framework*

MA Xue-sen1,2, WANG Xiao-jie1, HAN Jiang-hong1, WANG Ying-guan2

(1.School of Computer & Information,Hefei University of Technology,Hefei 230009,China;2.Key Laboratory of Wireless Sensor Networks & Communication,Shanghai Institute of Microsystem and Information Technology,Chinese Academy of Sciences,Shanghai 200050,China)

With the advent of big data,data volume and complexity increase drastically,Skyline query result set is so large that it can’t provide precise information to the users.As parallel computing framework,MapReduce has been widely applied to big data processing.A result optimal algorithm, MapReduce-based dominant number algorithm(MR-DMN)is proposed,based on dominating number under MapReduce framework,which solves problem of optimization of Skyline result set in big data environments.Lots of experiments show that the algorithm has good time and space efficiency.

big data; MapReduce; Skyline; dominant number

2016—03—24

國家自然科學基金資助項目(61370088)；國家科技支撐計劃資助項目(2013BAH51F01)；安徽省高校自然科學研究基金資助項目(KJ2012A233)；中國科學院無線傳感網(wǎng)絡與通信重點實驗室開放課題資助項目(2013003)

10.13873/J.1000—9787(2017)02—0146—04

TP 274

A

1000—9787(2017)02—0146—04

林 娟(1992-)，女，通訊作者，碩士研究生，主要研究方向為信號處理。