陳昆倫,李佳佺,李傳文,鄧慶緒

(東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,沈陽 110169)

1 引 言

在大數(shù)據(jù)環(huán)境下,如何從海量數(shù)據(jù)中高效篩選出人們感興趣的信息,是當(dāng)前數(shù)據(jù)庫領(lǐng)域關(guān)心的問題之一[1].Skyline查詢可以幫助人們在大量數(shù)據(jù)中找到可能“更感興趣”的點.Skyline查詢是一個典型的多目標(biāo)優(yōu)化問題,在推薦系統(tǒng)等多標(biāo)準(zhǔn)決策場景中有許多應(yīng)用.

Skyline查詢是根據(jù)點間的支配關(guān)系來進(jìn)行查詢的,“支配關(guān)系”具體描述為:假設(shè)空間中存在兩個點pi和pj,它們都有d個屬性.如果pi在至少一個屬性上優(yōu)于pj,并且在所有其他屬性上與pj一樣好,則稱點pi支配另一個點pj.“優(yōu)于”關(guān)系通常被量化為具有較小的屬性值.為了方便理解Skyline查詢,本文通過一個餐廳推薦的實例加以說明,該實例如表1所示.假設(shè)某用戶附近有4家餐廳,每家餐廳都具有人均消費、與用戶的距離和評分等級(1是最高等級)這3個屬性,餐廳推薦系統(tǒng)根據(jù)這3個屬性為用戶推薦餐廳,可以看出餐廳r2不論在人均消費、距離還是評分等級上都要優(yōu)于餐廳r1和餐廳r3,因此在Skyline查詢中稱餐廳r1和餐廳r3被餐廳r2所支配.餐廳r4雖然在人均消費和距離上都差于餐廳r2,但其評分登記高于r2,因此餐廳r4和餐廳r2間不存在支配關(guān)系,r2和r4稱為Skyline點,系統(tǒng)將其作為結(jié)果發(fā)送給用戶.可以看出Skyline查詢無法決定哪家餐館是最適合的,而是為用戶去掉各個方面都差于其它餐廳的餐廳,方便用戶可以做出最終決定.

表1 餐廳推薦實例Table 1 Restaurant recommendation example

隨著地理信息系統(tǒng)(Geographic Information System,GIS)、基于位置的服務(wù)(Location Based Service,LBS)技術(shù)和移動通信技術(shù)的高速發(fā)展,傳統(tǒng)的Skyline查詢算法出現(xiàn)了運行速度慢,執(zhí)行效率低下等問題,因此已經(jīng)無法滿足不斷增長的高維數(shù)據(jù)的需求[3].

順序Skyline查算法主要包括基于排序和基于分區(qū)的兩類算法.兩類算法都維護(hù)一個存儲Skyline點的Skyline緩沖區(qū).基于排序的算法重新排列數(shù)據(jù)集,使Skyline點更有可能在早期被處理并添加到緩沖區(qū)中.這有助于點消除效率的提高.基于分區(qū)的算法對緩沖區(qū)中的Skyline點進(jìn)行結(jié)構(gòu)化,以便剩余的每個點只需要與Skyline點的子集進(jìn)行比較.

Borzsonyi等人[4]提出了block-nested-loops(BNL)算法,該算法是Skyline查詢的基礎(chǔ)算法.它按順序處理所有點,并跟蹤到目前為止在Skyline緩沖區(qū)中沒有被任何其他點支配的點.Chomicki等人[5]提出了排序優(yōu)先Skyline(SFS)算法,該算法通過將點按曼哈頓范數(shù)進(jìn)行排序來優(yōu)化BNL.Sharifzadeh等人[6]提出了基于Voronoi的空間Skyline(VSS)算法,該算法在數(shù)據(jù)空間上構(gòu)建Voronoi圖來進(jìn)行空間Skyline查詢(SSQ).

