王海翔，鄭吉平,2,3+，王永閣

1.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106 2.南京大學(xué) 計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，南京 210023 3.新南威爾士大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，悉尼，澳大利亞 NSW 2052

結(jié)合非空間屬性的通用Skyline查詢處理技術(shù)*

王海翔1，鄭吉平1,2,3+，王永閣1

1.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106 2.南京大學(xué) 計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，南京 210023 3.新南威爾士大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，悉尼，澳大利亞 NSW 2052

WANG Haixiang,ZHENG Jiping,WANG Yongge.General Skyline query processing technology combining with non-spatial attributes.Journal of Frontiers of Computer Science and Technology,2016,10(7)：936-947.

Skyline查詢作為多目標(biāo)決策的重要手段之一，近年來在各個領(lǐng)域得到廣泛的應(yīng)用。提出了結(jié)合非空間屬性的通用Skyline查詢處理技術(shù)，采用R樹對設(shè)施集及數(shù)據(jù)集建立索引，并提出了兩種方法來計算Skyline。第一種是基于全最近鄰算法的擴(kuò)展，通過計算靜態(tài)Skyline結(jié)果來裁剪部分?jǐn)?shù)據(jù)集。另一種是基于漸進(jìn)最近鄰的算法，采用查詢點(diǎn)導(dǎo)向的搜索方法，利用靜態(tài)Skyline結(jié)果計算與每一類設(shè)施最遠(yuǎn)的距離，將其作為邊界閾值對數(shù)據(jù)點(diǎn)集進(jìn)行裁剪，采用數(shù)據(jù)點(diǎn)導(dǎo)向的搜索方法，為裁剪后的每一個數(shù)據(jù)點(diǎn)計算距其最近的設(shè)施，并將數(shù)據(jù)點(diǎn)與設(shè)施的距離映射到多維距離空間中，結(jié)合非空間屬性進(jìn)行Skyline計算。實(shí)驗(yàn)結(jié)果表明，第二種方法減少了I/O次數(shù)，降低了CPU執(zhí)行時間，提高了計算效率。

通用Skyline查詢；R樹索引；非空間屬性；最近鄰

1　引言

衛(wèi)星成像技術(shù)、GPS定位技術(shù)和醫(yī)學(xué)圖像技術(shù)的發(fā)展促使了空間數(shù)據(jù)的產(chǎn)生，隨著空間數(shù)據(jù)的增加，對其進(jìn)行分析、處理、應(yīng)用的需求也不斷增大。此外，移動設(shè)備、無線通信技術(shù)的發(fā)展使得位置服務(wù)（location based services，LBS）在人們的日常生活中得到了廣泛應(yīng)用。Skyline查詢作為多目標(biāo)決策的重要手段之一，其在位置服務(wù)系統(tǒng)中也具有重要意義。

傳統(tǒng)Skyline查詢從給定數(shù)據(jù)集中返回不被其他點(diǎn)支配的點(diǎn)，然而實(shí)際應(yīng)用中，可能還需要考慮其他因素的影響。例如，同學(xué)聚會時通常會選擇交通方便的餐館，因此會考慮離公交站臺（假設(shè)只有一種交通工具）近的餐館。然而除了聚餐，可能還有其他活動，如看電影，往往電影院和餐館有一定的距離。這樣就想找一個距離電影院、公交站臺都很近的餐館，但是電影院、公交站臺又有很多個，并不能確定選擇哪一個電影院、公交站臺，這里針對某個餐館，選擇距其最近的公交站臺和電影院作為距離的衡量標(biāo)準(zhǔn)。如圖1（a）所示，在圖中有一些公交站臺、電影院和餐館，如距離點(diǎn)p1最近的公交站臺和電影院分別為b2和c2，然后將每個點(diǎn)映射到圖1（b）的二維距離空間中，其中每個點(diǎn)的坐標(biāo)含義是該餐館與公交站臺和電影院的最近距離，由此可得Skyline結(jié)果為{p1,p8}。對于這種類型的Skyline查詢稱之為通用Skyline查詢（general Skyline queries）。此外，在選擇餐館時，可能并不僅僅關(guān)注距離這方面的屬性，往往餐館的非空間屬性，如價格、評級、服務(wù)質(zhì)量等也需要考慮在內(nèi)，因此需要考慮結(jié)合非空間屬性的查詢。

Fig.1　Example of general Skyline queries圖1　通用Skyline查詢例子

此外，通用Skyline查詢這類問題看成多源Skyline查詢問題，對于多源Skyline查詢已有一些研究，如文獻(xiàn)[1-2]等，但這些研究中考慮的查詢點(diǎn)是確定的，即在Skyline查詢之前已確定了查詢點(diǎn)的位置，因此可以利用一些空間幾何的特性來處理這一類問題。但當(dāng)查詢點(diǎn)不確定時，首先需要確定查詢點(diǎn)，然后才能進(jìn)行Skyline查詢。因?yàn)閷τ谕愒O(shè)施而言，不同的數(shù)據(jù)點(diǎn)對應(yīng)的查詢點(diǎn)可能是不同的，所以現(xiàn)有研究所采用的方法并不適用于這種查詢。針對以上問題，本文提出了結(jié)合非空間屬性的通用Skyline查詢處理技術(shù)。

目前在多維數(shù)據(jù)查詢的索引中，R樹索引具有明顯優(yōu)勢，并且本文設(shè)計的數(shù)據(jù)集均為多維數(shù)據(jù)集，為避免R樹中節(jié)點(diǎn)的重疊區(qū)域過多，采用R樹的變種R*樹建立索引。因此，首先采用R樹對設(shè)施集以及查詢數(shù)據(jù)集建立索引來進(jìn)行Skyline查詢，進(jìn)而提出基于全最近鄰的Skyline查詢算法及其擴(kuò)展算法，以及基于漸進(jìn)最近鄰的Skyline查詢算法。前者采用數(shù)據(jù)點(diǎn)導(dǎo)向搜索方法來為每一個數(shù)據(jù)點(diǎn)計算各類型設(shè)施中距離其最近的點(diǎn)，然后將該數(shù)據(jù)點(diǎn)與各類設(shè)施中點(diǎn)的距離映射到距離空間中，結(jié)合非空間屬性并采用已有的Skyline查詢處理方法進(jìn)行Skyline的計算。因?yàn)殪o態(tài)Skyline結(jié)果不受距離支配的限制，仍然會屬于最終Skyline，所以基于全近鄰算法的擴(kuò)展方法主要通過預(yù)先計算靜態(tài)Skyline來減少數(shù)據(jù)集進(jìn)行最近鄰設(shè)施計算的個數(shù)，從而提高效率。后者采用查詢點(diǎn)導(dǎo)向和數(shù)據(jù)點(diǎn)導(dǎo)向相結(jié)合的方法，首先計算靜態(tài)Skyline結(jié)果，并計算其與各類設(shè)施距離的最大值作為閾值，每一類設(shè)施維護(hù)一個優(yōu)先權(quán)隊列，利用漸進(jìn)最近鄰的方法，使用閾值對數(shù)據(jù)集進(jìn)行剪枝，對那些遠(yuǎn)于閾值的點(diǎn)進(jìn)行裁剪，從而減少I/O以及各個數(shù)據(jù)點(diǎn)之間的支配性比較代價，提高計算效率。

