道路網環境下K-支配空間Skyline查詢方法

李 松 竇雅男 郝曉紅 張麗平 郝忠孝,2

1(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080)2(哈爾濱工業大學計算機科學與技術學院 哈爾濱 150001)

隨著數據智能和數據處理技術的發展及廣泛應用，多目標優化查詢問題成為一個熱點和難點問題.多目標優化查詢幫助用戶在一定約束條件下獲得在多個目標對象下的查詢結果以達到最優的結果集.Skyline查詢是多目標優化查詢中一類重要的查詢問題.Skyline查詢方法由Borzsony等人[1]提出，通過Skyline點的性質縮小結果集，提高并優化查詢效率.

目前，Skyline查詢方法的研究已經拓展到無線傳感網絡中的動態Skyline查詢[2]、不確定數據Skyline查詢[3]、移動K-支配最近鄰查詢[4]、反Skyline查詢[5]、數據流Skyline查詢[6]、子空間Skyline查詢[7]、連續Skyline查詢[8]、概率Skyline查詢[9]、Top-kSkyline查詢[10]、基于MapReduce的Skyline查詢[11]、障礙空間中的Skyline查詢[12]等方面.取得的研究成果解決了Skyline查詢領域及延伸領域內的一系列重要的問題.上述研究的空間條件均沒有考慮路網環境，但實際生活中人們很多時候均活動在道路網中，因此，道路網Skyline查詢是一類重要的Skyline查詢問題，道路網Skyline查詢問題具有重要的應用價值.

相對于理想空間，道路網的空間拓撲結構更加復雜，數據對象之間的距離計算復雜度更高，傳統的距離計算已不能很好地適用于道路網環境中.近年來針對道路網多目標優化查詢的研究已經取得一些重要研究成果，潘曉等人[13]提出了在道路網絡上基于時空相似性的連續查詢隱私保護算法，該算法通過分組策略和共享機制防止連續查詢攻擊和位置依賴攻擊.Bao等人[14]提出一種基于將道路邊緣劃分為子區間的基本算法，并通過檢查子區間的端點來找到最佳位置.這些算法很好地處理了路網邊緣區域的點，但是卻忽略了數據點之間的空間支配關系，導致非邊緣的數據對象之間的距離也需要通過復雜的計算得到結果.文獻[15]對各個區域的數據點與查詢點的位置關系均進行了處理，但是算法需要重復檢查數據點之間的支配性，從而影響了算法查詢效率.

Huang[16]出于用戶隱私保護提出了基于位置范圍的Skyline查詢方法，設計了數據對象與道路網間的數據結構，將查詢對象模糊化為一個位置范圍用以保護用戶隱私.該方法計算數據點與查詢對象的網絡距離時，只需計算數據點與位置范圍邊界交點的網絡距離，再重新利用Dijkstra算法來計算距離，不再需要重復查詢，因而可以節省實時計算開銷.Miao等人[17]針對查詢點推理確定更有潛力的Skyline點，方法具有一定的創新，但是算法對每個查詢點的計算效率有待進一步提升.文獻[18-19]提出了安全區域的概念，在安全區域內計算查詢對象與目標對象之間的最短網絡距離.但是安全區域需要對區域更新和維護.

對于K-支配Skyline查詢問題，Lee等人[20]提出了一種在計算期間減少選擇候選者和支配誤報的方法.Miao等人[21]研究了不完整數據上K-支配Skyline查詢的問題，提出利用位圖索引縮小搜索空間的方法.這些算法可以有效減少數據點的k維屬性支配判斷的比較次數和減少IO代價次數，具有較好的性能.但忽略了數據對象的空間屬性對查詢結果的影響，當數據對象的空間位置屬性改變時，則需要重新計算k維的結果.文獻[22]考慮到數據對象的屬性具有相關聯性，通過查詢預處理對空間屬性必支配的屬性進行處理使得查詢效率提升.文獻[23]基于MapReduce平臺提出了一個有效的并行算法來處理K-支配Skyline查詢問題.文獻[24]提出了一種基于索引的K-支配Skyline查詢算法,通過為數據集建立2個索引,算法可以高效地進行計算,在時間、空間和漸進性上具有一定的性能優勢.