現(xiàn)有的的研究[7,8]已經(jīng)開始使用具有強(qiáng)大并行計算能力的GPU來進(jìn)行并行化Skyline計算.大多數(shù)基于GPU的基于排序的Skyline算法[9]都是對其順序?qū)?yīng)的改編.這些算法將檢查所有點以增加Skyline緩沖區(qū),這阻礙了它們的效率.基于分區(qū)的并行Skyline算法使用遞歸分區(qū)過程或樹狀結(jié)構(gòu)[10-13],以減少點支配檢查,但它們對于GPU處理來說本質(zhì)上是困難的.

針對現(xiàn)有方法的不足,本文提提出了基于網(wǎng)格劃Skyline算法(SkyCell)[8],與之前的Skyline查詢算法不同,SkyCell算法不是通過點與點間的支配關(guān)系,而是考慮網(wǎng)格間的支配關(guān)系,通過不斷的對網(wǎng)格進(jìn)行細(xì)化來得到Skyline集[9].

2 相關(guān)工作

2.1 問題定義

首先對Skyline查詢設(shè)計到的相關(guān)定義進(jìn)行介紹.

定義1.(點支配)任意兩點p,q∈P,當(dāng)且僅當(dāng)滿足:

1)對于任意維度k≥d,滿足p[k]≤q[k]

2)至少存在一個維度r≤d,滿足p[r]

則稱點p被點q支配,即:

p∧(?r∈[0,d),p[r]

(1)

定義2.(Skyline點)若點p∈P不被P中的其它任何點支配,則稱點p為P的一個Skyline點.

定義3.(Skyline集)令S為所有不被其它點所支配的點的集合,即:

S={p∈P|/?q∈P:q

(2)

則稱S為P的Skyline集.

定義4.(Skyline查詢)給定d維(d>1)歐幾里得空間中n個點的集合P={p1,p2,…,pn},Skyline查詢的目標(biāo)是計算P中的Skyline集S?P.

3 網(wǎng)格劃分

3.1 多層網(wǎng)格劃分

本文將空間視為d維單元超立方體,使用多層網(wǎng)格對其進(jìn)行劃分.頂層網(wǎng)格層(第0層)具有最粗粒度(即整個數(shù)據(jù)空間是一個單元格),而底層(第ρ層)具有最細(xì)粒度.每一層都是一個規(guī)則的網(wǎng)格,在第i層有2i-d個單元.為了方便理解,給出多層數(shù)據(jù)空間劃分的示例,如圖1所示,其中d=2,對于第0層～第4層,有20×2=1～24×2=256個單元.每一層具有相同的單元大小.圖1中將第4層放大以獲得更好的可見性.

圖1 多層數(shù)據(jù)空間劃分示例圖Fig1 Example diagram of multi-layered data space division

第i層中的單元集記為Li.單元格c=Li[cld-1,…,cl0]由其列號索引,即它分別位于維度d-1,…,0,中的cld-1,…,cl0列.使用c[k]來表示c在維度k中的索引:c[k]=clk.在圖1中,第4層中的單元格c=L4[10,1]在,維度1(垂直維度)的第10列和維度0(水平維度)的第1列,即c[1]=10和c[0]=1.

在第i層中,點p所屬的網(wǎng)格c的計算公式如公式(3)所示:

cld-1,…,cl0c=Li[?p[d-1]·2i」,…,?p[0]·2i」]

(3)

例如點p=(0.63,0.08)在第3層屬于網(wǎng)格L3[|0.63×23|,|0.08×23|]=L3[5,0],在第4層屬于網(wǎng)格L4[?0.63×22」,?0.08×24」]=L4[10,1].

3.2 網(wǎng)格支配

定義5.(網(wǎng)格支配)對同層的網(wǎng)格ci和cj,如果滿足:ci不為空,且ci的索引在每個維度上都小于cj的索引,即:

c≠?∧?k∈[0,d),ci[k]

(4)

則稱單元格ci支配單元格cj,記為cicj.

定義6.(網(wǎng)格部分支配)對同層的網(wǎng)格ci和cj,如果滿足:ci不為空,ci的索引至少在一個維度上等于cj的索引,并且ci的索引在所有其他維度上都小于cj的索引,即:

c≠?∧?k∈[0,d),ci[k]≤cj[k]∧?k∈[0,d),
ci[k]=cj[k]

(5)

則稱單元格ci部分支配單元格cj,記為ci?cj.

(6)

3.3 候選網(wǎng)格單元

定義7.(關(guān)鍵網(wǎng)格單元)既不被任何其他單元格支配也不部分被任何其他單元格支配的非空單元格稱為關(guān)鍵網(wǎng)格單元.

將第i層中所有關(guān)鍵單元的集合表示為Ki.圖1中被“*”標(biāo)記出來的網(wǎng)格單元就是關(guān)鍵網(wǎng)格單元.

定義8.(候選網(wǎng)格單元)候選網(wǎng)格單元由關(guān)鍵單元格和它們的部分支配網(wǎng)格單元組成,公式表示如公式(7)所示:

(7)

其中,Ci表示第i層的候選網(wǎng)格單元集,Ki表示第層的關(guān)鍵網(wǎng)格單元集,Γ(c)表示被關(guān)鍵網(wǎng)格部分支配的單元集.

選網(wǎng)格單元離散化數(shù)據(jù)集P的凸包以進(jìn)行Skyline計算.為了避免出錯,候選網(wǎng)格單元必須覆蓋數(shù)據(jù)空間的每個維度.為了得出候選網(wǎng)格單元的數(shù)量,本文使用一組覆蓋每個維度的輔助候選單元.這些輔助候選網(wǎng)格單元的數(shù)量可以很容易地推導(dǎo)出來,將它們和候選網(wǎng)格單元建立一對一的映射關(guān)系.使用輔助關(guān)鍵網(wǎng)格單元可以簡化輔助候選單元格的描述.

為了定義輔助關(guān)鍵網(wǎng)格單元,首先將d個輔助點添加到d維數(shù)據(jù)集P中.第i個輔助點λi,對于所有0≤j

輔助點雖然是Skyline點,但它們不會影響P的Skyline點.這是因為數(shù)據(jù)點落在[0,1)d中.輔助點不會支配或被[0,1)d(包括原點)中的任何點支配,這是因為它們在某些維度的坐標(biāo)為1,在所有其他維度上坐標(biāo)為0.

這d個輔助點在每個網(wǎng)格層外創(chuàng)造了d個額外的關(guān)鍵單元.這樣的單元就是輔助關(guān)鍵單元,例如圖1中每層外的淺灰色單元(第4層的∧0和∧1).

定義9.(輔助候選網(wǎng)格單元)第i層的輔助候選單元集合,用CcAi表示,由被輔助關(guān)鍵單元部分支配的網(wǎng)格單元組成.在d維空間第層表格中,輔助候選單元網(wǎng)格的數(shù)量由公式(8)計算得出:

CcAi={c∈Li|c[j]=2i-1,j∈[0,d)}

(8)

3.4 限制候選單元格數(shù)量

由于本文的算法是從候選網(wǎng)格單元計算出Skyline點的,候選網(wǎng)格單元的數(shù)量決定了計算成本,因此要對其數(shù)量進(jìn)行限制.

定理1.在第i層中,候選單元集Ci和輔助候選單元集CcA之間存在雙射關(guān)系.

推論1.在維d空間中,第i層中候選單元的數(shù)量,用|Ci|表示,計算公式如公式(9)所示:

(9)

證明:根據(jù)定理1,候選單元格的數(shù)量與輔助候選單元格的數(shù)量相同.并結(jié)合公式(8),推導(dǎo)出每個j∈[0,d]的CcAi中的網(wǎng)格單元數(shù),從而推導(dǎo)出|CcAi|和|Ci|.

1)對于j=0,有c[0]=2i-1.此情況下網(wǎng)格單元的數(shù)量由公式(10)計算得出:

(2i-1)·2i(d-2)=(2i-1)1·2i(d-2)

(10)

這些網(wǎng)格單元構(gòu)成了[2i]d網(wǎng)格的一個片段,例如,二維網(wǎng)格中的一列(例如圖1中第4層最右邊的一列).

2)對于j=1,根據(jù)c[1]=2i-1和c[0]≠2i-1,以避免兩次計算相同的單元.這類網(wǎng)格單元的數(shù)量由公式(11)計算得出:

(2i-1)·2i(d-2)=(2i-1)1·2i(d-1-1)

(11)

在維度0中,這些網(wǎng)格單元2i-1有個可能的列索引由于c[0]≠2i-1而少了一列);在維度1中,只有一個可能的列索引(c[1]=2i-1);在其他d-2維度中,每個維度都由有2i個可能的列索引(參見圖1中沒有第 4 層右上單元格的第1行).

3)一般來說,對于j=k,有c[k]=2i-1∧c[0]≠2i-1∧c[1]≠2i-1∧…∧c[k-1]≠2i-1.這類網(wǎng)格單元的數(shù)量由公式(12)計算得出:

(2i-1)k·2i(d-1-k)

(12)

將j∈[0,d-1]的數(shù)目相加就得出公式(9).

推論2.給定i>j,Ci中的網(wǎng)格單元覆蓋的體積(或d=2時的面積)必須小于Cj中的網(wǎng)格單元覆蓋的體積.

證明:直觀地說,這是因為上層的候選網(wǎng)格單元都被下層的候選網(wǎng)格單元所覆蓋(參考圖1).

推論3.給定第i層中的一個關(guān)鍵單元ck讓sub_cell(ck)是第i+1層中對ck進(jìn)行劃分后得到的單元集.在sub_cell(ck)中至少存在一個關(guān)鍵單元,即:

?ck′∈subcell(ck)∧ck′∈Ki+1

(13)

證明:第i層中的每個單元,包括一個關(guān)鍵單元ck,在第i+1層中被劃分為2d個單元,例如,圖1中第0層中的一個單元在第1層中被劃分為22=4個單元.因此,sub_cell(ck)≠?.

回顧一下,一個關(guān)鍵單元ck是非空的(即包含數(shù)據(jù)點),sub_cell(ck)中一定有非空的單元.在這些單元中,必須有一個單元ck′不被sub_cell(ck)中的其他單元所支配(這些單元不能都相互支配).

該推論表明第i層中的關(guān)鍵網(wǎng)格單元必須至少在第i+1層中產(chǎn)生一個關(guān)鍵網(wǎng)格單元.

圖1中,第1層的關(guān)鍵單元L1[0,0](用“*”標(biāo)記),產(chǎn)生第2層的關(guān)鍵單元L2[0,1],后者產(chǎn)生第3層的關(guān)鍵單元L3[0,3].

以上就是本文提出的網(wǎng)格劃分和候選網(wǎng)格單元的定義,接下將詳細(xì)介紹基于此候選網(wǎng)格單元的Skyline算法.

4 基于關(guān)鍵單元收縮的Skyline算法

4.1 SkyCell算法

基于上文介紹的網(wǎng)格劃分和候選網(wǎng)格單元,本文提出了SkyCell算法,如算法1所示.

算法1.SkyCell算法

輸入:數(shù)據(jù)集P

輸出:Skyline點集S

1.在數(shù)據(jù)集P計算出Lρ～L0

2.R0←L0[0,…,0]

3.for i=0 to ρ-1 do

4. Ri+1=ShrinkKeyCells(P,i,Ri,Li+1)

5.return RefineSkyline(P,Rρ)

SkyCell算法首先在數(shù)據(jù)集P上計算ρ層的一個網(wǎng)格分區(qū).將這些點存儲在一個數(shù)組中,并根據(jù)它們所屬的ρ層單元進(jìn)行排序,可以使用任何單元排序方法,如Z-排序,只要讓同一網(wǎng)格單元中的點存儲在數(shù)組中的一個連續(xù)段即可.然后,對于每個ρ層單元,記錄該單元中的點的開始和結(jié)束數(shù)組索引.一個空單元具有相同的起始和結(jié)束數(shù)組索引.這樣就構(gòu)建了網(wǎng)格結(jié)構(gòu)Lρ.從Lρ中構(gòu)建出Lρ-1.對于每個網(wǎng)格單元c∈Lρ-1,記錄下它是否包含數(shù)據(jù)點,這將用于以后的關(guān)鍵單元測試.重復(fù)上述過程,構(gòu)建出從Lρ-2～L0的其他層的網(wǎng)格結(jié)構(gòu)(第1行).