2　相關(guān)工作

Borzsonyi等人[3]在數(shù)據(jù)庫查詢領(lǐng)域引入了Skyline操作后，研究人員在此基礎(chǔ)上對集中數(shù)據(jù)庫中的Skyline查詢技術(shù)提出了許多改進(jìn)方法[2，4-15]。

Sharifzadeh等人[1]首先介紹了空間Skyline的概念。假設(shè)P為數(shù)據(jù)點(diǎn)集合，Q為查詢點(diǎn)集合，那么對Q而言，P的空間Skyline由P中沒有被其他點(diǎn)所支配的點(diǎn)組成。提出了B2S（2branch-and-bound spatial Skyline）算法和VS（2Voronoi-based spatial Skyline）算法來計算空間Skyline結(jié)果。B2S2算法是在BBS（branchand-bound Skyline）算法的基礎(chǔ)上提出的，使用R樹為數(shù)據(jù)構(gòu)建索引。VS2算法是基于Voronoi圖的方法，主要思想是遍歷Voronoi圖對應(yīng)的Delaunay圖，在遍歷過程中對圖進(jìn)行邊界限定從而降低搜索空間。此外，還提出了VCS（2Voronoi-based continuous spatial Skyline query）算法對連續(xù)空間Skyline查詢進(jìn)行處理。Son等人[16]在上述研究的基礎(chǔ)上對算法進(jìn)行了改進(jìn)。首先針對VS2算法不能完全返回正確的結(jié)果進(jìn)行了驗(yàn)證，然后提出了一個新穎又有效的算法來進(jìn)行空間Skyline查詢。

文獻(xiàn)[17-18]研究了單查詢點(diǎn)移動的連續(xù)Skyline查詢處理問題。Huang等人[17]利用時空相關(guān)性表示空間屬性沒有顯著變化的兩個時間片刻，通過維護(hù)事件來逐步求解Skyline結(jié)果。Cheema等人[18]提出使用安全區(qū)域（safe zone）的思想來減少屬于最終空間Skyline的點(diǎn)的重復(fù)遍歷。此外，Deng等人[2]提出了3個算法研究了公路網(wǎng)中的空間Skyline查詢處理問題。Yoon等人[19]研究了無線傳感器網(wǎng)絡(luò)中的空間Skyline查詢處理問題，用來進(jìn)行多目標(biāo)協(xié)同定位，提出了一個分布式的空間Skyline查詢算法（distributed spatial Skyline，DSS）。DSS算法通過節(jié)點(diǎn)之間的幾何屬性以及拓?fù)浣Y(jié)構(gòu)來劃分搜索空間，提供精確的結(jié)果。

現(xiàn)有的通用Skyline查詢中[20]查詢點(diǎn)是確定的，即在Skyline查詢之前已確定了查詢點(diǎn)的位置。但當(dāng)查詢點(diǎn)不確定時，首先需要確定查詢點(diǎn)，然后才能進(jìn)行Skyline查詢。對于同類設(shè)施而言，不同的數(shù)據(jù)點(diǎn)對應(yīng)的查詢點(diǎn)可能是不同的，因此現(xiàn)有研究所采用的方法并不適用于這種查詢。基于上述問題，本文提出了結(jié)合非空間屬性的通用Skyline查詢處理技術(shù)。

3　基于R樹的最近鄰方法

3.1問題定義

假設(shè)P表示數(shù)據(jù)點(diǎn)集合，F(xiàn)表示所有設(shè)施集合，F(xiàn)i表示第i種類的設(shè)施集合，f表示某一個具體設(shè)施，設(shè)施種類共有m種。點(diǎn)p∈P與第i種設(shè)施的最近距離，使用p.di表示，也就是說p.di=min{Dist(p,f), f∈Fi}。如圖1所示，共有公交站臺和電影院兩種設(shè)施，因此每個餐館（數(shù)據(jù)點(diǎn)）可以映射到兩維的空間中。假設(shè)點(diǎn)p共有d維非空間屬性（非空間屬性是指與距離無關(guān)的屬性，例如餐館的價格、評級、服務(wù)質(zhì)量等），使用p.si表示點(diǎn)p的第i維非空間屬性，使用D來表示維度集合。

那么結(jié)合非空間屬性的通用Skyline查詢定義如下（假設(shè)取小為優(yōu)）。

定義1（靜態(tài)支配）P中的兩個點(diǎn)p和p′，如果對于?i∈D，都有p.si≤p′.si，并且?j∈D，使得p.sj

定義2（空間支配）P中的兩個點(diǎn)p和p′，對于F來講p空間支配p′，如果對于所有的類型i，都有p.di≤p′.di，并且存在一個設(shè)施類型 j，使得 p.dj< p′.dj成立，使用p?spap′表示。

定義3（完全支配）如果將p與設(shè)施集合的最近距離映射到新的距離空間中，結(jié)合非空間屬性，共有d+m維，使用D′來表示新的維度集合，使用p.vi表示新空間上的第i維的值。那么P中的兩個點(diǎn)p和p′，如果對于?i∈D′，都有p.vi≤p′.vi，并且?j∈D′，使得p.vj

結(jié)合非空間屬性的通用Skyline即由那些沒有被任何點(diǎn)完全支配的點(diǎn)組成。

3.2R樹與優(yōu)先權(quán)隊列

3.2.1R樹

因?yàn)镽樹使用廣泛，在處理多維數(shù)據(jù)查詢時具有較高的效率，所以采用R樹將空間數(shù)據(jù)建立索引，對m種設(shè)施的集合分別建立R樹。采用優(yōu)先權(quán)隊列的方法對數(shù)據(jù)進(jìn)行處理，獲取第一個較優(yōu)的點(diǎn)。