已有的道路網Skyline查詢一般只有一個查詢對象，但是查詢對象往往是不唯一的，查詢對象之間的相互影響可能導致數據對象的屬性值發生變化.因此，使用單一的查詢點會導致查詢結果不符合實際需求.并且查詢方法若不考慮數據點的非空間屬性對查詢的影響，則可能導致查詢的結果不準確.在實際應用中，數據點的空間位置和非空間屬性值都對用戶的選擇有影響，這就需要結合空間屬性和非空間屬性k維的支配關系來選擇.如何將K-支配Skyline查詢問題應用于道路網環境，特別當查詢點的空間位置發生動態改變時還能準確提供最優化查詢結果成為研究的難點.針對這些問題，本文將K-支配應用到道路網Skyline查詢中以處理多屬性數據對象，利用K-支配解決了道路網查詢支配的問題.本文利用道路網Voronoi圖的定義與相關性質對數據點進行約減和支配檢查.在理論論證和分析的基礎上提出了道路網K-支配空間Skyline查詢方法.

1 定義與性質

道路網K-支配空間Skyline查詢是道路網Skyline查詢的變種問題，該問題涉及4個組成對象：數據點集、查詢區域范圍、查詢屬性范圍以及道路網.本文假定數據點集P是一組具有k維屬性的點的集合，其中k-1維為靜態的非空間屬性，k維屬性為數據點在道路網中位置的坐標.

本節給出相關的定義與性質.

定義1.非空間屬性支配[22].給定2個數據點p1，p2，考慮所有的非空間屬性，如果p1能被p2支配，稱p2非空間屬性支配p1，記為p2p1.所有非空間屬性支配p1點的集合稱為p1的非空間屬性支配集，記為Dom(p1).

定義2.道路網支配[16].在道路網環境下給定一個查詢點q和2個數據點p1，p2，d(q,p1)表示數據點p1距離查詢點q的網絡距離.當且僅當滿足2個條件時，稱p2道路網支配p1(簡稱“支配”)，記為p2p1:

2)d(p2,q)

定義3.空間支配[7].空間中存在一個數據點p∈P，查詢點qi，如果滿足條件：對于P中任意一個數據點p′∈P，對于查詢點qi存在d(qi,p)≤d(qi,p′)成立，則數據點p空間支配數據點p′.

定義4.網絡Voronoi圖(network Voronoi diagram, NVD)[25].NVD與基本Voronoi圖的區別在于NVD采用的是路網距離，而并非歐氏距離.在NVD中，由路網中的邊和虛線所圍成的區域稱為網絡Voronoi區域(network Voronoi polygon, NVP).由pi生成的NVP記為VNVP(pi).若給定生成點集合P={p1,p2,…,pn}，邊的集合E={e1,e2,…,ek}.pj為不同于pi的生成點，則VNVP(pi)可以形式化定義為

(1)

性質1[25].如果點q在網絡Voronoi多邊形VNVP(pi)中，則q到生成點pi的距離小于q到其他生成點的距離.

性質2[25].距離pi點最近的生成點一定在與VNVP(pi)有公共Voronoi邊的Voronoi多邊形中.

定義5.道路網K-支配空間Skyline查詢.給定一個查詢點q和一個n維空間的對象集P，其中道路網K-支配空間Skyline查詢結果返回P的一個子集，在此子集中的數據點都不能被P中的任何其他點在用戶偏好的k-1個維度上非空間屬性支配，并且在第k維空間屬性上在道路網環境中也未被其他數據點空間支配，這樣的數據點被稱為道路網K支配空間Skyline點，記為K-PNS(q,P).道路網K-支配空間Skyline查詢本文簡稱為K-PNS查詢.

表1表示一個賓館數據對象的非空間屬性表.非空間屬性是數據點的非空間地理位置的數據點自身存在的一些屬性.這些信息不是地理位置上的空間坐標的位置，是非空間上數據點本身自有的屬性，本文中的非空間屬性是在一定范圍內隨機取得的模擬值.表1中，數據點p1,p2,p3,p4,p5為數據對象集中5個具有5維屬性的賓館，其中前4維為非空間屬性，對應賓館的價格、開業時間、用戶評價和清潔情況.最后一維屬性為賓館距離查詢點的道路網距離,如圖1所示，圖1給出了5個賓館對象在道路網上的位置分布以及查詢區域，需要查找的是在5維屬性中數據點在4維屬性維度上不被支配的查詢結果，即道路網4-支配空間Skyline查詢.

