一種網(wǎng)格化高并發(fā)Skyline查詢處理方法

李佳佺,劉晏如,李傳文

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,沈陽(yáng) 110169) E-mail：lichuanwen@mail.neu.edu.cn

1 引 言

自2001年由Borzsony等人提出后,Skyline查詢處理一直是數(shù)據(jù)庫(kù)領(lǐng)域的一個(gè)研究熱點(diǎn).Skyline點(diǎn)是指不被任何其他點(diǎn)“支配”的點(diǎn).點(diǎn)pa支配點(diǎn)pb是指pa在所有維度上不比pb差,且在至少一個(gè)維度上優(yōu)于pb.理論上,每一個(gè)點(diǎn)都需要跟其他所有的點(diǎn)進(jìn)行比較才能確定是否為Skyline點(diǎn).即使現(xiàn)有的各種方法從各個(gè)角度進(jìn)行了優(yōu)化,Skyline查詢的代價(jià)仍然很高,尤其是在數(shù)據(jù)量大、維數(shù)多的情況下.Skyline查詢?cè)谠S多領(lǐng)域有著廣泛的應(yīng)用,如：多目標(biāo)優(yōu)化問(wèn)題,數(shù)據(jù)挖掘和可視化,以及用戶偏好查詢等.例如,在二手車交易市場(chǎng)里人們對(duì)里程數(shù)低同時(shí)價(jià)位低的車感興趣,但一般來(lái)說(shuō)里程數(shù)低的車價(jià)位要高,反之亦然.這時(shí),采用Skyline查詢就可以避免人們買到里程數(shù)和價(jià)位同時(shí)都不具競(jìng)爭(zhēng)力的車.

如圖1所示,對(duì)價(jià)格和里程數(shù)兩個(gè)屬性進(jìn)行Skyline查詢會(huì)返回C1、C2和C4車輛,而C3雖然在里程數(shù)上與C1相同,但是在價(jià)格屬性上要高于C1,所以C3被C1支配,不是Skyline.這個(gè)例子中,不是Skyline的點(diǎn)都不需要被考慮.用戶只需要在Skyline點(diǎn)中選擇適合自己的結(jié)果.

圖1 二手車數(shù)據(jù)skyline分布圖Fig.1 Skyline map of used car data

目前存在很多Skyline查詢處理算法,主要是基于排序、分治和索引3類.然而現(xiàn)有Skyline方法都是通過(guò)設(shè)計(jì)在點(diǎn)與點(diǎn)之間進(jìn)行支配關(guān)系測(cè)試的各種算法最終求解Skyline集合的.與所有基于點(diǎn)的Skyline方法不同,本文提出一種對(duì)空間分塊進(jìn)行關(guān)系測(cè)試,通過(guò)對(duì)空間劃分的不斷細(xì)化最終得到Skyline集的名為CSL(Cell Skyline)的求解方法.

這種基于網(wǎng)格的Skyline求解方法相對(duì)于其它基于點(diǎn)的方法的優(yōu)勢(shì)在于：1)同一劃分層次的網(wǎng)格內(nèi)容可以并行計(jì)算,因而可以設(shè)計(jì)并行算法在多核CPU或GPU上進(jìn)行處理;2)計(jì)算過(guò)程可以根據(jù)需要達(dá)到任意精度,既可以計(jì)算出精確的Skyline點(diǎn),也可以停止在任意的網(wǎng)格層次.因而在計(jì)算能力有限但對(duì)結(jié)果精度要求不高的場(chǎng)合更加適用.

2 相關(guān)工作

Borzsony等[1]在2001年首先提出了Skyline操作,并且提出了3種基本實(shí)現(xiàn)Skyline操作的思路,分別基于排序,分治和索引方式.后續(xù)進(jìn)行Skyline算法研究的大部分學(xué)者們,在沿著這3種思路進(jìn)行深入探索的過(guò)程中,提出了很多有代表性的算法.