假設(shè)使用二維的數(shù)據(jù)構(gòu)建R樹，如圖2所示R樹的度為3。每一個中間記錄ei表示每一個對應(yīng)的下層節(jié)點(diǎn)的最小邊界矩形（minimum bounding rectangle, MBR），葉子節(jié)點(diǎn)表示的是一個數(shù)據(jù)點(diǎn)。根據(jù)歐式距離來計算距離，也就是說，在進(jìn)行最近鄰計算時最小距離mindist的計算由式（1）確定，假設(shè)查詢點(diǎn)為q的位置坐標(biāo)為(q1,q1,…,qd)：

數(shù)據(jù)點(diǎn)的mindist為查詢點(diǎn)與數(shù)據(jù)點(diǎn)的歐式距離，MBR的mindist為查詢點(diǎn)到該MBR的最小距離。

Fig.2　Example of R tree圖2　R樹舉例

3.2.2優(yōu)先權(quán)隊列

將數(shù)據(jù)點(diǎn)建立R樹索引后，在R樹上進(jìn)行查詢處理，這里引入優(yōu)先權(quán)隊列（priority queue），按照某個函數(shù)保證隊首元素始終是一個最優(yōu)的元素。如果隊首是一個數(shù)據(jù)點(diǎn)，那么取出的結(jié)果即為最優(yōu)的結(jié)果；如果隊首為一個中間記錄e，那么將e取出，并按照e的孩子節(jié)點(diǎn)的key值插入到隊列中。

定理1假設(shè)d(x,y)表示x與y的歐式距離，記錄e為R樹節(jié)點(diǎn)的最小邊界矩形MBR，令q為查詢點(diǎn)，那么對于子樹Tsubtree的任意記錄e，都有d(q,Tsubtree)≤d(q,e)。

證明 根據(jù)式（1），當(dāng)Tsubtree只有一層，即其記錄e對應(yīng)R樹的葉子節(jié)點(diǎn)為數(shù)據(jù)點(diǎn)，這時候d(q,Tsubtree)即為查詢點(diǎn)q與記錄e的距離，結(jié)論成立；當(dāng)子樹Tsubtree對應(yīng)的記錄為中間節(jié)點(diǎn)，利用反證法，假設(shè)d(q,Tsubtree)> d(q,e)，d(q,Tsubtree)相當(dāng)于查詢點(diǎn)q與Tsubtree對應(yīng)的MBR（使用MBRi表示）的最小距離，因?yàn)橛涗沞為Tsubtree的記錄，從而e在MBRi內(nèi)，又d(q,Tsubtree)>d(q,e)，所以查詢點(diǎn)到MBRi的最小距離并不是d(q,Tsubtree)，這與定義矛盾，因此d(q,Tsubtree)≤d(q,e)，結(jié)論成立?！?/p>

使用定理1，如果某一個記錄e′與查詢點(diǎn)的距離小于查詢點(diǎn)與某子樹的距離，即d(q,e)

3.3最近鄰方法

3.3.1全最近鄰算法

全最近鄰（all nearest neighbor，ANN）算法從數(shù)據(jù)集中返回距離當(dāng)前查詢點(diǎn)最近的一個點(diǎn)，即將每個數(shù)據(jù)點(diǎn)作為查詢點(diǎn)，查詢距離該查詢點(diǎn)最近的第i種類型的設(shè)施。將m種設(shè)施建立R*樹索引，從而獲取距離當(dāng)前查詢點(diǎn)p（某數(shù)據(jù)點(diǎn)）最近的m種設(shè)施f1,f2,…,fm，同時將 p與這些設(shè)施之間的距離映射到距離空間中，如圖1（b）所示。

3.3.2漸進(jìn)最近鄰算法

漸進(jìn)最近鄰（incremental nearest neighbor，INN）算法是指逐步獲取距離查詢點(diǎn)q最近的數(shù)據(jù)點(diǎn)，即當(dāng)已獲得x個最近鄰的點(diǎn)后，獲取第x+1個距離查詢點(diǎn)最近的點(diǎn)。假設(shè)使用R*樹為所有的數(shù)據(jù)點(diǎn)建立索引，使用優(yōu)先權(quán)隊列Q來維護(hù)R*樹的各個記錄，其中距離查詢點(diǎn)越近優(yōu)先權(quán)越高。首先將R*樹的根節(jié)點(diǎn)插入到隊列中，在每一次INN查詢時，都返回Q中最優(yōu)的一個元素。若最優(yōu)的元素是一個數(shù)據(jù)點(diǎn)，那么直接返回結(jié)果；若最優(yōu)的元素是一個中間節(jié)點(diǎn)，則將其彈出，同時將其孩子節(jié)點(diǎn)放入Q中，直到找到第一個數(shù)據(jù)點(diǎn)。

ANN算法與INN算法最大的不同點(diǎn)是，ANN算法只返回距離查詢點(diǎn)最近的一個數(shù)據(jù)點(diǎn)，而INN算法可以增量地返回距離查詢點(diǎn)第i近的數(shù)據(jù)點(diǎn)。如圖1所示，假設(shè)查詢點(diǎn)位于原點(diǎn)，首先進(jìn)行最近鄰查詢，然后進(jìn)行INN查詢，圖3是優(yōu)先權(quán)隊列Q中的內(nèi)容。首先將R樹的根節(jié)點(diǎn)的所有記錄插入到Q中，那么e6和e7進(jìn)入隊列，按照mindist排序，然后具有較小值的e7出隊，其孩子節(jié)點(diǎn)的記錄都插入到Q中。然后擴(kuò)展e3，在得到p9后，ANN算法停止；而INN算法若繼續(xù)執(zhí)行會得到下一個距離查詢點(diǎn)最近的數(shù)據(jù)點(diǎn)為p10，直到最后將所有的數(shù)據(jù)點(diǎn)都計算出來，INN算法輸出的結(jié)果按照與查詢點(diǎn)的距離依次遞增。

Fig.3　Nearest neighbor queries圖3　最近鄰查詢

3.4搜索導(dǎo)向

3.4.1數(shù)據(jù)點(diǎn)導(dǎo)向