Table 1 Example of Non-spatial Attributes of Hotel Data Object表1 賓館數據對象的非空間屬性示例

Fig. 1 Example of spatial attributes of hotel data object圖1 賓館數據對象的空間屬性的示例

首先對空間屬性進行支配查詢，圖1中圓弧線a1,a2,a3,a4,a5,a6,a7,a8表示數據點p2,p3,p4相對查詢點的支配圓域，由圖1可以看出在支配圓域內的點支配生成該圓域的點，因此，數據點p2,p3,p4在道路網環境空間支配點p1和p5，即數據點在空間屬性上不被支配的查詢結果為{p2,p3,p4}.進一步對非空間屬性進行3維支配的查詢，基于查詢區域的道路網Skyline查詢需要查找對象集中既便宜，且用戶評價好又距離用戶當前位置近的賓館.由表1可以看到在非空間屬性中，在價格方面數據點p4和點p2被點p3支配，因此對于數據點在道路網4支配空間Skyline查詢的結果為{p3}.即該例子中的道路網K-支配空間Skyline查詢的結果為{p3}.

2 道路網K-支配空間Skyline查詢

本文提出的道路網K-支配空間Skyline查詢方法主要分為2個主要的過程：道路網中約減數據集過程和K-支配檢查過程.首先通過約減大量的非候選數據點得到道路網環境中的候選集合，然后對候選集的非空間屬性進行K-支配檢查得到道路網精煉集合，最后對精煉集合進行支配檢查得到最終的空間Skyline集合.本節優先處理數據點空間屬性的道路網支配關系，由于數據點非空間屬性往往較多，從而使得非空間屬性間支配比較次數增加，如果優先處理非空間屬性間的支配關系，在數據點數量較大時，算法的查詢效率會降低.

2.1 約減數據集

約減數據集過程主要是對數據點進行過濾處理，通過道路網Voronoi圖與查詢點集合建立影響的查詢區域間的空間位置關系來剪枝掉大量的被支配的數據點，用于獲得精確的候選點集合.首先對空間數據點構建道路網Voronoi圖，再對查詢點建立一個查詢的凸包.然后利用道路網Voronoi圖及其查詢區域形成的位置關系以及數據點之間的支配關系來約減大量被支配的數據點，從而縮小查詢范圍，剩下的數據點構成候選點集合.在此過程中通過對查詢點集建立查詢區域與建立數據點的道路網Voronoi圖的方法來約減數據集，能夠優化處理數據集并且有效地減少查詢點重復搜索的現象，約減掉大量的非候選點，較大程度地縮小了查詢的范圍.

本文所研究的數據點與查詢點之間的距離均采用道路網絡中的網絡距離.本節以定理的形式給出約減方法.假定數據點前n維的非空間屬性是固定不變的，本節為了簡化道路網非空間屬性對空間支配的影響，用數據對象的非空間屬性值的總和來表示非空間屬性的支配能力，結合數據點的空間屬性，查詢結果得到的不被空間支配的候選集是固定的，使得查詢效率更快.由于數據點為道路網上的靜態點，故其道路網Skyline查詢結果的變化是由查詢位置與數據點之間的距離變化引起的.

定理1.在由數據點構造的道路網Voronoi圖中，若查詢凸包CH(Q)內有一數據點p，則數據點p支配CH(Q)與該點所成圓相切區域外的數據點，則該區域外的數據點均被約減，區域內的數據點可加入候選集中.

證明. 已知在道路網Voronoi圖中的數據點p與各查詢點所成圓域外的一點數據點，2點所連接的線段的垂直平分線將2點分割為2個區域，p點與查詢區域CH(Q)在同一邊，根據垂直平分線性質，p點與各查詢點的距離更近，則數據點p支配CH(Q)與該點所成圓相切區域外的數據點.在圖2中，任意選取1組數據點和查詢點，例如查詢點集為Q={q1,q2,q3}，數據點集為P={p1,p2,p3,p4,p5}.查詢點組成的查詢區域CH(Q)內任意位置有一數據點p，分別以各查詢點q為圓心、以數據點p與各查詢點間的距離為半徑做圓.圖2中的矩形區域表示數據點p與各查詢點形成的圓(circle(p,q))相切的數據點p的支配區域，圓弧線l1,l2,l3表示數據點相對不同查詢點的支配圓域.如圖2所示，數據點p2是數據點p與各查詢點形成的圓相切矩形區域外的任意一個數據點.從圖2可以求得數據點p與查詢點q1的道路網環境中的網絡距離關系為：d(q1,p)