基于排序.自BNL[1]被提出后,串行算法從SFS[2]到LESS[3]再到SaLSa[4]他們的核心思想是依據(jù)單調(diào)函數(shù)進(jìn)行預(yù)先排序來(lái)避免過(guò)多的兩點(diǎn)之間各個(gè)維度比較,實(shí)際上因?yàn)樵谂藕眯蚝?當(dāng)前點(diǎn)只能被前驅(qū)點(diǎn)所控制,而不會(huì)被后繼點(diǎn)控制,所以一旦發(fā)現(xiàn)當(dāng)前點(diǎn)被控,后面的點(diǎn)都無(wú)需再進(jìn)行檢查,他們之間的根本差異在于所選單調(diào)函數(shù)的不同;后來(lái)當(dāng)并行算法興起后,Wonik Choi等人的GNL[5]算法對(duì)BNL進(jìn)行了暴力并行化,B?gh,Kenneth S等人提出的GGS[6]算法達(dá)到了最大理論吞吐量,但是由于并行算法比串行算法多做上百倍的工作,所以在性能上并沒(méi)有趕超串行算法.

基于分治.S.Zhang[7]和J.Lee[8]提出的串行算法是基于點(diǎn)劃分的,關(guān)鍵點(diǎn)在于每次劃分如何選擇pivot,多核算法如Pskyline[9]和Hybrid[10],并行算法SkyAlign[11]采用了基于網(wǎng)格劃分的搜索樹(shù),這種方式只在意吞吐量,導(dǎo)致效率不如順序算法.串行和多核算法的瓶頸都在于合并代價(jià)大,每4個(gè)小格就需要進(jìn)行3次合并,且劃分會(huì)隱藏控制性,導(dǎo)致大量的冗余處理,處理代價(jià)增大;

基于索引.一些算法[12-16]采用了優(yōu)化的Hash Index、R-Tree或MapReduce索引結(jié)構(gòu),取得了一定的優(yōu)化效果.Liu等提出的基于Voronoi變形的Skyline Diagram[17]和李松等人提出的基于Voronoi圖的K-支配空間Skyline查詢方法[18],性能上優(yōu)于以往的索引算法.DFTS[19]和基于STR-Tree的Skyline查詢算法采用過(guò)濾剪枝的策略,縮短了在大數(shù)據(jù)環(huán)境下的時(shí)間開(kāi)銷.這些基于索引的Skyline算法的優(yōu)點(diǎn)在于一旦索引結(jié)構(gòu)建立完成,則無(wú)需訪問(wèn)全部數(shù)據(jù)即可獲得Skyline集合,而且查詢快速.但其無(wú)法避免的弊端是索引的構(gòu)建成本高,不適用于動(dòng)態(tài)的查找,應(yīng)用范圍較窄.

3 問(wèn)題定義

給定包含n個(gè)d維數(shù)據(jù)點(diǎn)的集合P,首先定義P中的Skyline點(diǎn).

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

記p[i]為點(diǎn)p第i維的值,則點(diǎn)支配可定義如下.

定義2.(點(diǎn)支配)任給p,q∈P,q被p支配(記為pq)當(dāng)且僅當(dāng)：1)對(duì)于任意維度k

pq?(?k∈[0,d),p[k]≤q[k])∧
(?r∈[0,d),p[r]

(1)

P中所有的Skyline點(diǎn)構(gòu)成P的Skyline集.

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

S={p∈P|q∈P：qp}

(2)

稱S為P的Skyline集.

下面討論一種高度并行的Skyline集求解方法.

4 基于網(wǎng)格的Skyline

本方法主要思路如下：將空間劃分成網(wǎng)格形式,則網(wǎng)格之間存在支配關(guān)系,所有網(wǎng)格可以被分為a)確認(rèn)被支配區(qū)域,b)確認(rèn)不能支配其它網(wǎng)格的區(qū)域和c)尚未明確區(qū)域,每個(gè)區(qū)域包含一系列連續(xù)的網(wǎng)格.本文證明,Skyline點(diǎn)只存在于未確認(rèn)區(qū)域中.因此,可將未確認(rèn)區(qū)域進(jìn)一步細(xì)化,繼續(xù)劃分為上述3種類型網(wǎng)格區(qū)域.隨著網(wǎng)格劃分粒度的逐漸細(xì)化,未確認(rèn)區(qū)域所占空間不斷變小,空間中包含的點(diǎn)逐漸收斂于Skyline集合,從而可以得到最終的Skyline結(jié)果.

4.1 網(wǎng)格支配

按粒度由粗到細(xì)對(duì)空間進(jìn)行多次劃分,每次劃分稱為一層.第1層將空間的每一維度劃分為2部分,第2層將每一維度劃分為4部分,依此類推,第m層將每一維度劃分為2m部分.因此,第m個(gè)劃分層次中,空間被分為2d·m部分.為簡(jiǎn)化計(jì)算,以下僅討論所有劃分皆為均分的情況,此時(shí)第m層每個(gè)網(wǎng)格所占的空間在第m+1層都將被均分為2d個(gè)網(wǎng)格.