對于每個數(shù)據(jù)點(diǎn)p，首先將p作為“查詢點(diǎn)”，查詢距離其最近的m種設(shè)施（查詢點(diǎn)），如圖1（a）所示，p1.dc和 p1.db可以使用最近鄰的方法從Fc={c1,c2,c3}中和Fb={b1,b2}中選擇，p1看作查詢點(diǎn)。這種導(dǎo)向的優(yōu)點(diǎn)是對于給定的數(shù)據(jù)點(diǎn)可以正確地返回距離其最近的設(shè)施點(diǎn)，并將其映射到距離空間上。然而這種方法需要對所有的數(shù)據(jù)點(diǎn)計算最近的距離，實(shí)際情況中并不是所有的數(shù)據(jù)點(diǎn)都需要用來計算Skyline結(jié)果，因此這種方法不能對數(shù)據(jù)集進(jìn)行裁剪，當(dāng)數(shù)據(jù)集較大時，對每個數(shù)據(jù)點(diǎn)進(jìn)行最近鄰查詢，然后計算Skyline，開銷較大。

3.4.2查詢點(diǎn)導(dǎo)向

與上述方法不同，查詢點(diǎn)導(dǎo)向的搜索將設(shè)施作為查詢點(diǎn)來計算。使用靜態(tài)Skyline結(jié)果來過濾掉一些不可能成為Skyline的點(diǎn)。這種方法可以對數(shù)據(jù)點(diǎn)集合進(jìn)行裁剪，減少數(shù)據(jù)點(diǎn)的訪問量。使用INN算法來逐步獲得距離查詢點(diǎn)最近的數(shù)據(jù)點(diǎn)，這里查詢點(diǎn)是某一類型的設(shè)施。給出幾個概念。

碰撞（hit）：假設(shè)對某一設(shè)施 f∈F，維護(hù)一個半徑fr，那么對于數(shù)據(jù)點(diǎn) p而言，如果Dist(p,f)≤fr，則稱p被 f碰撞。其中Dist(p,f)稱為p與 f的碰撞距離，使用Distp,f表示。

對于每種設(shè)施類型i，維護(hù)一個全局的半徑Ri, Ri表示對于i類型的設(shè)施而言當(dāng)前最大的碰撞距離，由式（2）決定：

在每一次迭代中，對i類型的設(shè)施找一個新的設(shè)施點(diǎn) f∈Fi來檢測新的碰撞，這樣Ri的增加是最小化的。如圖4所示，第一次迭代計算距離b2最近的數(shù)據(jù)點(diǎn)，第二次迭代計算距離b1最近的數(shù)據(jù)點(diǎn)，將此時碰撞距離設(shè)置為Ri，因?yàn)榇藭rDist(b1,p7)>Dist(b2,p8)。因此Ri在搜索中是非遞減的，根據(jù)其單調(diào)性，當(dāng)數(shù)據(jù)點(diǎn)p被i類型的設(shè)施 f第一次碰撞時，可以設(shè)置為p.di=Distp,f，圖4中第一次迭代可以計算出 p8.db和p1.dc。需要注意的是，一個數(shù)據(jù)點(diǎn)可能被相同類型的設(shè)施多次碰撞，這樣的碰撞稱為冗余碰撞，如圖4中相對于c1的碰撞p1，因?yàn)樗呀?jīng)在第一次迭代中被c2碰撞。

根據(jù)以上分析，首先計算靜態(tài)Skyline結(jié)果SKsta，然后計算SKsta中與每一種類型設(shè)施的最大距離，使用定理2對數(shù)據(jù)集進(jìn)行裁剪。

定理2SKsta中的點(diǎn)距離i類設(shè)施的最遠(yuǎn)距離為di.max，i從1到m，對于任何一個點(diǎn)pt，如果對任意的i，i從1到m，pt與i類設(shè)施的最近距離大于等于di.max，那么pt不會屬于最終Skyline。

證明 顯然 pt?SKsta，因此?sp∈SKsta，使得sp能夠靜態(tài)支配pt。因?yàn)镾Ksta中的點(diǎn)距離i類設(shè)施的最遠(yuǎn)距離為di.max，所有sp距離i類設(shè)施的距離小于等于di.max。又因?yàn)閜t與i類設(shè)施的最近距離大于等于di.max，所以有sp空間支配 pt。因此，pt被sp完全支配，其不屬于SK。□

Fig.4　Query point oriented search圖4　查詢點(diǎn)導(dǎo)向的搜索

如圖4所示，假設(shè)靜態(tài)Skyline結(jié)果SKsta={p3,p8}，這兩個點(diǎn)距離c設(shè)施和b設(shè)施的最大距離分別為p3.dc和 p3.db。在第4次迭代過程后，獲得了所有小于這兩個閾值的碰撞，而那些尚未被任何一種設(shè)施碰撞過的點(diǎn) p4、p5和 p6，因?yàn)槠渑cc設(shè)施和b設(shè)施的最近距離都大于閾值，所以直接可以將p4、p5和p6裁剪，這些點(diǎn)不會屬于最終Skyline結(jié)果。

除了可以對數(shù)據(jù)集進(jìn)行裁剪，查詢點(diǎn)導(dǎo)向的搜索的另一個好處是在INN查詢中碰撞距離的計算代價較小。因?yàn)镮NN算法可以通過連續(xù)地維護(hù)優(yōu)先權(quán)隊列來分享計算，所以平均了計算代價。將在下一節(jié)討論基于INN的Skyline查詢處理算法。

4　基于最近鄰的Skyline查詢算法

4.1基于ANN的Skyline查詢算法及其擴(kuò)展算法

當(dāng)所有的數(shù)據(jù)點(diǎn)都能夠映射到距離空間中時，結(jié)合非空間屬性，便可以采用已有的Skyline查詢處理技術(shù)來處理問題。一種直接的方法是首先計算所有查詢點(diǎn)與設(shè)施集合的最小距離，然后映射到距離空間中，之后再采用已有的Skyline算法來計算。這里采用前一節(jié)所述的全最近鄰查詢算法來計算數(shù)據(jù)點(diǎn)相對某種設(shè)施集合Fi的最近距離，稱之為基于ANN的Skyline查詢算法（Skyline query algorithm based on ANN,SQ_ANN），在不引起混淆的情況下簡記為ANN。以下描述了基于ANN的Skyline查詢算法。

算法1 SQ_ANN算法

1.For每個數(shù)據(jù)點(diǎn)p

2.for每一種設(shè)施集合Fi

3.使用ANN方法計算數(shù)據(jù)點(diǎn)p相對于Fi的最近距離p.di；

