基于Hadoop平臺下Skyline查詢算法優化研究

王志力 王彥麗 李廣慶

基于Hadoop平臺下Skyline查詢算法優化研究

王志力 王彥麗 李廣慶

本文利用云計算下Hadoop平臺搭建實驗環境，在每個存儲數據的節點上對數據建立R-樹索引，將操作分散到分布式索引集群的各個節點上，同時采用云計算下現有優秀的Hadoop平臺調度算法，提高Map/Reduce性能，通過設計和改進一種基于索引并行的近鄰NN（Nearest Neighbor，最近鄰）算法。通過實驗測試，體現算法的優越性和漸進性，從而減少I/O的讀取次數和CPU的計算成本，最終實現數據的查詢處理優化目的。

Skyline查詢算法在實際應用中確實表現出不錯的查準率和查全率，目前很多改進的Skyline查詢算法查詢效率都不是很高，所以面對海量數據時，查詢算法主要改進查詢時間效率，漸進性，負載平衡和數據容錯性處理等方面。目前主要從數據庫存儲方式方面設計Skyline查詢算法，大多是在數據節點上建立索引達到查詢優化的目的。

Skyline計算

Skyline計算應用于很多不同領域的數據集，比如集中式數據庫、時空數據庫、數據流、分布式數據庫和屬性數據分類數據中。Skyline算法主要偏向于個人偏好查詢，在數據庫中搜索不被支配的點。一個點所以支配另外一個點是因為第一個點至少肯定有一項要比另外一個點要好，該算法主要根據用戶的選擇和喜好找到適合的語義。Skyline計算在數據領域的定義：在一個數據集中D=｛s1，s2，s3，…sn｝，其中各數據點可表示為Si=｛p1，p2，…，pn｝，i=1，2，3，…n-1，n。對于任何一個pi∈D，pi∈（0，1），對于pi來說，數據的屬性值越小越好。查詢對象數據集合中所有不被其他點支配的點組成的集合謂Skyline查詢；其中每個點稱之為SP。本文中的Skyline查詢優化算法采用索引技術，減少Skyline計算中SP點和點之間的比較次數，然后盡可能的找到最合適的SP點。

最近鄰的Skyline查詢算法

基于索引的Skyline算法是指在輸出用戶自己要查詢的SP點前，首先建立分布式數據結構，通過利用用戶建立的索引，盡量減少Skyline計算過程中點和點比較的次數，優先找出最可能得SP點。一般的Skyline查詢算法比較次數的最好情形為O（kn），最壞復雜度為O（kn2）。最近鄰算法（NearestNeighbor，簡稱NN）是對數據對象構建R-樹索引，求出距離最近的點，對該點進行數據分區，構建矩形區，同時遞歸調用算法來計算，直到分區中不含有任何Skyline查詢結果為止。NN算法的是在數據集中找到的k個最近的鄰居，根據分類屬性統計，統計出的結構按照分類屬性來賦值。因此在類別決策時，只與極少量的相鄰樣本有關。NN算法主要靠極少的鄰居樣本進行分類，它更應用于類別比較多的數據。

Hadoop平臺上NN算法查詢優化研究

改進NN查詢算法

Skyline查詢改進后使用分枝界定法。首先采取R-樹遍歷，然后再訪問MBR分配到各層。從根結點N開始，對所有的結點離根節點N的距離進行計算，分片采用升序方式存儲在內存堆棧中，如果結點不被SP中的點支配，繼續遍歷其孩子結點，若孩子結點被SP支配，那么放棄這個結點，否則繼續存儲在內存堆棧中，如此循環下去直到找到葉子結點并且不被SP支配，那么這個點一定是Skyline點。把這個點存儲在表中。循環如此，直到堆棧為空。在每次查詢過程中需要執行多次Skyline查詢，多次遍歷R-樹。

改進后的算法采用一種相互Skyline查詢，在查詢過程中利用局部查詢得到Skyline集合來盡量減少SP點，提高搜索效率，減少I/O開銷。當數據量非常大的時候，可能出現錯誤不能保證查詢正常進行，運行故障監測和任務遷移，在查詢過程中找到發生的故障，將故障中的任務遷移到副本，盡量保證查詢的正常執行。圖1是M=2階R-樹，圖2是M=2階R-樹在二維空間上的表現形式。

圖1　M=2階 R-樹

圖2　R-樹二維空間上的表現形式

具體步驟如下。