證畢.

Fig. 2 Example based on theorem 1,2 and 3圖2 基于定理1,2,3的示例

定理2.已知數據點p∈P，如果查詢區域CH(Q)與該數據點所在的道路網Voronoi單元VC(p)相交，若數據點q為與數據點p所在道路網上任意一條不相交的道路網上的一個數據點，則數據點p支配點q，數據點q被剪枝.

證明. 任意連接與查詢區域有關聯的數據點p和與查詢區域不相交的Voronoi單元內的數據點，則該2個數據點構成的線段的垂直平分線將與查詢區域相交的Voronoi單元的數據點與查詢點劃分在一邊.根據Voronoi圖性質可知，在Voronoi單元內的數據對象點與形成該Voronoi單元的生成點之間的距離最短，因此與查詢區域相交的數據點支配未與查詢區域相交的數據點.如圖2所示，任意選取數據點如p4，數據點p4∈P，數據點p4所在的Voronoi單元與查詢區域CH(Q)相交，作線段pp″為數據點p1和數據點p4線段的垂直平分線，根據垂直平分線性質可知，同屬一邊的2點距離更近，由圖2可以知道線段pp″與查詢區域CH(Q)不相交，且該垂直平分線將數據點p4與CH(Q)劃分到同一側，已知垂直平分線上點到線段的兩端點的距離相等，則對于qi∈CH(Q)，一定有d(qi,p4)

證畢.

定理3.對于給定的查詢凸包區域CH(Q)，若數據點所在的道路網與CH(Q)的邊界相交，則該數據點與查詢各點的網絡距離更近，該數據點可加入到候選集中.

證明. 對于查詢區域CH(Q)內任意查詢點q，從q出發，要到達查詢區域CH(Q)外的任意對象點pi，其最短路徑必定經過查詢區域CH(Q)與道路網的交點.由2點間線段最短定理可知，數據點pi與查詢點q間的網絡距離一定大于查詢點q與相交路網上數據點的距離，故數據點pi被剪枝.如圖2所示，要從對象數據點p1，p2，p3，p4到查詢區域CH(Q)中任意一個查詢點q，必定經過查詢區域CH(Q)的邊界與道路網的交叉點a,b,c這3個點之中的某一個.因此，對于數據點p1，存在有d(q1,p)=d(q,b)+d(b,p1).可見數據點p1到查詢區域內部點q必經過查詢區域的交點b，由此可知數據點所在的道路網與CH(Q)的邊界相交，則該數據點與查詢各點的網絡距離更近，將該數據點加入到候選集中.

證畢.

只有當一個數據點在空間屬性與非空間屬性上均支配另一個數據點時，該數據點才可能是道路網中K-支配Skyline點，應該將這類數據點加入到候選集中.由于可能存在數據點的某些非空間屬性值較大，影響K-支配查詢的效率，因此在道路網環境中用數據點的非空間屬性值的總和代表數據點非空間屬性的支配能力，總體的支配能力可以初步約減掉部分非空間屬性值較大的情況，便于約減非空間屬性支配能力差的數據點.

約減策略1.數據點在查詢區域內或者查詢點所在的道路網Voronoi單元與查詢區域相交，則將查詢點加入到候選集中.

在數據點構造的道路網Voronoi圖中，若查詢凸包CH(Q)內有一個數據點p，則數據點p支配CH(Q)與該點所成圓的相切區域外的數據點，則該區域外的數據點均被約減，區域內的數據點可加入候選集中.任意連接與查詢區域有交集的數據點p和未與查詢區域相交的Voronoi單元內的數據點，則該2個數據點構成的線段的垂直平分線將與查詢區域相交的Voronoi單元內的數據點與查詢點分在一邊.根據Voronoi圖性質，在Voronoi單元內的點與形成該Voronoi單元的點之間的距離最短，因此，與查詢區域相交的數據點支配未與查詢區域相交的數據點.

