結合非空間屬性的通用Skyline查詢處理技術*

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

1.南京航空航天大學 計算機科學與技術學院，南京 211106 2.南京大學 計算機軟件新技術國家重點實驗室，南京 210023 3.新南威爾士大學 計算機科學與工程學院，悉尼，澳大利亞 NSW 2052

結合非空間屬性的通用Skyline查詢處理技術*

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

1.南京航空航天大學 計算機科學與技術學院，南京 211106 2.南京大學 計算機軟件新技術國家重點實驗室，南京 210023 3.新南威爾士大學 計算機科學與工程學院，悉尼，澳大利亞 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查詢作為多目標決策的重要手段之一，近年來在各個領域得到廣泛的應用。提出了結合非空間屬性的通用Skyline查詢處理技術，采用R樹對設施集及數據集建立索引，并提出了兩種方法來計算Skyline。第一種是基于全最近鄰算法的擴展，通過計算靜態Skyline結果來裁剪部分數據集。另一種是基于漸進最近鄰的算法，采用查詢點導向的搜索方法，利用靜態Skyline結果計算與每一類設施最遠的距離，將其作為邊界閾值對數據點集進行裁剪，采用數據點導向的搜索方法，為裁剪后的每一個數據點計算距其最近的設施，并將數據點與設施的距離映射到多維距離空間中，結合非空間屬性進行Skyline計算。實驗結果表明，第二種方法減少了I/O次數，降低了CPU執行時間，提高了計算效率。

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

1　引言

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

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

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

此外，通用Skyline查詢這類問題看成多源Skyline查詢問題，對于多源Skyline查詢已有一些研究，如文獻[1-2]等，但這些研究中考慮的查詢點是確定的，即在Skyline查詢之前已確定了查詢點的位置，因此可以利用一些空間幾何的特性來處理這一類問題。但當查詢點不確定時，首先需要確定查詢點，然后才能進行Skyline查詢。因為對于同類設施而言，不同的數據點對應的查詢點可能是不同的，所以現有研究所采用的方法并不適用于這種查詢。針對以上問題，本文提出了結合非空間屬性的通用Skyline查詢處理技術。

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

2　相關工作

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

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

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

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

3　基于R樹的最近鄰方法

3.1問題定義

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

那么結合非空間屬性的通用Skyline查詢定義如下（假設取小為優）。

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

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

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

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

3.2R樹與優先權隊列

3.2.1R樹

因為R樹使用廣泛，在處理多維數據查詢時具有較高的效率，所以采用R樹將空間數據建立索引，對m種設施的集合分別建立R樹。采用優先權隊列的方法對數據進行處理，獲取第一個較優的點。

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

數據點的mindist為查詢點與數據點的歐式距離，MBR的mindist為查詢點到該MBR的最小距離。

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

3.2.2優先權隊列

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

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

證明 根據式（1），當Tsubtree只有一層，即其記錄e對應R樹的葉子節點為數據點，這時候d(q,Tsubtree)即為查詢點q與記錄e的距離，結論成立；當子樹Tsubtree對應的記錄為中間節點，利用反證法，假設d(q,Tsubtree)> d(q,e)，d(q,Tsubtree)相當于查詢點q與Tsubtree對應的MBR（使用MBRi表示）的最小距離，因為記錄e為Tsubtree的記錄，從而e在MBRi內，又d(q,Tsubtree)>d(q,e)，所以查詢點到MBRi的最小距離并不是d(q,Tsubtree)，這與定義矛盾，因此d(q,Tsubtree)≤d(q,e)，結論成立。□

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

3.3最近鄰方法

3.3.1全最近鄰算法

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

3.3.2漸進最近鄰算法

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

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

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

3.4搜索導向

3.4.1數據點導向

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

3.4.2查詢點導向

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

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

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

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

根據以上分析，首先計算靜態Skyline結果SKsta，然后計算SKsta中與每一種類型設施的最大距離，使用定理2對數據集進行裁剪。

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

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

Fig.4　Query point oriented search圖4　查詢點導向的搜索

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

除了可以對數據集進行裁剪，查詢點導向的搜索的另一個好處是在INN查詢中碰撞距離的計算代價較小。因為INN算法可以通過連續地維護優先權隊列來分享計算，所以平均了計算代價。將在下一節討論基于INN的Skyline查詢處理算法。

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

4.1基于ANN的Skyline查詢算法及其擴展算法

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

算法1 SQ_ANN算法

1.For每個數據點p

2.for每一種設施集合Fi

3.使用ANN方法計算數據點p相對于Fi的最近距離p.di；

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

5.end for

6.end for

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

考慮到當靜態Skyline結果較大時可以有效地減少進行全最近鄰計算的數據點的個數，提出了基于ANN的Skyline查詢的改進方法，稱之為ex-ANN。可以先計算靜態Skyline結果，然后將這部分結果放入Skyline結果，從而減少需要進行最近鄰設施計算的數據集合大小。這種方法對于靜態Skyline結果集較大時比較有效，因為通過計算SKsta便可以對數據集進行裁剪，并且SKsta肯定會成為最終Skyline結果，所以不需要對這部分數據進行全最近鄰計算，從而節省了開銷。

4.2基于INN的Skyline查詢算法

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

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

算法2 SQ_INN算法

//階段1閾值計算

1.針對數據集的非空間屬性計算靜態Skyline結果SKsta；

2.for每一個pt∈SKsta

3.for每一種設施集合Fi