如果網(wǎng)格ci不為空,則對(duì)于某些網(wǎng)格cj,任何存在于cj中的點(diǎn)一定會(huì)被ci中的任意點(diǎn)支配.這種情況下,稱cj被ci支配：

定理1.同一層網(wǎng)格ci,cj,當(dāng)1)ci不為空;2)?k∈[0,d],ci[k]

證明：當(dāng)cicj時(shí),由條件1知ci中存在數(shù)據(jù)點(diǎn),任取其中一點(diǎn)pi.如果cj為空,則定理得證.如cj不為空,其中任何一點(diǎn)pj,由條件2知：

?k∈[0,d),pi[k]

(3)

根據(jù)定義2知pipj.根據(jù)定義1,pj不可能為Skyline點(diǎn).

圖2 各層cell的類別Fig.2 Types of cells in each layer

4.2 網(wǎng)格分類

由定理1簡(jiǎn)單推導(dǎo)可知,每層網(wǎng)格可分為3個(gè)集合：1)被支配(Dominated)的網(wǎng)格,記為D;2)不被支配的空(Empty)網(wǎng)格,記為E和;3)未確認(rèn)(Uncertain)網(wǎng)格,記為U.將第m層所有網(wǎng)格集合記為Cm,或簡(jiǎn)記為C,顯然有：

C=D∪E∪U

D∩E=E∩U=U∩D=?.

(4)

定理2.Skyline點(diǎn)只存在于集合U中.

證明：由于D,E,U是集合C的劃分,只需證明D、E中不存在Skyline點(diǎn).由定理1知D中不存在Skyline點(diǎn),而E中皆為空網(wǎng)格也不可能存在Skyline點(diǎn).

由于Skyline點(diǎn)只存在于集合U中,顯然U占據(jù)的空間越小對(duì)于確定S集越有利.

(5)

推理1.第m層和第m+1層的被支配網(wǎng)格集和不被支配空網(wǎng)格集所對(duì)應(yīng)的空間滿足關(guān)系：

(6)

證明：由定理3可直接得出結(jié)論.

由于Skyline點(diǎn)只存在于集合U中,顯然D中的網(wǎng)格都是被U中的網(wǎng)格支配的.本研究發(fā)現(xiàn),存在關(guān)鍵(Key)網(wǎng)格集合K?U,由K支配的網(wǎng)格集與U支配的網(wǎng)格集一致.

定理4.給定網(wǎng)格c∈U,如果對(duì)于c的任一維k∈[0,d),所有滿足c′∈U且?j∈[0,d),j≠k,c′[j]=c[j]的網(wǎng)格c′都有c′[k]≥c[k],稱c為一個(gè)關(guān)鍵網(wǎng)格,所有關(guān)鍵網(wǎng)格的集合記為K,則被K支配的網(wǎng)格集與被U支配的網(wǎng)格集一致,即：

(7)

證明：因?yàn)镵?U,所以被K支配的網(wǎng)格集被包含于被U支配的網(wǎng)格集.下面用反證法證明被K支配的網(wǎng)格集包含被U支配的網(wǎng)格集.假設(shè)存在網(wǎng)格cd∈D,并且不存在ck∈K滿足ckcd,那么必然存在網(wǎng)格cu∈U且cu?K滿足cucd,即?j∈[0,d),cd[j]≥cu[j].因?yàn)閏u?K,必然至少存在任一維k,存在滿足c′∈U且?j∈[0,d),j≠k,c′[j]=c[j]的網(wǎng)格c′,c′[k]

由于K的特殊性,在由第m層到第m+1層的劃分中,可由Km中的網(wǎng)格入手找到Km+1.

4.3 網(wǎng)格細(xì)化

引理1.關(guān)鍵網(wǎng)格c∈K中必定包含至少一個(gè)Skyline點(diǎn).

證明：c∈K,因此c不為空.考察c中包含的點(diǎn)集P′,由于任何一個(gè)點(diǎn)集中必然存在Skyline點(diǎn),則必然存在P′為全集的非空Skyline集S′.根據(jù)K的定義可知,如果對(duì)于c∈K的任一維k,所有滿足c′∈U且?j∈[0,d),j≠k,c′[j]=c[j]的網(wǎng)格c′都有c′[k]≥c[k],因此K中不存在其它網(wǎng)格中的點(diǎn)能夠支配S′中的任何點(diǎn).由此可知,S′?S.