約減策略2.數據點所在的道路網如果與查詢區域相交，則將該數據點加入到候選集中.

任意連接與查詢區域有關聯的數據點p和未與查詢區域相交的Voronoi單元的數據點，則該兩個數據點夠成的線段的垂直平分線將與查詢區域相交的Voronoi單元的數據點與查詢點化分在一邊.根據Voronoi圖性質可知在Voronoi單元內的點與形成該Voronoi單元的點之間的距離最短，因此各查詢點與有關聯的VNVP(p)內的數據點p的空間距離更短，即與查詢區域相交的數據點支配未與查詢區域相交的數據點.對于查詢區域CH(Q)內的任意查詢點q，從q開始到達查詢區域CH(Q)外任意對象點pi，其最短路徑必定經過查詢區域CH(Q)與道路網的交點.因此，數據點pi與查詢點q間的網絡距離一定大于查詢點q與相交路網上數據點的距離，故數據點pi被剪枝.

約減策略3.對于候選集中數據點的非空間屬性的支配能力進行比較，支配能力更強的數據點留在候選集，否則從候選集中刪除.

用數據點的非空間屬性值的總和來表示數據對象的非空間屬性的支配能力，只有當一個數據點在空間屬性與非空間屬性上均支配另一個數據點時，該數據點才可能是道路網中K-支配Skyline點，應該將這類數據點加入到候選集中.

基于定理1、定理2和定理3及約減策略，本節進一步給出算法R-PNS，如算法1所示.

算法1.R-PNS(Q,P,R).

輸入：查詢區域Q、道路網路段集合R、數據集P;

輸出：基于查詢范圍Q的道路網Skyline查詢候選集resultSP.

① 以P中的數據點和道路網路段為生成點創建道路網Voronoi圖;

②a[pi]←?;

③ fori=0 tondo

④ 計算p點的前n維非空間屬性值的和；

⑤ 將結果按升序結果存入a[pi]中；

⑥ end for

⑦resultSP←?;

⑧ 連接查詢點組成最大的凸多邊形查詢區域CH(Q);

⑨ ifp在CH(Q)內then

⑩SR(p,Q)←circle(p,q1)∪…∪circle(p,qm);*以qi為圓心，p,qi之間的距離為半徑做圓，m為查詢點的數量*

約減數據集由算法1實現.算法1首先對數據點集建立道路網Voronoi圖并對數據點的非空間屬性值進行計算，總和的值越小表示數據點的非空間屬性的支配能力越強.再對查詢點建立查詢區域CH(Q)，根據道路網Voronoi圖與查詢區域CH(Q)的位置關系，由定理1判斷數據點是否在查詢區域CH(Q)內，如果數據點在查詢區域內，則直接將該數據點加入候選集中.再進行判斷與查詢區域有交集的道路網Voronoi單元的數據點，根據定理2將這些數據點加入候選集中，這些點在空間上支配那些所在的道路網Voronoi單元不與查詢區域相交的數據點.再判斷數據點所在的道路網路段與查詢區域是否相交.根據定理3將道路網上相交的數據點加入候選集中，將不符合條件的數據點約減，減少計算大量非候選數據點.根據道路網Voronoi圖查詢區域CH(Q)與道路網集R路段的交點，將每一個交點所在路段上的數據點加入到候選集，再將所有的候選點進行合并.最后對resultSP集合中數據點的非空間屬性值進行支配能力檢查，值越小的數據點支配另一個數據點.在道路網環境中用數據點的非空間屬性值的總和代表數據點的非空間屬性的支配能力，總體的支配能力可以初步約減掉部分非空間屬性值較大的情況，約減非空間屬性支配能力差的數據點，獲得最終的候選集.

2.2 精煉候選集

精煉候選集過程的主要處理對象是在約減過程中所得到的候選集resultSP.本節首先根據數據點K-支配的定義及支配關系給出定理4和定理5，再根據定理對候選集中的數據點進行非空間屬性支配判斷，若滿足條件則加入候選集中，從而構成精煉候選集.本文中數據點的非空間屬性是由數據點的前n維隨機生成的，非空間屬性值越小越好.

定理4[24].對于任意2個數據點pi和pj，若數據點pi在k維非空間屬性上支配數據點pj，則數據點pi必定k-1維支配數據點pj.