4.將p.di映射到距離空間上；

5.end for

6.end for

7.采用已有的Skyline查詢算法來對距離空間上的數(shù)據(jù)以及非空間屬性數(shù)據(jù)計算Skyline；

考慮到當(dāng)靜態(tài)Skyline結(jié)果較大時可以有效地減少進(jìn)行全最近鄰計算的數(shù)據(jù)點(diǎn)的個數(shù)，提出了基于ANN的Skyline查詢的改進(jìn)方法，稱之為ex-ANN?？梢韵扔嬎沆o態(tài)Skyline結(jié)果，然后將這部分結(jié)果放入Skyline結(jié)果，從而減少需要進(jìn)行最近鄰設(shè)施計算的數(shù)據(jù)集合大小。這種方法對于靜態(tài)Skyline結(jié)果集較大時比較有效，因?yàn)橥ㄟ^計算SKsta便可以對數(shù)據(jù)集進(jìn)行裁剪，并且SKsta肯定會成為最終Skyline結(jié)果，所以不需要對這部分?jǐn)?shù)據(jù)進(jìn)行全最近鄰計算，從而節(jié)省了開銷。

4.2基于INN的Skyline查詢算法

盡管ex-ANN算法在靜態(tài)Skyline結(jié)果集較大時可以很好地處理問題，但是多數(shù)情況下，靜態(tài)Skyline結(jié)果與整個數(shù)據(jù)集比起來所占比例并不大。因此根據(jù)上一節(jié)討論，結(jié)合數(shù)據(jù)點(diǎn)導(dǎo)向以及查詢點(diǎn)導(dǎo)向的優(yōu)缺點(diǎn)，將這兩種搜索導(dǎo)向方法結(jié)合起來提出了一個高效的基于INN的Skyline查詢算法（Skyline query algorithm based on INN，SQ_INN），在不引起混淆的情況下簡記為INN。假設(shè)數(shù)據(jù)點(diǎn)集合使用R樹建立索引，用RP表示，所有類型的設(shè)施集合也使用R樹建立索引，假設(shè)i類型的設(shè)施使用RFi表示。

算法可以分成4個階段，如下所示：

算法2 SQ_INN算法

//階段1閾值計算

1.針對數(shù)據(jù)集的非空間屬性計算靜態(tài)Skyline結(jié)果SKsta；

2.for每一個pt∈SKsta

3.for每一種設(shè)施集合Fi

4.獲取pt與設(shè)施集合最近鄰的最遠(yuǎn)距離di.max；

5.end for

//階段2數(shù)據(jù)集裁剪

6.for每一種設(shè)施集合Fi

7.whileRi

8.p為相對Fi最近的數(shù)據(jù)點(diǎn)；

9.if對p的碰撞不是冗余碰撞

10.p.di=Ri，將p插入到候選集C中；

11.end while

12.end for

//階段3補(bǔ)全距離屬性

13.for每一個pt∈C

14.for每一種設(shè)施集合Fi

15.ifpt.di未設(shè)置

16.計算pt相對于Fi的最近鄰；

17.end for

//階段4

18.采用已有的Skyline查詢算法來對距離空間上的數(shù)據(jù)計算Skyline；

階段1對數(shù)據(jù)集的非空間屬性計算靜態(tài)Skyline結(jié)果SKsta，然后計算SKsta中與第i種類型設(shè)施最近鄰的最大距離di.max，獲取m個最大距離后作為閾值進(jìn)入階段2。

階段2因?yàn)樵趯?shí)際應(yīng)用中，查詢點(diǎn)的個數(shù)往往遠(yuǎn)遠(yuǎn)少于數(shù)據(jù)點(diǎn)的個數(shù)，所以采用查詢點(diǎn)導(dǎo)向的搜索方法來計算數(shù)據(jù)點(diǎn)的距離并且裁剪一些數(shù)據(jù)點(diǎn)，當(dāng)?shù)竭_(dá)閾值時，在該設(shè)施集合的搜索結(jié)束。為每一個設(shè)施 f維護(hù)一個優(yōu)先權(quán)隊列Qf來進(jìn)行INN查詢，為每一種類型的設(shè)施i維護(hù)一個優(yōu)先權(quán)隊列QFi來記錄對于Fi而言最近的數(shù)據(jù)點(diǎn)，QFi中具有最小距離的元素具有最大的優(yōu)先權(quán)。首先對Fi中所有的設(shè)施 f調(diào)用INN查詢，獲取QFi隊首的數(shù)據(jù)點(diǎn)p，然后將其彈出隊列，然后計算下一個距離最近的數(shù)據(jù)點(diǎn)p2，將其插入隊列。如果當(dāng)前的碰撞并非冗余碰撞，則，即數(shù)據(jù)點(diǎn)p相對i類設(shè)施的最近距離是當(dāng)前的碰撞距離，此時的碰撞距離即Ri。當(dāng)Ri≥di.max時，迭代結(jié)束，此時那些至少被碰撞過一次的數(shù)據(jù)點(diǎn)進(jìn)入候選集，從而裁剪掉那些沒有被碰撞過的點(diǎn)。

如圖4所示，假設(shè)靜態(tài)Skyline結(jié)果SKsta={p3,p8}，這兩個點(diǎn)距離c設(shè)施和b設(shè)施的最大距離分別為p3.dc和p3.db。第一輪迭代，對設(shè)施b，首先獲得p8，p8的碰撞非冗余碰撞，因此設(shè)置 p8.db；對設(shè)施c，首先獲得p1，因?yàn)槠湟卜侨哂嗯鲎玻栽O(shè)置p1.dc，這兩個點(diǎn)都插入到候選集中。第四輪迭代后，下一輪迭代Rc和Rb將會超過 p3.dc和 p3.db，因此迭代結(jié)束。這時沒有被任何設(shè)施碰撞的點(diǎn)被裁剪掉，階段2結(jié)束，此時候選集中C的點(diǎn)為{p1,p2,p3,p7,p8}。

階段3對候選集中的數(shù)據(jù)點(diǎn)采用數(shù)據(jù)點(diǎn)導(dǎo)向的搜索方法進(jìn)行距離計算。如在階段2結(jié)束后，p1、p2和p7僅被一種設(shè)施類型碰撞，需要對這3個點(diǎn)進(jìn)行相對其他設(shè)施類型的最近鄰計算，從而獲得p1.db、p2.db和p7.dc，當(dāng)所有候選集中的數(shù)據(jù)點(diǎn)的距離都計算結(jié)束后，階段3結(jié)束。