然后根據(jù)推論3,用一個名為單元收縮算法(ShrinkKeyCells)的子程序(第2～4行,將在后面進(jìn)行詳細(xì)介紹).在順序單元收縮算法中,Ri包含關(guān)鍵網(wǎng)格單元(Ri=Ki);在此特別說明,L0只有一個網(wǎng)格單元、(即整個數(shù)據(jù)空間),記做K0和C0.

當(dāng)Rρ被計算出來,Kρ也被計算出來.使用Kρ來計算Cρ.單元收縮算法從關(guān)鍵單元中計算出候選單元.然后,從Cρ中的每個候選單元中計算出Skyline點,并將它們作為結(jié)果返回.由于來自不同候選單元的點不會相互支配,候選單元可以被并行處理,本文使用排序優(yōu)先的Skyline(SFS)[5]算法來計算每個單元中的Skyline點.這些步驟寫于子程序RefineSkyline中(第5行).

4.2 單元收縮方法

推論4.給定一個關(guān)鍵單元cki+1∈Ki+1,存在一個候選單元ci∈Ci,使得cki+1∈sub_cell(ci),即:

(14)

從圖1中可以看出,每層的關(guān)鍵單元(用“*”標(biāo)記)都對應(yīng)于前一層的候選單元.

接下來介紹如何枚舉中的候選單元.一個層中的所有單元都可以通過它們的列索引列舉得出.通過仔細(xì)控制枚舉過程,可以按列指數(shù)枚舉一層中的所有候選網(wǎng)格單元.為了方便理解,枚舉過程如圖2所示.該圖顯示了3維空間的第2層網(wǎng)格,其中第2維(即維數(shù)d-1,是最重要的維數(shù))由4個網(wǎng)格代表(可以認(rèn)為它們是從cl2=0～cl2=3到的堆疊).虛線單元是從第1層的候選單元中劃分出來的(即除了L1[0,0,0]之外,L1中的所有單元都是候選單元),假設(shè)第1層中只有L1[-1,-1,1]、L1[-1,1,11]和L1[1,-1,-1]3個輔助的關(guān)鍵單元,沒有其他關(guān)鍵單元.

圖2 枚舉候選網(wǎng)格單元示例圖Fig.2 Example diagram of candidate cell enumeration

圖2中的虛線單元構(gòu)成sub_cell(K1).通過列舉它們來找到第2層的關(guān)鍵單元K2,這是通過排序從維度d-1～0的列索引來完成的,即從[0,0,0]到[3,3,3]列舉[cl2,cl1,cl0].首先,考慮cl2=0.在cl1=0時,假設(shè)L1[0,0,3]被發(fā)現(xiàn)是第一個非空單元.根據(jù)定義,這一定是K2的一個關(guān)鍵單元,用ck0表示.現(xiàn)在cl0=3.將cl1加1(cl1=1)并重置cl0.檢查到cl0=2,因為在cl0=3處已經(jīng)找到了一個關(guān)鍵單元ck0,它將部分地支配L1[0,1,3].重復(fù)這個過程,本文列舉cl1=2的單元格(cl0也等于2).沒有發(fā)現(xiàn)非空的單元,就轉(zhuǎn)到cl1=3.假設(shè)發(fā)現(xiàn)了另一個非空單元,即一個關(guān)鍵單元ck1=L2[0,3,0].

現(xiàn)在轉(zhuǎn)到cl2=1.再次列舉[cl1,cl0].注意,cl0只需要達(dá)到2,因為存在關(guān)鍵單元ck0=L2[0,0,0].這就找到第3個關(guān)鍵單元ck2=L2[1,1,2].重復(fù)這個過程,在cl2=2時沒有關(guān)鍵單元.在cl2=3時,有第4個關(guān)鍵單元ck3=L2[2,1,0].枚舉結(jié)束了,因為ck3限制了cl0小于0.

