王志力 王彥麗 李廣慶

基于Hadoop平臺(tái)下Skyline查詢算法優(yōu)化研究

王志力 王彥麗 李廣慶

本文利用云計(jì)算下Hadoop平臺(tái)搭建實(shí)驗(yàn)環(huán)境，在每個(gè)存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)上對(duì)數(shù)據(jù)建立R-樹(shù)索引，將操作分散到分布式索引集群的各個(gè)節(jié)點(diǎn)上，同時(shí)采用云計(jì)算下現(xiàn)有優(yōu)秀的Hadoop平臺(tái)調(diào)度算法，提高M(jìn)ap/Reduce性能，通過(guò)設(shè)計(jì)和改進(jìn)一種基于索引并行的近鄰NN（Nearest Neighbor，最近鄰）算法。通過(guò)實(shí)驗(yàn)測(cè)試，體現(xiàn)算法的優(yōu)越性和漸進(jìn)性，從而減少I/O的讀取次數(shù)和CPU的計(jì)算成本，最終實(shí)現(xiàn)數(shù)據(jù)的查詢處理優(yōu)化目的。

Skyline查詢算法在實(shí)際應(yīng)用中確實(shí)表現(xiàn)出不錯(cuò)的查準(zhǔn)率和查全率，目前很多改進(jìn)的Skyline查詢算法查詢效率都不是很高，所以面對(duì)海量數(shù)據(jù)時(shí)，查詢算法主要改進(jìn)查詢時(shí)間效率，漸進(jìn)性，負(fù)載平衡和數(shù)據(jù)容錯(cuò)性處理等方面。目前主要從數(shù)據(jù)庫(kù)存儲(chǔ)方式方面設(shè)計(jì)Skyline查詢算法，大多是在數(shù)據(jù)節(jié)點(diǎn)上建立索引達(dá)到查詢優(yōu)化的目的。

Skyline計(jì)算

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

最近鄰的Skyline查詢算法

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

Hadoop平臺(tái)上NN算法查詢優(yōu)化研究

改進(jìn)NN查詢算法

Skyline查詢改進(jìn)后使用分枝界定法。首先采取R-樹(shù)遍歷，然后再訪問(wèn)MBR分配到各層。從根結(jié)點(diǎn)N開(kāi)始，對(duì)所有的結(jié)點(diǎn)離根節(jié)點(diǎn)N的距離進(jìn)行計(jì)算，分片采用升序方式存儲(chǔ)在內(nèi)存堆棧中，如果結(jié)點(diǎn)不被SP中的點(diǎn)支配，繼續(xù)遍歷其孩子結(jié)點(diǎn)，若孩子結(jié)點(diǎn)被SP支配，那么放棄這個(gè)結(jié)點(diǎn)，否則繼續(xù)存儲(chǔ)在內(nèi)存堆棧中，如此循環(huán)下去直到找到葉子結(jié)點(diǎn)并且不被SP支配，那么這個(gè)點(diǎn)一定是Skyline點(diǎn)。把這個(gè)點(diǎn)存儲(chǔ)在表中。循環(huán)如此，直到堆棧為空。在每次查詢過(guò)程中需要執(zhí)行多次Skyline查詢，多次遍歷R-樹(shù)。

改進(jìn)后的算法采用一種相互Skyline查詢，在查詢過(guò)程中利用局部查詢得到Skyline集合來(lái)盡量減少SP點(diǎn)，提高搜索效率，減少I/O開(kāi)銷。當(dāng)數(shù)據(jù)量非常大的時(shí)候，可能出現(xiàn)錯(cuò)誤不能保證查詢正常進(jìn)行，運(yùn)行故障監(jiān)測(cè)和任務(wù)遷移，在查詢過(guò)程中找到發(fā)生的故障，將故障中的任務(wù)遷移到副本，盡量保證查詢的正常執(zhí)行。圖1是M=2階R-樹(shù)，圖2是M=2階R-樹(shù)在二維空間上的表現(xiàn)形式。

圖1　M=2階 R-樹(shù)

圖2　R-樹(shù)二維空間上的表現(xiàn)形式

具體步驟如下。

（1）將根所包含的結(jié)點(diǎn)n1升序放入堆D1中，同時(shí)將根所包含的結(jié)點(diǎn)n2升序置入堆棧D2中。

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

