基于M apReduce的Skyline查詢優化算法?

楊 啟 王 芳 黃樹成

（江蘇科技大學計算機科學與工程學院 鎮江 212003）

1 引言

Skyline查詢指從一個數據庫中找到最優的數據集合。典型的Skyline查詢例子如圖1所示，某個游客去海濱城市旅游，他想找一個離海邊近并且價格便宜的酒店。這時游客可以考慮選擇折線上的點，那些不在折線上的數據點，其價格和距離沒有折線上的點更優。

隨著數據量的海量增長，傳統的單服務器的串行算法已經不能滿足人們的需求。MapReduce計算框架［3］廣泛應用于大數據以及云計算處理中，因此可以用MapReduce框架來處理Skyline查詢。在海量數據中，Skyline查詢結果集遠小于原始數據集，本文將支配能力較強的數據點優先地對數據進行過濾，能夠有效地過濾一大部分非Skyline數據點，減少Map任務和Reduce任務的輸入，使得查詢效率更高。

圖1 一個關于酒店的Skyline查詢實例

2 相關工作

2.1 Skyline查詢

Skyline的定義與性質:設d維的數據集S=（S1，S2，…，Sd），S 上每一維屬性 S1，S2，…，Sd都是全序集，記全序關系為?，對任意的 x，y∈Si，x?y，表示x的取值優于y。全序關系可以根據用戶偏好定義。

定義 1（支配［4］dominate）給定 d 維的數據集 S上的兩個數據點 p=（p1，p2，…，pd）以及 q=（q1，q2，…，qd），稱點p支配點q，當且僅當滿足對于任意的i（1，d）都有 pi≤ qi，并且至少存在一個 i，使得 pi＜qi。

定義 2（數據點［5］Skyline）對數據集 S 上的任意點p，稱p為S中的Skyline點，當且僅當在S中不存在支配點p的數據點。S中所有Skyline數據點的集合構成了關于S的Skyline數據集。

Skyline查詢的概念最早由Borzsonyi等提出。BNL算法通過比較每個數據點的價值來找到Skyline點，由于時間復雜度為O（n2），計算時間隨著數據點的增加而顯著增加。此外 NN［6］和 BBS［7］算法應用多維索引如R-樹結構來加快Skyline查詢處理。在SFS算法［8］中指定一個單調函數，如果數據點p'的單調函數結果不大于數據點p，則意味著p不受p'的支配。利用這一特性，數據點根據單調函數的返回值按遞減排序，在檢查數據點是否是Skyline點時，數據點只需要與它之前的數據點進行比較。因此，數據之間的比較點的數量在BNL算法［1］進行可以減少。此外，文獻［9］中提出的算法使用了一個額外的消除過濾器窗口，該窗口包含一組選定的數據點，以盡可能地消除非Skyline數據點。為了減少基于排序的方法所需的計算成本，Mamoulis等提出了動態索引技術［10］。當數據維度較高且數據量過大，分布式并行Skyline查詢成為研究重點。

2.2 M apReduce并行計算框架

MapReduce是一個分布式并行計算框架，已經廣泛運用于大數據計算中。MapReduce是一種編程模型，它可以開發可擴展的并行應用程序來處理大型集群機器上的大數據。理想情況下，MapReduce系統能在參與的機器之間實現高度的負載平衡，并盡量減少每個機器的空間使用、CPU和I/O時間，以及網絡傳輸。它的基本思想是分治法，主要有兩個部分組成:Map Task和Reduce Task，就是將大量的數據處理劃分成多個子任務，每一個數據分片交給一個Map Task處理，Reduce Task負責對Map的結果進行匯總整理和輸出。圖2描述了MapReduce的數據處理過程。

圖2 MapReduce的數據處理過程

3 改進的Skyline算法

3.1 原始的算法思想

原始的Skyline算法即將數據進行分區后，然后求出各個分區的Skyline結果，最后進行合并。由于原始數據集數量較多，將數據劃分后，每一個進入Map階段的Skyline查詢的數據量仍然較多，并且每個數據點間需要進行比較，這樣算法效率較低。然而通常情況下Skyline查詢的結果集遠小于原始數據集，為了提高算法的效率應盡量減少數據點間的重復比較。