本節將數據點的非空間維數屬性值的范圍定為相同的，并且屬性值越小它的優勢越大.數據點在k維上的最好和最差的支配能力分別為

(2)

(3)

定理5[24].如果對于數據集d維中的任意2個數據點p1和p2，若在k維上存在worstK(p1)≥bestK(p2)，則數據點p2一定不會在k-1維非空間屬性上支配數據點p1.

可以將候選點與各查詢點間的距離總和作為空間屬性的值，如果數據點在非空間和空間屬性上均不被其他數據點支配，則將該點加入到精煉集合中.將數據點與查詢點的空間距離總和作為空間屬性與非空間屬性進行K-支配判斷，得到精煉集合Sk.由于數據點的空間屬性同樣需要檢查K-支配，影響K-支配查詢的效率，因此在道路網環境中用數據點與各查詢點的空間距離總和作為空間屬性代表數據點空間屬性的支配能力，總體的支配能力可以約減掉部分空間屬性值較大的情況，便于精煉數據點.

我們進一步給出道路網數據點K-支配的I-PNS算法如算法2所示.

算法2.I-PNS(resultSP,Q,t).

輸入：候選集resultSP、查詢集合Q、用戶感興趣的非空間屬性值個數t;

輸出：resultSP中的K-支配Skyline數據精煉候選集Sk.

①Sk←?;

② for every pointp∈resultSPdo

③ 計算點p最好的支配能力值bestK(p)和最差的支配能力值worstK(p);

④p初始化標記為p.isDominat=false;

⑤ 對resultSP中的數據點p的最好的支配能力值bestK(p)進行升序排序;

⑥ 將bestK(p)升序排序結果存儲到數組AI[1,2,…,t]中;*數組AI[1,2,…,t]構成AI表*

⑦ 對resultSP中的數據點p最差的支配能力值worstK(p)進行升序排序;

⑧ 將worstK(p)升序排序結果存儲到數組BI[1,2,…,t]中；*數組BI[1,2,…,t]構成B表*

⑨ end for

⑩ fori=1 totdo*t是數組A和數組B中數據點的個數*

算法2首先建立2個索引表來存儲數據點的k維的最好和最壞支配能力值：AI表和BI表，根據對算法1中所得的候選集優化精煉的基本思想，首先要對候選集中的數據點計算其最好支配能力值和最差支配能力值，將結果按升序存儲在表中，并對每一個數據點初始標記為未被支配.再根據定理4和5對表AI和BI中的數據點進行比較.如果worstK(pi)

2.3 查詢算法

本節根據道路網K-支配空間Skyline查詢的不同情況分別調用道路網空間Skyline情況下的R-PNS算法和K-支配空間Skyline查詢情況下的I-PNS算法進行查詢.

定理6.確定數據點的支配判定圓區域的范圍，數據點p與查詢點qi之間通過道路網相互連接，當數據點p∈Sk時，則以查詢點qi為圓心、查詢點qi與數據點p間的網絡距離d(qi,p)為半徑做圓，若在多個圓域的相交區域中存在數據點pk，則數據點pk空間上支配數據點p，則將數據點p剪枝.

證明. 當數據點p∈Sk時，以查詢點qi為圓心、以qi與數據點p之間的網絡距離d(qi,p)為半徑作圓，若在多個圓域的相交區域內存在數據點pk，則對于查詢點qi，一定存在d(qi,pk)

證畢.

圖3中，以qi點為中心、以候選集內的任意一數據點p之間的網絡距離為半徑做圓，圓弧線d1,d2,d3表示數據點相對不同查詢點的支配圓域.若該圓域相關的相交區域內存在其他數據點p′，則相交區域內的數據點p′支配數據點p.根據定理2和3，{p1,p2,p4,p′}可加入候選集.以{q1,q2,q3}為圓心、以各候選集內的數據點的網絡距離為半徑做圓(如圖3所示)，點p′即處于這些圓域的相交區域中，根據定理6可知p2支配點p′.由此可知，數據點中不被空間支配的查詢結果為Sk={p4,p′}.

Fig. 3 Example based on theorem 6圖3 基于定理6的示例

本節查詢算法的主要思想為：首先調用算法1得到初步約減數據集后的候選集，再調用算法2對候選集進行非空間屬性K-支配精煉處理，獲得更精確的候選集.然后分別求出候選集中的點p到qi的網絡距離d(p,qi).若滿足d(qi,p1)