引理2.Km中任一網(wǎng)格cm所占據(jù)的空間在Cm+1中被2d個(gè)網(wǎng)格占據(jù),記這些網(wǎng)格的集合為F.則：

1)F中至少有一個(gè)屬于Km+1;

2)F中的網(wǎng)格不可能被不屬于F的網(wǎng)格支配;

2)用反證法證明.假設(shè)D中的網(wǎng)格c被不屬于D的網(wǎng)格c′支配,則c′在第m層所屬的網(wǎng)格在任一維度上必然都不大于cm,與定理4中關(guān)鍵網(wǎng)格的定義矛盾.因此命題得證.

由定理3可知,下一層的未確認(rèn)網(wǎng)格肯定由上一層的未確認(rèn)網(wǎng)格劃分產(chǎn)生.更進(jìn)一步,下一層的關(guān)鍵網(wǎng)格集可以由上一層的關(guān)鍵網(wǎng)格集按如下定理所指出的方式產(chǎn)生.

定理5.第m+1層的關(guān)鍵網(wǎng)格集Km+1中的任一元素c滿足：1)c是第m層的某個(gè)關(guān)鍵網(wǎng)格劃分后的2d個(gè)網(wǎng)格中的一個(gè);或者2)存在一第m層的關(guān)鍵網(wǎng)格劃分后的空網(wǎng)格c′,c和c′至少有1維的序號(hào)相同,且在序號(hào)不同的維上c的序號(hào)都大于c′.

證明：由引理2知,如果c是第m層的某個(gè)關(guān)鍵網(wǎng)格劃分后的2d個(gè)網(wǎng)格中的一個(gè),則它不可能被不屬于該關(guān)鍵網(wǎng)格劃分而成的其它網(wǎng)格支配.因此,只要c不被該關(guān)鍵網(wǎng)格自身劃分而成的網(wǎng)格支配,則它一定是第m+1層的關(guān)鍵網(wǎng)格.

如果c不是第m層的某個(gè)關(guān)鍵網(wǎng)格劃分后的2d個(gè)網(wǎng)格中的一個(gè),則需要證明條件2.首先證明對(duì)于U中的任一非關(guān)鍵網(wǎng)格cu都存在同一層的一個(gè)關(guān)鍵網(wǎng)格ck,二者至少有1維的序號(hào)相同,且在序號(hào)不同的維上cu的序號(hào)都大于ck.假設(shè)上述命題不成立,即1)cu和所有關(guān)鍵網(wǎng)格ck的所有序號(hào)都不相同,或者2)在序號(hào)不同的維上cu的序號(hào)不都大于ck.

如果1)成立,那么存在以下3種情況：a)cu所有序號(hào)都比某一關(guān)鍵網(wǎng)格小,則cu被支配;b)cu所有序號(hào)都比某一關(guān)鍵網(wǎng)格大,則cu支配該關(guān)鍵網(wǎng)格;c)cu所有序號(hào)與任一關(guān)鍵網(wǎng)格相比都有大有小,則cu本身應(yīng)為關(guān)鍵網(wǎng)格.所以上述3種均與cu是屬于U的非關(guān)鍵網(wǎng)格這一事實(shí)矛盾.

如果2)成立,那么也存在類似1)中b和c的兩種情況,同樣可以推出與cu是屬于U的非關(guān)鍵網(wǎng)格這一事實(shí)的矛盾,因此命題成立.

由上述命題可知,第m+1層的c對(duì)應(yīng)的第m層的網(wǎng)格c′u必然對(duì)應(yīng)一關(guān)鍵網(wǎng)格c′k,c′k劃分后的第m+1層的網(wǎng)格必然存在和c至少有1維的序號(hào)相同,且在序號(hào)不同的維上的序號(hào)都小于c的網(wǎng)格c′.由于c是關(guān)鍵網(wǎng)格,所以c′肯定為空.

下一章本文設(shè)計(jì)了一種根據(jù)上層關(guān)鍵網(wǎng)格集找到下層關(guān)鍵網(wǎng)格集的具體算法.

5 CSL并行算法