階段4對候選集中映射到距離空間中的點(diǎn)結(jié)合非空間屬性采用已有的Skyline查詢算法來計算最終Skyline結(jié)果。

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

在實(shí)驗(yàn)中，利用生成的數(shù)據(jù)集對本文提出的基于ANN的Skyline查詢算法及其擴(kuò)展算法，以及基于INN的Skyline查詢算法進(jìn)行比較和分析。所有算法采用Visual C++2010實(shí)現(xiàn)，在3.3 GHz Intel Core i3-2120 CPU和3 GB內(nèi)存系統(tǒng)上執(zhí)行。

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

采用文獻(xiàn)[3]中的方法生成空間屬性和非空間屬性獨(dú)立分布、相關(guān)分布、反相關(guān)分布的合成數(shù)據(jù)集。針對數(shù)據(jù)點(diǎn)集合和設(shè)施集合，首先生成兩維的獨(dú)立分布數(shù)據(jù)作為各個集合中點(diǎn)的空間位置，數(shù)據(jù)各個維度的范圍是[0,1]，空間位置的范圍是1×1。比較基于ANN的算法SQ_ANN及其擴(kuò)展算法ex-ANN，以及基于INN的算法SQ_INN的執(zhí)行效率，通過算法運(yùn)行時間、I/O次數(shù)來比較算法的性能，同時比較了Skyline結(jié)果集合的大小。實(shí)驗(yàn)主要分析非空間屬性維度、數(shù)據(jù)集大小、設(shè)施種類以及每種設(shè)施數(shù)量大小改變情況下的算法性能，表1為主要參數(shù)的默認(rèn)值及其變化范圍。采用R*樹對數(shù)據(jù)集合和設(shè)施集合構(gòu)建索引，索引構(gòu)建數(shù)據(jù)頁大小都設(shè)置為1 KB。

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

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

由于在進(jìn)行結(jié)合非空間屬性的通用Skyline查詢時，主要的時間以及I/O消耗發(fā)生在最近鄰計算階段，在進(jìn)行實(shí)驗(yàn)對比時，在數(shù)據(jù)點(diǎn)的非空間屬性維度不變的情況下，非空間屬性的數(shù)據(jù)分布相關(guān)、獨(dú)立、反相關(guān)對算法的執(zhí)行效率影響不大，因此只采用獨(dú)立分布數(shù)據(jù)來進(jìn)行實(shí)驗(yàn)比較。在進(jìn)行非空間屬性維度對算法性能影響的實(shí)驗(yàn)時，考慮了3種分布：相關(guān)分布、反相關(guān)分布、獨(dú)立分布（靜態(tài)屬性值從0到1變化）對算法性能的影響。

實(shí)驗(yàn)通過比較執(zhí)行時間、I/O次數(shù)對比了SQ_ANN算法、ex-ANN算法與SQ_INN算法的性能。同時比較了不同情況下Skyline結(jié)果的大小。實(shí)驗(yàn)表明，SQ_INN算法比SQ_ANN算法及其擴(kuò)展算法無論在執(zhí)行時間還是I/O代價上，在處理結(jié)合非空間屬性的通用Skyline查詢時都較優(yōu)。

5.2.1非空間屬性維度對算法性能的影響

圖5～圖7比較了在非空間屬性維度變化的情況下對算法性能的影響，圖中（a）、（b）和（c）分別表示非空間屬性服從相關(guān)分布、反相關(guān)分布和獨(dú)立分布。圖5表示I/O次數(shù)，圖6表示CPU執(zhí)行時間，圖7表示Skyline大小隨著每種設(shè)施數(shù)量變化產(chǎn)生的影響。從圖中可以看出，INN算法在各個方面要明顯優(yōu)于ANN及其擴(kuò)展算法。從圖5可以看出，隨著非空間屬性維度增大，I/O次數(shù)對于ANN和INN算法并沒有明顯影響。這主要是因?yàn)樵谶M(jìn)行全最近鄰查詢時，并不涉及非空間屬性，所以其I/O消耗主要是進(jìn)行最近鄰查詢時產(chǎn)生的。從圖6可以看出，隨著非空間屬性維度增大，對于反相關(guān)分布，CPU執(zhí)行時間都隨之增加，這主要是因?yàn)榉强臻g屬性維度的增加使得兩點(diǎn)之間的支配性代價增加，所以計算Skyline時產(chǎn)生了更多的時間消耗。從圖7中可以看出，對于反相關(guān)分布和獨(dú)立分布，靜態(tài)Skyline的大小明顯增加，因此ex-ANN算法要優(yōu)于ANN算法。基于上述分析，隨著維度增加，兩兩點(diǎn)間的支配性概率降低，非空間屬性維度對最終Skyline結(jié)果影響較大。

Fig.5　I/O number on non-spatial dimension圖5　非空間屬性維度對I/O次數(shù)的影響

Fig.6　CPU time on non-spatial dimension圖6 非空間屬性維度對CPU執(zhí)行時間的影響

Fig.7　Skyline set on non-spatial dimension圖7　非空間屬性維度對Skyline結(jié)果集的影響

5.2.2數(shù)據(jù)集合大小對算法性能的影響

圖8比較了在數(shù)據(jù)集合大小變化的情況下對算法性能的影響，圖中（a）、（b）和（c）分別表示I/O次數(shù)、CPU執(zhí)行時間以及Skyline大小隨著數(shù)據(jù)集大小變化產(chǎn)生的影響。從圖中可以看出，INN算法在各個方面要明顯優(yōu)于ANN及其擴(kuò)展算法。圖8（a）和圖8（b）表明，隨著數(shù)據(jù)集增大，I/O次數(shù)和CPU執(zhí)行時間都隨之增加。這主要是因?yàn)閷τ贏NN查詢，隨著數(shù)據(jù)集的增大，其對于每一種類型的設(shè)施進(jìn)行最近鄰查詢時所消耗的I/O和CPU執(zhí)行時間成正比，所以ANN算法所消耗的時間與I/O次數(shù)隨著數(shù)據(jù)集增大明顯增加。將距離映射到二維的距離空間中加上非空間屬性進(jìn)行Skyline計算。從圖8（c）中可以看出，靜態(tài)Skyline的大小與整個數(shù)據(jù)集相比，數(shù)量可以忽略，因此對于ex-ANN算法與ANN算法基本性能相等。