本節進一步給出K-PNS查詢算法，如算法3所示.

算法3.K-PNS(Q,k,P,R).

輸入：查詢集Q、支配維數k、數據集P、道路網路段集R;

輸出：道路網K-支配情況下的空間Skyline查詢的結果集Sp.

①resultSp←?,Sk←?,Sp←?;

②resultSp←callR-PNS(Q,P,R);*調用算法1，計算約減候選集合*

③Sk←callI-PNS(resultSp,Q,k);*調用算法2，計算精煉候選集合*

④ ifp在Sk中then

⑤ forj=1 tomdo

⑥C←Calculate_Circle(qj,pi);*計算支配判定圓的范圍*

⑦ ifpinsideSk并且p∩C≠? then

⑧Sp←Sp-p;

⑨ else ifp不在其他點的支配圓域內then

⑩Sp←Sp+p;

算法3首先調用算法1求出PNS查詢結果；在考慮數據點的k維屬性時，則調用算法2得到精煉集.對精煉集合中的數據點再進行支配檢查，對數據點與查詢點做判定圓區域檢查，在區域內若無其他數據點則加入Sp集，否則刪除.最后算法對Sp集中的點進行k維檢查，不滿足條件的數據點從Sp集中刪除，最終留下的數據點就是道路網K-支配空間Skyline查詢的結果集.

3 實驗比較與分析

本節通過實驗對算法進行性能評估.由于道路網中K-支配空間Skyline查詢問題是本文研究的一個新問題，已有研究成果無法直接處理道路網中K-支配空間Skyline查詢問題，因此，為了構造對比算法，我們對文獻[26-27]的曼哈頓道路網中空間Skyline查詢的MSSQ算法和道路網基于距離的連續Skyline查詢的Cknn-SQ算法進行了適當的修改，針對給定查詢問題采用反復調用MSSQ算法和Cknn-SQ算法的策略，從而逐步得到數據點k維屬性上的Skyline查詢結果，從而與本文提出的K-PNS算法形成對比算法.得到的對比算法在本文稱為MSSQ算法和Cknn-SQ算法.MSSQ算法分別對數據點集P和查詢點集Q在一維上建立平衡二叉樹，在其他維度上保存數據；Cknn-SQ查詢算法從Skyline結果集中向用戶返回s個Skyline點，這s個Skyline點在距離屬性上要優于剩下的數據點.

本文使用的道路網數據集是來自美國加利福尼亞州空間信息網絡，該網絡中的數據集由地理信息組成.我們從該數據集中抽取10 000個節點對象和5 000個線段對象(線段作為道路網線段).為便于實驗，對數據對象信息進行了適當調整和改動.查詢集是由數據集中隨機抽取的100個點的集合，數據點的非空間屬性以數值來表示，數值在[0,20]上隨機產生.

實驗平臺配置為：4 GB內存、2.0 GHz CPU、500 GB硬盤，Windows 10操作系統上用Microsoft Visual Studio2013實現.實驗需要驗證的是3個算法的查詢性能，測試的指標是CPU時間和IO執行次數，兩者反映各個算法的查詢性能.實驗測試中采用的合成數據為Skyline查詢的測試數據集，測試過程中取執行30次查詢的平均值作為結果.實驗分別測試非空間屬性維數k值、數據點數量和道路網路段數量對CPU執行時間和IO執行效率的影響.

Fig. 4 Effect of k value on the efficiency ofthe query algorithms圖4 k值對查詢算法效率的影響

如圖4所示，實驗測試了k值對算法的影響.在數據點的數量是10 000、查詢點數量為100、道路網線段數量為1 000、數據點維數d=10、數據集的非空間屬性維數k從1增加到5的情況下測試了3種查詢算法的查詢性能.從圖4(a)中可以看出，K-PNS算法、MSSQ算法和Cknn-SQ算法的CPU執行時間都是隨著k值的增大而呈上升趨勢，K-PNS算法和Cknn-SQ算法的查詢效率均優于MSSQ算法.但是Cknn-SQ算法上升趨勢比K-PNS算法更顯著，原因在于Cknn-SQ算法需要重新調用算法對視作數據點的道路網線段重新處理.圖4(b)展示了k值增加對K-PNS算法、MSSQ算法和Cknn-SQ算法的IO代價的影響情況.由圖4(b)可以看到隨著k值的增加，3個算法的IO代價都逐漸增大，但K-PNS算法隨著k值的增長速率先增大后減小，IO代價的增幅最小.這是因為在數據點的非空間屬性維數較小時，數據點的非空間屬性的相互支配較多，所以IO代價較高.

