李佳佺,劉晏如,李傳文

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

1 引 言

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

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

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

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

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

2 相關(guān)工作

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

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

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

基于索引.一些算法[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查詢算法采用過濾剪枝的策略,縮短了在大數(shù)據(jù)環(huán)境下的時間開銷.這些基于索引的Skyline算法的優(yōu)點在于一旦索引結(jié)構(gòu)建立完成,則無需訪問全部數(shù)據(jù)即可獲得Skyline集合,而且查詢快速.但其無法避免的弊端是索引的構(gòu)建成本高,不適用于動態(tài)的查找,應(yīng)用范圍較窄.

3 問題定義

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

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

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

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

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

(1)

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

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

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

(2)

稱S為P的Skyline集.

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

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

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

4.1 網(wǎng)格支配

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

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

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

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

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

(3)

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

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

4.2 網(wǎng)格分類

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

C=D∪E∪U

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

(4)

定理2.Skyline點只存在于集合U中.

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

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

(5)

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

(6)

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

由于Skyline點只存在于集合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,如果對于c的任一維k∈[0,d),所有滿足c′∈U且?j∈[0,d),j≠k,c′[j]=c[j]的網(wǎng)格c′都有c′[k]≥c[k],稱c為一個關(guān)鍵網(wǎng)格,所有關(guān)鍵網(wǎng)格的集合記為K,則被K支配的網(wǎng)格集與被U支配的網(wǎng)格集一致,即：

(7)

證明：因為K?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].因為cu?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)格細化

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

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

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

1)F中至少有一個屬于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可知,下一層的未確認網(wǎng)格肯定由上一層的未確認網(wǎng)格劃分產(chǎn)生.更進一步,下一層的關(guān)鍵網(wǎng)格集可以由上一層的關(guān)鍵網(wǎng)格集按如下定理所指出的方式產(chǎn)生.

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

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

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

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

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

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

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

5 CSL并行算法

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

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

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

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

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

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

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

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

2.foreachp∈Npardo

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

4.foreachδ∈DM-1pardo

6.form←M-2to0do

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

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

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

5.2 CSL算法

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

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

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

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

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

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

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

由上述討論可知,Sk和Su的并集就是最終的Skyline點集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

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

步驟a：獲取k劃分成的2d個網(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具有相同維度序號的網(wǎng)格集,然后劃分加入集合U′k中(第5行).對步驟a中找到的E中的每個網(wǎng)格,根據(jù)定理5在U′k中找到對應(yīng)的新關(guān)鍵網(wǎng)格(6-7行).注意定理5能夠保證新的關(guān)鍵網(wǎng)格必定能通過這種方式找到,但不保證E中的每個網(wǎng)格都存在一個對應(yīng)的關(guān)鍵網(wǎng)格.

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

6 實驗結(jié)果與分析

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

表1 實驗參數(shù)Table 1 Experiment parameters

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

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

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