5.2.3設(shè)施的種類對算法性能的影響

圖9比較了在設(shè)施種類變化的情況下對算法性能的影響，圖中（a）、（b）和（c）分別表示I/O次數(shù)、CPU執(zhí)行時間以及Skyline大小隨著設(shè)施種類變化產(chǎn)生的影響。從圖中可以看出，INN算法在各個方面要明顯優(yōu)于ANN及其擴(kuò)展算法。圖9（a）和圖9（b）表明，隨著數(shù)據(jù)集增大，I/O次數(shù)和CPU執(zhí)行時間都隨之增加。這主要是因?yàn)閷τ贏NN查詢，雖然數(shù)據(jù)集大小相同，但是相當(dāng)于對n種設(shè)施都需要進(jìn)行一次最近鄰查詢，I/O次數(shù)和CPU執(zhí)行時間與設(shè)施種類成正比，所以ANN算法所消耗的時間與I/O次數(shù)隨著設(shè)施種類增加明顯增大。從圖9（c）中可以看出，靜態(tài)Skyline的大小與整個數(shù)據(jù)集相比，數(shù)量可以忽略，因此對于ex-ANN算法與ANN算法基本性能相等。將距離映射到n維的距離空間中加上非空間屬性進(jìn)行Skyline計算，Skyline結(jié)果大小隨著設(shè)施種類的增加顯著增大。這主要是因?yàn)殡S著維度的增加，各個點(diǎn)之間被支配的概率降低，所以Skyline結(jié)果集也隨之增加。

Fig.8　Algorithm performance with different sizes of datasets圖8　數(shù)據(jù)集大小對算法性能的影響

Fig.9　Algorithm performance with different kinds of facilities圖9　設(shè)施種類對算法性能的影響

5.2.4每種設(shè)施數(shù)量對算法性能的影響

圖10比較了在每種設(shè)施數(shù)量變化的情況下對算法性能的影響，圖中（a）、（b）和（c）分別表示I/O次數(shù)、CPU執(zhí)行時間以及Skyline大小隨著每種設(shè)施數(shù)量變化產(chǎn)生的影響。從圖中可以看出，INN算法在各個方面要明顯優(yōu)于ANN及其擴(kuò)展算法。圖10（a）和圖10（b）表明，隨著每種設(shè)施數(shù)量增大，I/O次數(shù)和CPU執(zhí)行時間都隨之增加，這主要是因?yàn)閷τ贏NN查詢，每種設(shè)施種類增加，所以對于設(shè)施集合所建立的R樹節(jié)點(diǎn)個數(shù)也會有所增加，在進(jìn)行最近鄰查詢的時候，對設(shè)施進(jìn)行一次最近鄰查詢所消耗的I/O次數(shù)和CPU執(zhí)行時間增加，當(dāng)數(shù)據(jù)集合大小不變，設(shè)施種類不變時，總的I/O次數(shù)與執(zhí)行時間隨之變大。因此ANN算法所消耗的時間與I/O次數(shù)隨著設(shè)施種類增加明顯增大。從圖10（c）中可以看出，靜態(tài)Skyline的大小與整個數(shù)據(jù)集相比，數(shù)量可以忽略，因此對于ex-ANN算法與ANN算法基本性能相等。每種設(shè)施數(shù)量并不影響最終Skyline的計算，因此對Skyline結(jié)果大小也沒有明顯影響。

Fig.10　Algorithm performance with different numbers of facilities圖10　每種設(shè)施數(shù)量對算法性能的影響

6　總結(jié)

本文研究了結(jié)合非空間屬性的通用Skyline查詢處理技術(shù)，從設(shè)施集合中選擇距離某數(shù)據(jù)點(diǎn)最近的設(shè)施，并將其與該數(shù)據(jù)點(diǎn)之間的距離映射到距離空間上，然后在新的距離空間中進(jìn)行Skyline查詢。采用R樹索引結(jié)構(gòu)對數(shù)據(jù)集建立索引，根據(jù)數(shù)據(jù)點(diǎn)導(dǎo)向和查詢點(diǎn)導(dǎo)向兩種不同的搜索導(dǎo)向的優(yōu)缺點(diǎn)，提出了SQ_ANN算法及其擴(kuò)展算法，以及SQ_INN算法。SQ_INN算法主要是通過過濾的方法來對數(shù)據(jù)集進(jìn)行剪枝，減少I/O次數(shù)。理論和實(shí)驗(yàn)表明SQ_INN算法無論在CPU執(zhí)行時間還是I/O次數(shù)上都優(yōu)于SQ_ANN算法。

[1]Sharifzadeh M,Shahabi C.The spatial skyline queries[C]// Proceedings of the 32nd International Conference on Very Large Data Bases，Seoul,Korea,Sep 12-15,2006:751-762.

[2]Deng Ke,Zhou Xiaofang,Shen Hengtao.Multi-source skyline query processing in road networks[C]//Proceedings of the 23rd IEEE International Conference on Data Engineering,Istanbul,Turkey,Apr 15-20,2007.Piscataway,USA: IEEE,2007:796-805.

[3]Borzsonyi S,Kossmann D,Stocker K.The skyline operator [C]//Proceedings of the 17th International Conference on Data Engineering,Heidelberg,Germany,Apr 2-6,2001.Piscataway, USA:IEEE,2001:421-430.

[4]Tan K L,Eng P K,Ooi B C.Efficient progressive skyline computation[C]//Proceedings of the 27th International Conference on Very Large Data Bases,Roma,Italy,Sep 11-14, 2001:301-310.

[5]Chomicki J,Godfrey P,Gryz J,et al.Skyline with presorting [C]//Proceedings of the 19th International Conference on Data Engineering,Bangalore,India,Mar 5-8,2003.Piscataway,USA:IEEE,2003:717-719.

[6]Godfrey P,Shipley R,Gryz J.Maximal vector computation in large data sets[C]//Proceedings of the 31st International Conference on Very Large Data Bases,Trondheim,Norway, Aug 30-Sep 2,2005:229-240.

[7]Kossmann D,Ramsak F,Rost S.Shooting stars in the sky:an online algorithm for skyline queries[C]//Proceedings of the 28th International Conference on Very Large Data Bases, HongKong,China,Aug 20-23,2002:275-286.

[8]Papadias D,Tao Yufei,Fu G,et al.Progressive skyline computation in database systems[J].ACM Transactions on Database Systems,2005,30(1):41-82.