3.2 改進的算法思路

本文對原始數據集進行預處理，優先選出支配能力較強的點，使用這些支配能力較強的數據點對數據集進行過濾，來減少數據點之間的重復比較。把這些數據點放入Map任務，設置一個自定義時間間隔，在一部分Map任務完成后將局部過濾值發送給Master節點，Master節點從這些局部過濾值中選擇最優值作為全局變量，并發送給其他沒有執行的Map任務，使用這些全局變量過濾Map任務，從而減少Reduce任務的輸入量，提高算法的效率。

一個數據點的支配能力是指其支配其他數據點的能力，本文使用文獻［12］中數據點支配能力的計算方法，d維的點qk的支配能力為。利用Map的輸出默認按鍵值排序的功能，選取10個支配能力最強的點，將這10個點組成的比較點集放入第一個Map任務，讓其能夠優先成為全局過濾值，使得算法的過濾效果更加明顯，減少那些在某個Map任務中成為Skyline結果的數據點被換下的可能性，降低了數據點之間的重復比較次數。

以二維空間為例，如圖3所示，可以運用文獻［13］的方法確定該點的支配能力，凡是位于該點的支配范圍內的點，均是被該點支配的點，即一定不是Skyline查詢結果，這里兩維上的全偏序關系默認為小于關系。

圖3 Skyline數據空間

圖4 說明優化的Skyline查詢算法。將原始數據放入4個Map任務，本文設定每個時間間隔內有2個Map任務完成，具體步驟如下:

步驟1將原始數據的比較點集放入第一個Map任務，在第一個時間間隔內，第一個和第二個Map任務完成后，產生各自的局部過濾值。第一個Map 任務的 Skyline 結果為（1，9），（2，7），（4，3），（6，2），（8，1），其局部過濾值為（4，3），第二個 Map任務的 Skyline結果為（5，3），（6，2），其局部過濾值為（6，2），將（4，3）和（6，2）作為局部過濾值發送給Master節點；

步驟 2 Master節從點（4，3）和（6，2）中選擇點（4，3）作為全局過濾值發送給第一個和第二個Map任務；

步驟3使用全局過濾值點（4，3）過濾第一個Map任務和第二個Map任務的Skyline結果集，得到的結果分別是點（1，9），（2，7），（4，3），（6，2），（8，1）和（6，2），并將過濾后的結果發送給 Reduce任務；

步驟4將下一個時間間隔內中還沒有開始的Map任務進行預處理，獲取從Master節點傳來的全局過濾值（4，3）來過濾Map任務的原始數據，使用全局過濾值（4，3）過濾第三個Map任務，全局過濾值可以支配點（5，9），（7，8），（10，3），（6，5），（5，6），則第三個Map任務的輸入經過過濾后減少5個，第三個 Map任務的 Skyline結果集為（2，7），（8，1），（4，3），并將其局部過濾值（4，3）發送給Master節點，保證全局過濾值更新。全局過濾值（4，3）可以過濾第四個Map任務的所有原始數據集，被過濾的數據點一定不可能成為Skyline查詢的最終結果，所以第四個Map任務的Skyline結果為空，不產生任何的輸出。將過濾后的Skyline查詢結果發生時給Reduce任務；

圖4 優化的Skyline查詢算法

步驟5以同樣的方式過濾第五個Map任務，經過過濾后的 Skyline 結果集為（2，8），（3，6），（9，1），（1，9），并將過濾結果發送給 Reduce任務；

步驟6等到所有的Map任務完成后，Reduce任務將過濾所有的Skyline結果集，產生最終的Skyline結果；

將一段時間間隔內完成的Map任務的局部過濾值發送給Master節點，能夠有效減少系統的等待時間。優化的Skyline查詢算法能夠降低Map任務的輸入量，同時減少數據之間的重復比較次數，有效地提高了算法的效率。

4 實驗分析

4.1 實驗環境

本文的實驗環境由5臺PC機組成，每個PC機的配置為 Inter（R）Corei5-6500 CPU@3.20GHZ，4GB內存，操作系統為ubuntu11.10，其中一臺PC機作為Master節點，其它4臺PC機作為Slave節點。本文采用的Hadoop平臺版本為0.20.2，在JDK1.6環境下編譯。

