面向高維數(shù)據(jù)的Skyline查詢處理技術(shù)研究

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

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

1 引 言

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

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

表1 餐廳推薦實(shí)例Table 1 Restaurant recommendation example

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

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

Borzsonyi等人[4]提出了block-nested-loops(BNL)算法,該算法是Skyline查詢的基礎(chǔ)算法.它按順序處理所有點(diǎn),并跟蹤到目前為止在Skyline緩沖區(qū)中沒有被任何其他點(diǎn)支配的點(diǎn).Chomicki等人[5]提出了排序優(yōu)先Skyline(SFS)算法,該算法通過將點(diǎn)按曼哈頓范數(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)大并行計(jì)算能力的GPU來進(jìn)行并行化Skyline計(jì)算.大多數(shù)基于GPU的基于排序的Skyline算法[9]都是對(duì)其順序?qū)?yīng)的改編.這些算法將檢查所有點(diǎn)以增加Skyline緩沖區(qū),這阻礙了它們的效率.基于分區(qū)的并行Skyline算法使用遞歸分區(qū)過程或樹狀結(jié)構(gòu)[10-13],以減少點(diǎn)支配檢查,但它們對(duì)于GPU處理來說本質(zhì)上是困難的.

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

2 相關(guān)工作

2.1 問題定義

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

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

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

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

則稱點(diǎn)p被點(diǎn)q支配,即:

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

(1)

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

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

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

(2)

則稱S為P的Skyline集.

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

3 網(wǎng)格劃分

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

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

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

第i層中的單元集記為Li.單元格c=Li[cld-1,…,cl0]由其列號(hào)索引,即它分別位于維度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層中,點(diǎn)p所屬的網(wǎng)格c的計(jì)算公式如公式(3)所示:

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

(3)

例如點(diǎn)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)格支配)對(duì)同層的網(wǎng)格ci和cj,如果滿足:ci不為空,且ci的索引在每個(gè)維度上都小于cj的索引,即:

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

(4)

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

定義6.(網(wǎng)格部分支配)對(duì)同層的網(wǎng)格ci和cj,如果滿足:ci不為空,ci的索引至少在一個(gè)維度上等于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計(jì)算.為了避免出錯(cuò),候選網(wǎng)格單元必須覆蓋數(shù)據(jù)空間的每個(gè)維度.為了得出候選網(wǎng)格單元的數(shù)量,本文使用一組覆蓋每個(gè)維度的輔助候選單元.這些輔助候選網(wǎng)格單元的數(shù)量可以很容易地推導(dǎo)出來,將它們和候選網(wǎng)格單元建立一對(duì)一的映射關(guān)系.使用輔助關(guān)鍵網(wǎng)格單元可以簡化輔助候選單元格的描述.

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

輔助點(diǎn)雖然是Skyline點(diǎn),但它們不會(huì)影響P的Skyline點(diǎn).這是因?yàn)閿?shù)據(jù)點(diǎn)落在[0,1)d中.輔助點(diǎn)不會(huì)支配或被[0,1)d(包括原點(diǎn))中的任何點(diǎn)支配,這是因?yàn)樗鼈冊(cè)谀承┚S度的坐標(biāo)為1,在所有其他維度上坐標(biāo)為0.

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

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

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

(8)

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

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

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

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

(9)

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

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

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

(10)

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

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

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

(11)

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

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

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

(12)

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

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

證明:直觀地說,這是因?yàn)樯蠈拥暮蜻x網(wǎng)格單元都被下層的候選網(wǎng)格單元所覆蓋(參考圖1).

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

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

(13)

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

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

該推論表明第i層中的關(guān)鍵網(wǎng)格單元必須至少在第i+1層中產(chǎn)生一個(gè)關(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點(diǎn)集S

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

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

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

4.2 單元收縮方法

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

(14)

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

接下來介紹如何枚舉中的候選單元.一個(gè)層中的所有單元都可以通過它們的列索引列舉得出.通過仔細(xì)控制枚舉過程,可以按列指數(shù)枚舉一層中的所有候選網(wǎng)格單元.為了方便理解,枚舉過程如圖2所示.該圖顯示了3維空間的第2層網(wǎng)格,其中第2維(即維數(shù)d-1,是最重要的維數(shù))由4個(gè)網(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個(gè)輔助的關(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í),假設(shè)L1[0,0,3]被發(fā)現(xiàn)是第一個(gè)非空單元.根據(jù)定義,這一定是K2的一個(gè)關(guān)鍵單元,用ck0表示.現(xiàn)在cl0=3.將cl1加1(cl1=1)并重置cl0.檢查到cl0=2,因?yàn)樵赾l0=3處已經(jīng)找到了一個(gè)關(guān)鍵單元ck0,它將部分地支配L1[0,1,3].重復(fù)這個(gè)過程,本文列舉cl1=2的單元格(cl0也等于2).沒有發(fā)現(xiàn)非空的單元,就轉(zhuǎn)到cl1=3.假設(shè)發(fā)現(xiàn)了另一個(gè)非空單元,即一個(gè)關(guān)鍵單元ck1=L2[0,3,0].

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

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

接下來將介紹順序關(guān)鍵單元收縮方法,該方法遵循上述思路,通過sub_cell(Ci)中的網(wǎng)格單元來生成Ki+1中的關(guān)鍵網(wǎng)格單元.順序單元收縮算法如算法2所示,它列舉了維度d-1～1的所有列索引組合,但是單獨(dú)考慮了維度0的列索引(cl0).cl0的值范圍受到Ci中候選單元的起始索引和Ki+1中找到的關(guān)鍵單元的約束,這樣就可以對(duì)枚舉的內(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. 是一個(gè)輔助關(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中每個(gè)維度的枚舉從-2開始(算法2第2～第4行).這是因?yàn)檩o助關(guān)鍵單元在第i層的索引為-1,在第i+1層加倍為-2.不是說對(duì)于一個(gè)在維度j中具有列索引clj的單元格c∈Li,sub_cell(c)包含在維度j中具有列索引從2clj開始的單元.

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

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

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

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

本文從OpenStreetMap[14]中獲得32億個(gè)數(shù)據(jù)點(diǎn)(d=2),形成一個(gè)真實(shí)的數(shù)據(jù)集,,用“OSM”表示.本文通過隨機(jī)抽樣創(chuàng)建子集,用于不同數(shù)據(jù)集基數(shù)的實(shí)驗(yàn).本文通過使用前兩個(gè)維度的隨機(jī)采樣坐標(biāo)作為更高維度的坐標(biāo)來進(jìn)一步合成真實(shí)數(shù)據(jù)集.在之前的研究的基礎(chǔ)上,本文還使用常用的數(shù)據(jù)集生成器[2]生成合成數(shù)據(jù).生成的數(shù)據(jù)集包括Independent、Anti-correlated和Correlated這3部分,代表一個(gè)點(diǎn)在不同維度上的坐標(biāo)分別是獨(dú)立的、反相關(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查詢的圖表象限、全局和動(dòng)態(tài)Skyline.該算法通過給定一組點(diǎn),將平面劃分為一組區(qū)域,稱為Skyline多米諾骨牌.同一個(gè)Skyline polyomino中的所有查詢點(diǎn)都有相同的Skyline查詢結(jié)果.

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

圖4 整體運(yùn)行時(shí)間Fig.4 Overall running time

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

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

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

(15)

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

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

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

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

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

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

6 結(jié)束語

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

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

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

3)本文通過大量實(shí)驗(yàn),從多個(gè)角度證明了本文提出算法的有效性.