上面的枚舉收集了所有不被其他單元支配的非空單元,即K2中的關(guān)鍵單元.并且還修剪了部分sub_cell(K1)的枚舉(圖2中只有灰色單元被枚舉),從而降低了計算成本.

接下來將介紹順序關(guān)鍵單元收縮方法,該方法遵循上述思路,通過sub_cell(Ci)中的網(wǎng)格單元來生成Ki+1中的關(guān)鍵網(wǎng)格單元.順序單元收縮算法如算法2所示,它列舉了維度d-1～1的所有列索引組合,但是單獨考慮了維度0的列索引(cl0).cl0的值范圍受到Ci中候選單元的起始索引和Ki+1中找到的關(guān)鍵單元的約束,這樣就可以對枚舉的內(nèi)容進(jìn)行縮減.

算法2.順序關(guān)鍵單元收縮算法

輸入:當(dāng)前層數(shù)i,關(guān)鍵網(wǎng)格單元Ki,網(wǎng)格單元Li+1

輸出:關(guān)鍵網(wǎng)格單元Ki+1

1. Ki+1=?,j=0

2. for cld-1=-2 to 2i-1 do

3. … /*J表示[cld-1,…,cl1]*/

4. for cl1=-2 to 2i-1 do

6.then

8. Gs[J]←MingS(J),Ge[J]←MinGE(J)

9. if ck=Li+1[J,-1] or c[J,2i-1]

10. 是一個輔助關(guān)鍵單元 then

11. Ki+1←ck,continue

12. If J不包含負(fù)索引 then

13. for cl0=Gs[J] to cl0=Ge[J] do

14. If Li+1[J,cl0]不為空 then

15. Ge[J]←cl0-1

16. If

17. NotPartallyDomed(Li+1[J,cl0])

18. then

19. Ki+1←Li+1[J,cl0]

20. return Ki+1

使用J表示維度d-1～1的列索引組合,即Li+1[J,cl0]是被枚舉單元的索引.J中每個維度的枚舉從-2開始(算法2第2～第4行).這是因為輔助關(guān)鍵單元在第i層的索引為-1,在第i+1層加倍為-2.不是說對于一個在維度j中具有列索引clj的單元格c∈Li,sub_cell(c)包含在維度j中具有列索引從2clj開始的單元.

對于每個J,計算Gs[J]和Ge[J],以約束要枚舉的cl0的值(算法2第5～第7行).如果J能形成一個輔助關(guān)鍵單元,則將其加入Ki+1,并進(jìn)入下一個J組合(算法2第9行).如果不是,并且J不包含負(fù)指數(shù),列舉cl0來檢查Li+1[J,cl0]是否為非空(算法2第10～第12行).一旦找到一個非空單元c,Ge[J]就被更新為當(dāng)前的cl0-1(算法2第13行).檢查c是否被Ki+1中的一個輔助關(guān)鍵單元所部分支配(通過NotPartiallyDomed子程序).如果不是,那么c就是一個關(guān)鍵單元,本文將其加入Ki+1(算法2第15行).然后進(jìn)入下一個J組合(算法2第16行).