本章采用類C++的偽代碼對(duì)基于網(wǎng)格的Skyline查詢處理方法(Cell based SkyLine,CSL)所采用的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行描述.

5.1 數(shù)據(jù)結(jié)構(gòu)

首先創(chuàng)建一個(gè)全局Node數(shù)組N存儲(chǔ)P中的所有數(shù)據(jù)點(diǎn),其中每個(gè)Node對(duì)應(yīng)P中的一個(gè)點(diǎn)p.然后建立層次型的索引結(jié)構(gòu)C用以索引P中的數(shù)據(jù)點(diǎn).索引結(jié)構(gòu)C共有M層,第0層只有一個(gè)網(wǎng)格,之后每一層都將上一層的網(wǎng)格分為2d部分,即第m層包含2d·m個(gè)網(wǎng)格.除了劃分程度最細(xì)的第M-1層(最底層),所有層次都只存儲(chǔ)該網(wǎng)格是否為空的bool類型信息.第M-1層中除了存儲(chǔ)該網(wǎng)格是否為空的信息外,還額外存儲(chǔ)數(shù)據(jù)點(diǎn)的基本信息.

以二維為例,P中的每個(gè)點(diǎn)p都在N中存在唯一對(duì)應(yīng)的一個(gè)Node,其中包含點(diǎn)p的x維和y維的位置信息.

算法1.創(chuàng)建索引 Index Creating,IC

輸入：數(shù)據(jù)集P,M為劃分層數(shù)

輸出：全局?jǐn)?shù)組N,索引結(jié)構(gòu)C

1.用P中的數(shù)據(jù)點(diǎn)填充N

2.foreachp∈Npardo

/*其中index(p,i)代表p在DM-1中第i維的序號(hào)*/

4.foreachδ∈DM-1pardo

6.form←M-2to0do

7.forj1←0to2m,…,jd←0to2mpardo

/*上式右側(cè)為所有序號(hào)對(duì)應(yīng)于一個(gè)迪卡爾積

{2j1,2j1+1}×…×{2jd,2jd+1}中元素的網(wǎng)格*/

5.2 CSL算法

根據(jù)定理5描述的兩個(gè)相鄰劃分層次間關(guān)鍵網(wǎng)格的關(guān)聯(lián)關(guān)系,本節(jié)提出一種基于逐步細(xì)化網(wǎng)格的高并行化Skyline求解方法.本方法建立在并行理論基礎(chǔ)上,因此可以在多核并行環(huán)境下或GPU加速環(huán)境下實(shí)現(xiàn),從而最大程度地提升執(zhí)行效率,縮短查詢處理時(shí)間.

由于第0層只有一個(gè)網(wǎng)格,且該網(wǎng)格肯定是關(guān)鍵網(wǎng)格,因此可以從第0層開(kāi)始,采用基于定理5的算法可以找到任意層次的關(guān)鍵網(wǎng)格集.由定理4知,關(guān)鍵網(wǎng)格集K可以代表未確定網(wǎng)格集U,也即由K可以得到U.再根據(jù)定理2知,Skyline點(diǎn)肯定存在于U中,因此可以通過(guò)該算法找到所有Skyline點(diǎn).

算法2.基于網(wǎng)格的Skyline查詢 Cell based Skyline,CSL

輸入：全局?jǐn)?shù)組N,索引結(jié)構(gòu)C,M為劃分層數(shù)

輸出：Skyline集S

2.form←1toM-1do

3.Um-1←Get_U_From_K(C,Km-1)

4.Km←Shrink_K(C,Km-1,Um-1)

5.Sk←SkyLine(KM-1)

6.Su←SkyLine_Filtered_by_K(UM-1,KM-1,Sk)

7.returnS←Sk∪Su

在采用算法1建立索引之后,在劃分逐步細(xì)化的過(guò)程中,U集不斷縮小.從理論上講,可以不斷細(xì)化劃分層次,直到某一層中每個(gè)網(wǎng)格最多只包含一個(gè)數(shù)據(jù)點(diǎn)為止.根據(jù)定理2和定理5知,此時(shí)K中網(wǎng)格包含的數(shù)據(jù)點(diǎn)即為所有Skyline點(diǎn).然而在實(shí)際查詢過(guò)程中,采用這種極限細(xì)化的方式需要將層次數(shù)M設(shè)為大于logd|P|,顯然效率過(guò)低.