本文的數據集利用文獻［1］中的數據生成工具生成。實驗數據集量為2×105到10×105，數據維度從2維到6維變化，默認維度是4，節點數為4。本文測試Skyline查詢在獨立分布和反相關分布情況下的性能。

本文從維度，數據量和節點數三個角度對Skyline查詢時間進行分析比較，將本文的優化Skyline查詢算法（Optimized Skyline Query Algorithm，OS）與文獻［5］中的MR-BNL算法，MR-SFS算法進行比較。

4.2 實驗結果

1）圖5表示Skyline查詢時間隨數據量變化的情況，圖 5（a）和圖 5（b）分別表示獨立分布和反相關分布三種算法的運行時間與數據量的關系圖。隨著數據量的增大，每個Map任務需要處理的數據量也增大，當數據量從2×105條增加到10×105條時，可以看出算法的開銷增大。由于SFS算法是對BNL算法的改進，在數據量較小時，SFS算法的性能不能完全體現，當數據量較大時，SFS算法具有較高的時間性能。從圖中可以看出OS算法的運行時間遠低于MR-BNL算法和MR-SFS實驗法，原因是OS算法能夠在任務運行前過濾掉一大部分非Skyline數據，使得Map任務的輸入量減少，同時OS算法能在最初始的階段找出一些必定成為Skyline點的數據集，過濾效果更加明顯，從而減少數據的換入換出，降低數據點之間的重復比較次數，所以算法性能最佳。由于反相關數據在某一維上的取值越大那它在其他維度上取值越小，這樣使得互不支配的數據點更多，從而算法的運行時間比獨立分布的時間較長。

圖5 Skyline查詢算法基于數據量的運行時間

2）圖6表示Skyline查詢時間隨數據維度變化的情況，圖 6（a）和圖 6（b）分別表示獨立分布和反相關分布三種算法的運行時間與維度的關系圖。隨著維度的增加，數據點的支配關系需要比較更多的維度，這樣整個算法的時間開銷都增大。從圖中可以看出SFS算法的時間效率略高于BNL算法，而優化的OS算法隨著維度的變化依然擁有較高的時間效率，主要是由于過濾點集的選取較優。在低維度的時候，三種算法的運行時間都較短，然而隨著維度的增加，互不支配的數據也增多，數據間的比較增多，導致運行時間增加。當維度達到5維時，兩種分布情況下的查詢時間都急劇增加，出現“維度災難”。在反相關數據下，當維度高于5時，三種算法的運行時間急劇增加，其主要原因是反向關數據的特點和Skyline查詢支配的定義（一個數據支配另外一個數據指該數據的所有維度的取值都不比另外一個數據差，并且至少有一個維度是優于另外的一個數據）。在反相關數據中隨著維度的增加，算法的運行時間會呈指數增加。

圖6 Skyline查詢算法基于維度的運行時間

3）圖7表示Skyline查詢時間隨節點數變化的情況，圖 7（a）和圖 7（b）分別表示獨立分布和反相關分布三種算法的運行時間與節點數的關系。隨著節點數的增加，Skyline查詢時間都在減少。從圖中可以看出SFS算法的時間效率略高于BNL算法，而優化的OS算法在時間效率上依然高于SFS算法和BNL算法，主要是OS算法在節點數越多的時候過濾掉的數據點越多，并且并行處理更明顯，算法運行時間越少。當節點較少的時候，系統的并行性和處理效率較低，能夠設置的節點越多，系統的并行性和處理效率越強，算法的時間性能越優。

圖7 Skyline查詢算法基于節點數的運行時間

5 結語

由于傳統的Skyline算法在大數據情況下效率較低，本文設計的算法對原始數據集進行過濾，過濾掉一些不可能成為Skyline結果集的數據點，該方法能在最初始的階段找出一些必定成為Skyline點的數據集，使用這樣的數據點來過濾其他Map任務中的數據，過濾效果更加明顯。同時時刻更新全局變量，降低數據點之間的重復比較次數。大量實驗表明，算法具有良好的可用性和高效性。