接著進(jìn)一步調(diào)整Gs[J]和Ge[J],因為這些由之前的Gs[J]和Ge[J]所生成的組合產(chǎn)生的關(guān)鍵單元可能會支配或部分支配J產(chǎn)生的單元,這些被支配的單元可以被修剪.檢查d-1個以前的索引組合,其中每個組合在一個維度上與J不同.第k個(0

5 實 驗

5.1 實驗設(shè)置

本文采用C++和CUDA 10.0實現(xiàn)所提的算法.實驗使用具有32 GB內(nèi)存的64位計算機(jī)、2.1 GHz Intel Xeon Silver 4110 CPU(8核)和具有4,608核和24GB 內(nèi)存的Nvidia Quadro RTX6000 GPU.

本文從OpenStreetMap[14]中獲得32億個數(shù)據(jù)點(d=2),形成一個真實的數(shù)據(jù)集,,用“OSM”表示.本文通過隨機(jī)抽樣創(chuàng)建子集,用于不同數(shù)據(jù)集基數(shù)的實驗.本文通過使用前兩個維度的隨機(jī)采樣坐標(biāo)作為更高維度的坐標(biāo)來進(jìn)一步合成真實數(shù)據(jù)集.在之前的研究的基礎(chǔ)上,本文還使用常用的數(shù)據(jù)集生成器[2]生成合成數(shù)據(jù).生成的數(shù)據(jù)集包括Independent、Anti-correlated和Correlated這3部分,代表一個點在不同維度上的坐標(biāo)分別是獨立的、反相關(guān)的和相關(guān)的.本章使用數(shù)據(jù)維度d∈[1,10],使用數(shù)據(jù)維度n∈{1,2,…,10}×106.

將本文提出的算法SkyCell與3種最先進(jìn)的算法Skyline Diagram[15]、Hybrid[16]和SkyAlign[1]進(jìn)行比較.

Skyline Diagram[15]是一種基于分區(qū)的順序Skyline查詢算法,該算法包含3種Skyline查詢的圖表象限、全局和動態(tài)Skyline.該算法通過給定一組點,將平面劃分為一組區(qū)域,稱為Skyline多米諾骨牌.同一個Skyline polyomino中的所有查詢點都有相同的Skyline查詢結(jié)果.

Hybrid[16]是一種基于多核CPU的Skyline查詢算法,該算法以塊為單位處理點.它在所有線程之間維護(hù)一個共享的全局Skyline,用于在保持高吞吐量的同時最大限度地減少優(yōu)勢測試.該算法基于點的分區(qū),在共享的全局Skyline上使用了高效可更新的數(shù)據(jù)結(jié)構(gòu).

SkyAlign[1]是一種基于GPU的Skyline查詢算法,該算法采用了全局靜態(tài)分區(qū)方案,通過分區(qū),我們可以允許受控分支利用傳遞關(guān)系并避免大多數(shù)點對點比較,優(yōu)先考慮工作效率和可觀的吞吐量,而不是最大吞吐量,以實現(xiàn)數(shù)量級更快的性能.

5.2 實驗結(jié)果分析

5.2.1 分區(qū)率ρ的影響

首先對分區(qū)率ρ的影響進(jìn)行分析,以指導(dǎo)后續(xù)實驗選擇其值.

圖3展示了多層網(wǎng)格中的第ρ層包含的候選網(wǎng)格的比率,其中ρ∈[1,12],d∈[2,10].請注意,該比率僅取決于層數(shù)和維度,數(shù)據(jù)集基數(shù)和分布無關(guān).可以看出,候選單元格覆蓋的空間比例隨著ρ的增加呈指數(shù)下降.當(dāng)d=2時,候選網(wǎng)格在ρ=7時覆蓋不到1%的空間,并且這個比率在ρ=12時進(jìn)一步下降到0.01%.當(dāng)d=10時,仍然只需要ρ=10以便候選網(wǎng)格僅占數(shù)據(jù)空間的1%.這些結(jié)果驗證了本文提出的SkyCell算法可以快速修剪大部分?jǐn)?shù)據(jù)空間(以及因此的數(shù)據(jù)點),而不考慮僅考慮幾層的網(wǎng)格.

圖3 ρ與候選網(wǎng)格集的比率Fig.3 Ratio of candidate cells vs.ρ

圖4展示了關(guān)鍵單元收縮時間和細(xì)化Skyline點計算時間和算法整體運行時間,其中,數(shù)據(jù)從100萬(1B)～800萬(8B),層數(shù)ρ從2～8.隨著ρ的增加,關(guān)鍵單元收縮的時間增加,而Skyline點計算的時間減少,這都是符合預(yù)期的.它們的綜合效果是ρ=6時的最佳總體運行時間.

圖4 整體運行時間Fig.4 Overall running time