Fig. 5 Effect of dimension of data set onquery efficiency圖5 數據集維數對算法查詢效率的影響

圖5測試的是關于數據集維數變化對算法查詢效率的影響.在數據點的數量是10 000、查詢點數量為100、道路網線段數量為1 000、k=3的情況下測試了3種查詢算法的查詢性能.圖5表示的是數據集維數d對算法的查詢性能的影響.MSSQ算法采用平衡二叉樹處理數據點間的道路網距離，隨著數據集維數的增大，算法增加的趨勢并不快，但是算法原本需要花費較多的時間和IO代價處理.Cknn-SQ算法采用網格索引對道路網和道路網上的數據點進行索引，維數的增多和距離增大使算法的查詢性能有所降低.K-PNS算法在約減數據集的過程中，對空間屬性和非空間屬性分別進行了處理，因此隨著維數的增加，算法的查詢時間和IO代價變化較小.在數據集維數增加的情況下，K-PNS算法和Cknn-SQ算法優于MSSQ算法.

Fig. 6 Effect of data size on query performance圖6 數據點數量對查詢性能的影響

圖6測試數據點數量對算法查詢性能的影響.設道路網線段數量為1 000、查詢點為100、數據點維數d=10、k=3.由圖6(a)可知，K-PNS算法和Cknn-SQ算法的時間耗費相對較少，MSSQ算法時間耗費較多.因為MSSQ算法需要對數據點進行重復調用來計算數據點k維非空間屬性，在數據點增加的過程中反復調用算法花費時間較多，而K-PNS算法已經對數據點的非空間屬性進行了處理，所以隨著數據點的增加，CPU執行時間增加較小.從圖6(b)中可以看出，隨著數據點的增加，3個算法的IO代價都增加，本文所提的K-PNS算法比Cknn-SQ算法和MSSQ算法的CPU時間和IO開銷都要小.隨著道路條數的增多，道路連通性更加復雜，Cknn-SQ算法計算全局Skyline點過程中，對道路網的訪問以及對象之間的距離計算的復雜度都會增大.而K-PNS算法由于只需要維護固定對象序列的相鄰對象點的距離關系，雖然其開銷也會隨著道路條數的增多而增大，但較MSSQ算法和Cknn-SQ算法的復雜度降低.

Fig. 7 Effect of road network line segmentnumber on query performance圖7 道路網線段數量對查詢性能影響

圖7測試道路網線段對算法的查詢性能的影響.設數據點數量為10 000、查詢點數量為100、數據點集維數d=10、k=3.圖7表示的是道路網線段數量對算法的查詢性能的影響，w表示道路網線段數量.MSSQ算法采用平衡二叉樹處理數據點間的道路網距離，隨著道路網線段數量的增大，算法需要花費更多的時間和IO代價處理，而Cknn-SQ算法采用網格索引對道路網和道路網上的數據點進行索引，隨著道路網線段增多，數據點與查詢點之間的距離關系會發生變化，算法的查詢性能減慢.但是K-PNS算法中在約減數據集的過程中，對不被支配路段的點及其路段進行了約減，所以道路網路段的增加對CPU執行時間和IO代價增長的趨勢不大.因此在道路網線段增加的情況下，K-PNS算法優于MSSQ和Cknn-SQ算法.

4 結束語

本文對道路網K-支配空間Skyline查詢問題進行了系統研究.形式化定義了道路網環境下K-支配空間Skyline查詢，提出了有效地處理道路網K-支配空間Skyline查詢的算法，較大程度地減少了處理數據點和路段數量的時間，通過K-支配檢查可得到精準的結果集.理論研究和實驗表明，所提出的算法具有較好的性能.未來的研究重點主要集中在將障礙空間中的組反k最近鄰查詢技術[28]應用到障礙物的空間Skyline查詢領域以解決復雜環境條件下的空間Skyline查詢問題.