（1）將根所包含的結點n1升序放入堆D1中，同時將根所包含的結點n2升序置入堆棧D2中。

（2）首先對最近距離節點n1操作：移出棧中的n1，將n1的2個孩子（n3，n4）插入堆棧D1中，然后在對n3節點進行擴展，由于n3的兩個孩子結點（1、2）結點不被S1支配，將（1、2）插入堆棧D1里，移出最小距離的1，2，因為1和2是葉子的結點并且同時不被S所能支配，于是1、2就被放入Skyline點的固定列表S中。這樣我們就得到了局部的skyline點。通過用S1中的點與后面堆D1中的結點比較要被擴展后的結點n4，如果n4被S中的已經插入的點支配，所以n4移除，當堆棧D1為null時，S1中的點確認為全局的Skyline點。

（3）同樣的道理，對于（2）中的可以操作：將（5、6）插入堆D2中，這樣我們就得到了局部的Skyline點。通過用S2中的點與后面堆D2中的結點比較要擴展的是結點，當堆D2為空時，S2中的點就是局部所有的Skyline點。

（4）我們將S1中的全局Skyline點（1，2）與S2中的局部Skyline點（5，6）進行比較交集，得出S=（1，2）。

（5）局部Skyline查詢找到點的時候不斷的更新這個查詢點，全局Skyline查詢則不需要。

當數據量非常大的時候，容易出現局部Skyline集合發生故障，比如堆過大，線路中斷等情況。在算法執行過程中協調者一直在監測整個查詢過程，局部Skyline計算過程中周期性地保存中間結果和計算狀態至可靠節點。

（1）協調者接收查詢請求后，將查詢請求運行；

（2）協調者把發送查詢后接收所有返回局部Skyline集合放入Sn中；

（3）如果有未返回的局部Skyline集合，協調者發送消息探測等待看是否發生故障，如果未發生故障，則合并所有局部Skyline數據集；把所有的局部合并成全局Skyline集合；

（4）協調者將全局Skyline集合返回給用戶，查詢成功，退出；

（5）否則記錄故障，找到故障寫入訪問記錄文件RecordFile；

（6）檢查RecordFile的status是否完成；若是完成則繼續查詢執行（2），否則取出SP（dn），通過比較數據副本的負載平衡，用state記錄副本節點的忙閑，堆D（n）中等待該副本節點的運行者，Time記錄副本節點最近一次更新的時間；

（7）查找空閑副本，重新發送請求，找到合適數據副本的節點繼續執行（3）。

算法分析

通過分支界定法，局部查詢算法，查詢次數算法執行訪問結點的數目（N）小于s*h（h為R-樹的高度），減少了SP點的訪問次數。算法所需的堆中結點的數目應小于（s-1）*N。不符合的SP點直接支配剪掉，不影響后續查詢。

算法實驗評估

本文實驗環境在百兆局域網中的5臺PC機中運行，配置為：處理器：IntelCorei3-3210M（2.5GHz/ L33M），內存容量：2GB，硬盤容量：80GB，操作系統為WindowsXP。準備多臺服務器，虛擬機VMware的安裝，下載安裝軟件并分別在5臺機器上安裝。由于5臺機器的D盤剩余空間都較大，統一在D盤安裝VMwareWorkstation軟件，分配空間10G。設置1臺Master機，4臺Slave機。安裝Linux系統中的Ubuntu的iso文件。Jdk采用Jdk1.6.0版本和Hadoop采用版本hadoop-0.20.2。

圖3　二維數據的查詢比較

圖4　三維數據的查詢比較

第一組實驗R-樹采用頁面尺寸設置為512B，768B，1024B，3072B，本實驗在二維和三維數據上進行測試。采用JAVA語言來進行編譯。圖3是二維數據的查詢比較，圖4是三維數據上的數據查詢比較。改進的NN算法在查詢成本上原有的NN算法開銷和時間比較低。

第二組實驗對比訪問次數，經過比對如下表1，改進的NN算法比NN算法索引維護少，并且高的訪問次數并不一定有高的查詢成本，因為查詢成本除了I/O成本還包括CPU計算成本。

表1　改進前后的比對

通過改進NN算法，我們通過三組實驗驗證了改進的NN算法的有效性，不僅可以減少I/O的訪問次數，而且減少內存占用，減少CPU運行時間。R-樹對數據集進行索引，利用全局和局部查詢算法來盡可能減少SP點，保證算法的漸進性。達到了預期的查詢效果。

10.3969/j.issn.1001-8972.2015.24.024