（3）同樣的道理，對(duì)于（2）中的可以操作：將（5、6）插入堆D2中，這樣我們就得到了局部的Skyline點(diǎn)。通過(guò)用S2中的點(diǎn)與后面堆D2中的結(jié)點(diǎn)比較要擴(kuò)展的是結(jié)點(diǎn)，當(dāng)堆D2為空時(shí)，S2中的點(diǎn)就是局部所有的Skyline點(diǎn)。

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

（5）局部Skyline查詢找到點(diǎn)的時(shí)候不斷的更新這個(gè)查詢點(diǎn)，全局Skyline查詢則不需要。

當(dāng)數(shù)據(jù)量非常大的時(shí)候，容易出現(xiàn)局部Skyline集合發(fā)生故障，比如堆過(guò)大，線路中斷等情況。在算法執(zhí)行過(guò)程中協(xié)調(diào)者一直在監(jiān)測(cè)整個(gè)查詢過(guò)程，局部Skyline計(jì)算過(guò)程中周期性地保存中間結(jié)果和計(jì)算狀態(tài)至可靠節(jié)點(diǎn)。

（1）協(xié)調(diào)者接收查詢請(qǐng)求后，將查詢請(qǐng)求運(yùn)行；

（2）協(xié)調(diào)者把發(fā)送查詢后接收所有返回局部Skyline集合放入Sn中；

（3）如果有未返回的局部Skyline集合，協(xié)調(diào)者發(fā)送消息探測(cè)等待看是否發(fā)生故障，如果未發(fā)生故障，則合并所有局部Skyline數(shù)據(jù)集；把所有的局部合并成全局Skyline集合；

（4）協(xié)調(diào)者將全局Skyline集合返回給用戶，查詢成功，退出；

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

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

（7）查找空閑副本，重新發(fā)送請(qǐng)求，找到合適數(shù)據(jù)副本的節(jié)點(diǎn)繼續(xù)執(zhí)行（3）。

算法分析

通過(guò)分支界定法，局部查詢算法，查詢次數(shù)算法執(zhí)行訪問(wèn)結(jié)點(diǎn)的數(shù)目（N）小于s*h（h為R-樹(shù)的高度），減少了SP點(diǎn)的訪問(wèn)次數(shù)。算法所需的堆中結(jié)點(diǎn)的數(shù)目應(yīng)小于（s-1）*N。不符合的SP點(diǎn)直接支配剪掉，不影響后續(xù)查詢。

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

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

圖3　二維數(shù)據(jù)的查詢比較

圖4　三維數(shù)據(jù)的查詢比較

第一組實(shí)驗(yàn)R-樹(shù)采用頁(yè)面尺寸設(shè)置為512B，768B，1024B，3072B，本實(shí)驗(yàn)在二維和三維數(shù)據(jù)上進(jìn)行測(cè)試。采用JAVA語(yǔ)言來(lái)進(jìn)行編譯。圖3是二維數(shù)據(jù)的查詢比較，圖4是三維數(shù)據(jù)上的數(shù)據(jù)查詢比較。改進(jìn)的NN算法在查詢成本上原有的NN算法開(kāi)銷和時(shí)間比較低。

第二組實(shí)驗(yàn)對(duì)比訪問(wèn)次數(shù)，經(jīng)過(guò)比對(duì)如下表1，改進(jìn)的NN算法比NN算法索引維護(hù)少，并且高的訪問(wèn)次數(shù)并不一定有高的查詢成本，因?yàn)椴樵兂杀境薎/O成本還包括CPU計(jì)算成本。

表1　改進(jìn)前后的比對(duì)

通過(guò)改進(jìn)NN算法，我們通過(guò)三組實(shí)驗(yàn)驗(yàn)證了改進(jìn)的NN算法的有效性，不僅可以減少I/O的訪問(wèn)次數(shù)，而且減少內(nèi)存占用，減少CPU運(yùn)行時(shí)間。R-樹(shù)對(duì)數(shù)據(jù)集進(jìn)行索引，利用全局和局部查詢算法來(lái)盡可能減少SP點(diǎn)，保證算法的漸進(jìn)性。達(dá)到了預(yù)期的查詢效果。

10.3969/j.issn.1001-8972.2015.24.024