因此,本算法(算法2)實(shí)際分為兩大步驟：首先,計(jì)算出足夠細(xì)化的層次中的非確定集U,根據(jù)定理2知Skyline點(diǎn)只存在于集合U中(1～4行).然后,對(duì)U中各個(gè)網(wǎng)格中數(shù)據(jù)點(diǎn)進(jìn)行檢查,得到最終的Skyline點(diǎn)(5～6行).

算法首先從第0層開(kāi)始,依次調(diào)用Shrink_K函數(shù)(算法3)獲得每一層的關(guān)鍵網(wǎng)格集,并把結(jié)果作為下一層調(diào)用的輸入?yún)?shù)(2～4行).其中,需要根據(jù)Km-1在同一層中找到其對(duì)應(yīng)的未確認(rèn)網(wǎng)格集UM-1(第3行)作為Shrink_K函數(shù)的參數(shù).

根據(jù)定理2知,Skyline點(diǎn)肯定存在于UM-1中,因此可以理論上直接將UM-1中的數(shù)據(jù)點(diǎn)取出,調(diào)用傳統(tǒng)Skyline方法得到S集.然而引理1實(shí)際上暗示了K集中的Skyline點(diǎn)密度遠(yuǎn)大于U集的非關(guān)鍵網(wǎng)格.因此,先找出KM-1中的Skyline點(diǎn)Sk(第5行).引理2保證了Sk中的點(diǎn)必然不會(huì)被U集的非關(guān)鍵網(wǎng)格中的點(diǎn)支配,即KM-1中的Skyline點(diǎn)必然屬于S.在尋找UM-1集中非關(guān)鍵網(wǎng)格的Skyline點(diǎn)時(shí),可以先用Sk對(duì)數(shù)據(jù)點(diǎn)進(jìn)行支配判斷,最后在不被Sk支配的點(diǎn)集中尋找Skyline點(diǎn)集Su(第6行).

由上述討論可知,Sk和Su的并集就是最終的Skyline點(diǎn)集S.

算法3.縮減關(guān)鍵網(wǎng)格Shrink_K

輸入：索引結(jié)構(gòu)C,Km-1,Um-1

輸出：關(guān)鍵網(wǎng)格集Km

1.H←?

2.foreachk∈Km-1pardo

4.Kk,E←Identify_K_and_E(K′k)

5.U′k←Slice_Uwith_Common_Dim(k,Um-1)

6.foreache∈Epardo

7.Ku←Ku∪Identify_K_from_E(e,U′k)

8.H←H∪Kk∪Ku

9.returnH

依次對(duì)每一層的關(guān)鍵網(wǎng)格集進(jìn)行計(jì)算(Shrink_K函數(shù))是算法2的關(guān)鍵.算法3給出了這一過(guò)程的詳細(xì)步驟.對(duì)于每個(gè)關(guān)鍵節(jié)點(diǎn)k,找出由它產(chǎn)生的新的關(guān)鍵節(jié)點(diǎn),其中包括(a)k自身在下一層劃分中的關(guān)鍵節(jié)點(diǎn)(3～4行),和(b)與k有相同維度序號(hào)的非關(guān)鍵節(jié)點(diǎn)在下一層劃分中產(chǎn)生的關(guān)鍵節(jié)點(diǎn)(5～7行).

步驟a：獲取k劃分成的2d個(gè)網(wǎng)格K′k(第3行),其中不被K′k中其它網(wǎng)格支配的非空網(wǎng)格必定是新的關(guān)鍵網(wǎng)格(引理2),將新的關(guān)鍵網(wǎng)格加入Kk,其它網(wǎng)格加入E(第4行).

步驟b：先從Um-1中找到和k具有相同維度序號(hào)的網(wǎng)格集,然后劃分加入集合U′k中(第5行).對(duì)步驟a中找到的E中的每個(gè)網(wǎng)格,根據(jù)定理5在U′k中找到對(duì)應(yīng)的新關(guān)鍵網(wǎng)格(6-7行).注意定理5能夠保證新的關(guān)鍵網(wǎng)格必定能通過(guò)這種方式找到,但不保證E中的每個(gè)網(wǎng)格都存在一個(gè)對(duì)應(yīng)的關(guān)鍵網(wǎng)格.

圖3 算法中cell的分類Fig.3 Classification of cells in the algorithm

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

本節(jié)將提出的CSL算法與目前最先進(jìn)的Skyline Diagram系列算法中的QSweep[17]進(jìn)行對(duì)比.