[9]Papadias D,Tao Yufei,Fu G,et al.An optimal and progressive algorithm for skyline queries[C]//Proceedings of the2003 ACM SIGMOD International Conference on Management of Data,San Diego,USA,Jun 9-12,2003.New York, USA:ACM,2003:467-478.

[10]Wu Ping,Zhang Caijie,Feng Ying,et al.Parallelizing skyline queries for scalable distribution[C]//LNCS 3896:Proceedings of the 10th International Conference on Extending Database Technology,Munich,Germany,Mar 26-31,2006. Berlin,Heidelberg:Springer,2006:112-130.

[11]Chen Lijiang,Cui Bin,Lu Hua,et al.iSky:efficient and progressive skyline computing in a structured P2P network [C]//Proceedings of the 28th International Conference on Distributed Computing Systems,Beijing,China,Jun 17-20, 2008.Piscataway,USA:IEEE,2008:160-167.

[12]Tao Yufei,Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(3):377-391.

[13]Pei Jian,Jiang Bin,Lin Xuemin,et al.Probabilistic skylines on uncertain data[C]//Proceedings of the 33rd International Conference on Very Large Data Bases,Vienna,Austria,Sep 23-27,2007:15-26.

[14]Yoon K,Chung Y D,SangKeun L E E.In-network processing for skyline queries in sensor networks[J].IEICE Transactions on Communications,2007,90(12):3452-3459.

[15]Su I F,Chung Y C,Lee C,et al.Efficient skyline query processing in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2010,70(6):680-698.

[16]Son W,Lee M W,Ahn H K,et al.Spatial skyline queries: an efficient geometric algorithm[C]//LNCS 5644:Proceedings of the 11th International Symposium on Spatial and Temporal Databases,Aalborg,Denmark,Jul 8-10,2009.Berlin,Heidelberg:Springer,2009:247-264.

[17]Huang Zhiyong,Lu Hua,Ooi B C,et al.Continuous skyline queries for moving objects[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(12):1645-1658.

[18]Cheema M A,Lin Xuemin,Zhang Wenjie,et al.A safe zone based approach for monitoring moving skyline queries [C]//Proceedings of the 16th International Conference on Extending Database Technology,Genoa,Italy,Mar 18-22, 2013.New York,USA:ACM,2013:275-286.

[19]Yoon S H,Shahabi C.Distributed spatial skyline query processing in wireless sensor networks[C]//Proceedings of the International Workshop on Sensor Webs,Databases,and Mining in Networked Sensing Systems in Conjunction with International Conference on Networked Sensing Systems, 2009.

[20]Lin Qianlu,Zhang Ying,Zhang Wenjie,et al.Efficient general spatial skyline computation[J].World Wide Web,2013, 16(3):247-270.

WANG Haixiang was born in 1989.She received the M.S.degree from Nanjing University of Aeronautics and Astronautics in 2015.Her research interests include Skyline computation and perceptive data management,etc.

王海翔（1989—），女，江蘇連云港人，2015年于南京航空航天大學(xué)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)镾kyline計算，感知數(shù)據(jù)管理等。

ZHENG Jiping was born in 1979.He received the Ph.D.degree from Nanjing University of Aeronautics and Astronautics in 2007.From 2007 to 2009,he was a post-doctoral researcher at Department of Computer Science of Tsinghua University.From 2016 to 2017,he is a CSC visiting scholar at School of Computer Science and Engineering of University of New South Wales.Now he is an associate professor at Nanjing University of Aeronautics and Astronautics,and the senior member of CCF.His research interests include Skyline computation,perceptive data management,computational geometry and Monte Carlo methods,etc.

鄭吉平（1979—），男，江蘇南京人，2007年于南京航空航天大學(xué)獲得工學(xué)博士學(xué)位，2007—2009年在清華大學(xué)計算機(jī)系從事博士后研究工作，2016—2017年在澳大利亞新南威爾士大學(xué)計算機(jī)科學(xué)與工程學(xué)院從事國家公派訪問學(xué)者工作，現(xiàn)為南京航空航天大學(xué)副教授，CCF高級會員，主要研究領(lǐng)域?yàn)镾kyline計算，感知數(shù)據(jù)管理，計算幾何，蒙特卡羅方法等。

WANG Yongge was born in 1989.He is an M.S.candidate at Nanjing University of Aeronautics and Astronautics. His research interests include probabilistic Skyline computation and perceptive data management,etc.

王永閣（1989—），男，江蘇徐州人，南京航空航天大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)楦怕蔛kyline計算，感知數(shù)據(jù)管理等。

General Skyline Query Processing Technology Combiningwith Non-spatial Attributes?

WANG Haixiang1,ZHENG Jiping1,2,3+,WANG Yongge1
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China 2.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China 3.School of Computer Science and Engineering,University of New South Wales,Sydney,NSW 2052,Australia +Corresponding author:E-mail:zhjcs@nuaa.edu.cn

As one of the important methods for multi-criteria decision making problems,the Skyline query processing technologies have been widely studied in many applications.This paper proposes the general Skyline query processing technology combining with non-spatial attributes while R tree is adopted to index the facility set and the dataset.Two algorithms are provided to compute the Skyline results.The first algorithm is the extension of Skyline query algorithm based on all nearest neighbor method,which cuts off part of the dataset by computing the static Skyline results.The second algorithm is based on incremental nearest neighbor method,which utilizes the facility oriented searching method. The algorithm calculates the farthest distances between the static Skyline results and each type of facilities.The distances are set to bound thresholds so as to cut off data points which are farther than them.For the left points,data ori-ented search method is used to compute the nearest facilities of all types.After that,the distances between the data points and the facilities are mapped to the multi-dimensional distance space so as to compute the Skyline result combining with non-spatial attributes.The experimental results show that for the second algorithm the number of I/Os and CPU time are greatly reduced thus improves the computational efficiency.

general Skyline queries;R-tree index;non-spatial attributes;nearest neighbor

2015-06,Accepted 2015-10.

10.3778/j.issn.1673-9418.1506091

A

TP392

*The Natural Science Foundation of Jiangsu Province under Grant No.BK2014086(江蘇省自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.NS2015095(中央高校基本科研業(yè)務(wù)費(fèi)專項資金);the Foundation of Graduate Innovation Center in NUAAunder Grant No.KFJJ201461(南京航空航天大學(xué)研究生創(chuàng)新基地開放基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.018.html