4.獲取pt與設施集合最近鄰的最遠距離di.max；

5.end for

//階段2數據集裁剪

6.for每一種設施集合Fi

7.whileRi

8.p為相對Fi最近的數據點；

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

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

11.end while

12.end for

//階段3補全距離屬性

13.for每一個pt∈C

14.for每一種設施集合Fi

15.ifpt.di未設置

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

17.end for

//階段4

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

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

階段2因為在實際應用中，查詢點的個數往往遠遠少于數據點的個數，所以采用查詢點導向的搜索方法來計算數據點的距離并且裁剪一些數據點，當到達閾值時，在該設施集合的搜索結束。為每一個設施 f維護一個優先權隊列Qf來進行INN查詢，為每一種類型的設施i維護一個優先權隊列QFi來記錄對于Fi而言最近的數據點，QFi中具有最小距離的元素具有最大的優先權。首先對Fi中所有的設施 f調用INN查詢，獲取QFi隊首的數據點p，然后將其彈出隊列，然后計算下一個距離最近的數據點p2，將其插入隊列。如果當前的碰撞并非冗余碰撞，則，即數據點p相對i類設施的最近距離是當前的碰撞距離，此時的碰撞距離即Ri。當Ri≥di.max時，迭代結束，此時那些至少被碰撞過一次的數據點進入候選集，從而裁剪掉那些沒有被碰撞過的點。

如圖4所示，假設靜態Skyline結果SKsta={p3,p8}，這兩個點距離c設施和b設施的最大距離分別為p3.dc和p3.db。第一輪迭代，對設施b，首先獲得p8，p8的碰撞非冗余碰撞，因此設置 p8.db；對設施c，首先獲得p1，因為其也非冗余碰撞，所以設置p1.dc，這兩個點都插入到候選集中。第四輪迭代后，下一輪迭代Rc和Rb將會超過 p3.dc和 p3.db，因此迭代結束。這時沒有被任何設施碰撞的點被裁剪掉，階段2結束，此時候選集中C的點為{p1,p2,p3,p7,p8}。

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

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

5　實驗測評

在實驗中，利用生成的數據集對本文提出的基于ANN的Skyline查詢算法及其擴展算法，以及基于INN的Skyline查詢算法進行比較和分析。所有算法采用Visual C++2010實現，在3.3 GHz Intel Core i3-2120 CPU和3 GB內存系統上執行。

5.1實驗設置

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

Table 1　Experiment parameters表1　實驗參數

5.2實驗結果

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

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

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

圖5～圖7比較了在非空間屬性維度變化的情況下對算法性能的影響，圖中（a）、（b）和（c）分別表示非空間屬性服從相關分布、反相關分布和獨立分布。圖5表示I/O次數，圖6表示CPU執行時間，圖7表示Skyline大小隨著每種設施數量變化產生的影響。從圖中可以看出，INN算法在各個方面要明顯優于ANN及其擴展算法。從圖5可以看出，隨著非空間屬性維度增大，I/O次數對于ANN和INN算法并沒有明顯影響。這主要是因為在進行全最近鄰查詢時，并不涉及非空間屬性，所以其I/O消耗主要是進行最近鄰查詢時產生的。從圖6可以看出，隨著非空間屬性維度增大，對于反相關分布，CPU執行時間都隨之增加，這主要是因為非空間屬性維度的增加使得兩點之間的支配性代價增加，所以計算Skyline時產生了更多的時間消耗。從圖7中可以看出，對于反相關分布和獨立分布，靜態Skyline的大小明顯增加，因此ex-ANN算法要優于ANN算法。基于上述分析，隨著維度增加，兩兩點間的支配性概率降低，非空間屬性維度對最終Skyline結果影響較大。

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

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

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

5.2.2數據集合大小對算法性能的影響

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

5.2.3設施的種類對算法性能的影響

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

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

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

5.2.4每種設施數量對算法性能的影響

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

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

6　總結

本文研究了結合非空間屬性的通用Skyline查詢處理技術，從設施集合中選擇距離某數據點最近的設施，并將其與該數據點之間的距離映射到距離空間上，然后在新的距離空間中進行Skyline查詢。采用R樹索引結構對數據集建立索引，根據數據點導向和查詢點導向兩種不同的搜索導向的優缺點，提出了SQ_ANN算法及其擴展算法，以及SQ_INN算法。SQ_INN算法主要是通過過濾的方法來對數據集進行剪枝，減少I/O次數。理論和實驗表明SQ_INN算法無論在CPU執行時間還是I/O次數上都優于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年于南京航空航天大學獲得碩士學位，主要研究領域為Skyline計算，感知數據管理等。

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年于南京航空航天大學獲得工學博士學位，2007—2009年在清華大學計算機系從事博士后研究工作，2016—2017年在澳大利亞新南威爾士大學計算機科學與工程學院從事國家公派訪問學者工作，現為南京航空航天大學副教授，CCF高級會員，主要研究領域為Skyline計算，感知數據管理，計算幾何，蒙特卡羅方法等。

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—），男，江蘇徐州人，南京航空航天大學碩士研究生，主要研究領域為概率Skyline計算，感知數據管理等。

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(江蘇省自然科學基金);the Fundamental Research Funds for the Central Universities of China under Grant No.NS2015095(中央高校基本科研業務費專項資金);the Foundation of Graduate Innovation Center in NUAAunder Grant No.KFJJ201461(南京航空航天大學研究生創新基地開放基金).

CNKI網絡優先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.018.html