表1 實(shí)驗(yàn)參數(shù)Table 1 Experiment parameters

實(shí)驗(yàn)仿真環(huán)境為Win 10系統(tǒng),Intel Xeon Silver 4110核CPU.實(shí)驗(yàn)代碼由C++實(shí)現(xiàn),空間對(duì)象數(shù)據(jù)采用的真實(shí)NBA數(shù)據(jù)和由開(kāi)源對(duì)象生成工具生成的數(shù)據(jù),實(shí)驗(yàn)參數(shù)如表1所示.

圖4 數(shù)據(jù)點(diǎn)數(shù)量對(duì)查詢時(shí)間的影響Fig.4 Query time vs. number of query points

圖4給出了數(shù)據(jù)點(diǎn)數(shù)量對(duì)查詢時(shí)間的影響的實(shí)驗(yàn)結(jié)果.隨著數(shù)據(jù)點(diǎn)數(shù)量的增多,可以看到兩種方法所需的時(shí)間也隨之增多.由于本文提出的CSL方法采用了基于網(wǎng)格的支配判定策略,因而在各種數(shù)據(jù)量情況下執(zhí)行都明顯優(yōu)于Qsweep.

圖5 數(shù)據(jù)維度對(duì)查詢時(shí)間的影響Fig.5 Query time vs. data dimensions

仔細(xì)觀察還可以發(fā)現(xiàn),當(dāng)數(shù)據(jù)量不斷增多時(shí),CSL方法所需時(shí)間增長(zhǎng)的速度更慢.這是因?yàn)镃SL方法在劃分層次的上層就已經(jīng)能夠去掉大多數(shù)肯定不能成為Skyline結(jié)果的數(shù)據(jù).因此這些數(shù)據(jù)不會(huì)在后期被應(yīng)用于數(shù)據(jù)點(diǎn)支配情況的判定.

圖5給出了數(shù)據(jù)點(diǎn)維度數(shù)對(duì)查詢時(shí)間的影響的實(shí)驗(yàn)結(jié)果.隨著數(shù)據(jù)點(diǎn)維度由2維逐漸增加到5維,兩種方法所需的時(shí)間也隨之增多,但是CSL方法所需時(shí)間增長(zhǎng)的速度更慢.這主要是因?yàn)镃SL方法的基于網(wǎng)格的剪枝策略對(duì)于更高維數(shù)據(jù)依然保持有效,而傳統(tǒng)方法在處理高維數(shù)據(jù)時(shí)則會(huì)損失更多的執(zhí)行效率.

圖6 CPU核心數(shù)對(duì)查詢時(shí)間的影響Fig.6 Query time vs. the number of CPU cores

在圖6中本文研究了CPU核心數(shù)對(duì)CSL方法查詢時(shí)間的影響.由圖中可以看出,隨著使用的CPU核數(shù)增多,整體查詢處理時(shí)間有明顯下降.但是隨著核心數(shù)進(jìn)一步增加,對(duì)處理時(shí)間的影響逐漸減弱.這是因?yàn)殡m然CSL相對(duì)其它算法具備更強(qiáng)的并行能力,但多個(gè)線程之間還是難以避免地存在一定的依賴關(guān)系,因此部分線程之間需要相互等待進(jìn)而影響了整體處理速度.

7 結(jié)束語(yǔ)

本文提出了一種基于網(wǎng)格的Skyline求解方法,通過(guò)將空間按層劃分成網(wǎng)格形式,并在每一層中將所有網(wǎng)格可以被分為三種不同區(qū)域,將未確認(rèn)區(qū)域在層次遞增時(shí)進(jìn)一步細(xì)化,使空間中包含的點(diǎn)逐漸收斂于Skyline集合,從而可以得到最終的Skyline結(jié)果.本方法特點(diǎn)如下：

1)同一劃分層次的網(wǎng)格內(nèi)容可以并行計(jì)算,因而可以設(shè)計(jì)并行算法在多核CPU或GPU上進(jìn)行處理.

2)計(jì)算過(guò)程可以根據(jù)需要達(dá)到任意精度,既可以計(jì)算出精確的Skyline點(diǎn),也可以停止在任意的網(wǎng)格層次.

3)本方法更加適用于計(jì)算能力有限但對(duì)結(jié)果精度要求不高的場(chǎng)合.