此外,隨著n的增加,具有更大分層率(即更大的ρ)的網(wǎng)格有助于修剪更多點.因此,隨著ρ的增加,數(shù)據(jù)量為8B的曲線比數(shù)據(jù)量為1B的曲線下降得更快.其他參數(shù)上的算法性能顯示出類似的模式.因此,本章實驗使用ρ=6作為默認(rèn)值.

將順序SkyCell算法與使用了Skyline Diagram技術(shù)的Scan算法和Sweep算法進(jìn)行比較.根據(jù)Skyline圖,動態(tài)設(shè)置Skyline查詢,其中一個隨機(jī)坐標(biāo)的查詢點被用作數(shù)據(jù)空間的新原點.只有右上角象限的數(shù)據(jù)點被考慮用于Skyline計算.

在每個數(shù)據(jù)集上生成nq=10,000個查詢并報告平均算法響應(yīng)時間.對于Scan算法和Sweep算法,由于它們需要預(yù)計算,將預(yù)計算時間攤銷到算法響應(yīng)時間t中,計算公式如公式(15)所示:

(15)

其中,tp是預(yù)計算時間,tq是查詢時間.

1)數(shù)據(jù)集基數(shù)n對順序SkyCell算法的影響.實驗結(jié)果如圖5所示,n從1×106變化到10×106.可以看到SkyCell算法始終優(yōu)于Scan算法和Sweep算法,且優(yōu)勢分別高達(dá)4倍和8倍.公平地說,這是因為Scan算法和Sweep算法的預(yù)計算時間已攤銷到運行時間中.本文認(rèn)為,需要大量預(yù)計算的Skyline算法在其適用性方面受到影響,因為真實數(shù)據(jù)集通常是動態(tài)的,其中更新(例如,數(shù)據(jù)插入和刪除)可能會使預(yù)計算結(jié)果無效,本文提出的SkyCell算法沒有這樣的限制.它適用于靜態(tài)和動態(tài)場景,效率很高,例如,在不到1秒的時間內(nèi)從1000萬個真實數(shù)據(jù)點計算Skyline點,如圖5所示.

圖5 數(shù)據(jù)基數(shù)n對順序SkyCell性能的影響Fig.5 Performance of sequential SkyCell vs.n

2)數(shù)據(jù)維度的影響d對.順序SkyCell性能的影響.實驗結(jié)果如圖6所示,設(shè)置d=8(d=10時算法運行時間過長).

圖6 數(shù)據(jù)維度d對順序SkyCell性能的影響Fig.6 Performance of sequential SkyCell vs.d

SkyCell算法再次優(yōu)于其他對比實驗,且優(yōu)勢隨著增長.這是因為,當(dāng)d增加時,雖然關(guān)鍵網(wǎng)格收縮需要更多時間,但細(xì)化階段可能需要更少的時間(因為候選單元格占用的空間更小).相比之下,Scan算法和Sweep算法需要隨著d的增加以指數(shù)方式處理更多的網(wǎng)格,這就使得運行時間快速增加.此外,Scan算法和Sweep算法需要存儲大量的預(yù)計算數(shù)據(jù).對于d>5時,它們的預(yù)計算無法在本文實驗所使用的硬件上在4小時內(nèi)完成,因此在這些情況下沒有報告它們的結(jié)果.

6 結(jié)束語

本文從網(wǎng)格的角度對Skyline查詢進(jìn)行求解,考慮網(wǎng)格間的支配關(guān)系,提出了基于網(wǎng)格收縮的算法SkyCell.本文的主要貢獻(xiàn)如下:

1)本文提出了一種基于網(wǎng)格劃分和候選網(wǎng)格的Skyline查詢方法.通過使用網(wǎng)格支配檢查,本文的方法顯著減少了支配檢查的數(shù)量,從而對數(shù)據(jù)集大小產(chǎn)生了更好的可擴(kuò)展性.

2)本文提出了SkyCell算法,該算法需要檢查少量恒定數(shù)量的網(wǎng)格,就可以產(chǎn)生高效的Skyline計算.

3)本文通過大量實驗,從多個角度證明了本文提出算法的有效性.