道路網(wǎng)環(huán)境下K-支配空間Skyline查詢方法

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

1(哈爾濱理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)2(哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

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

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

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

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

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

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

1 定義與性質(zhì)

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

本節(jié)給出相關(guān)的定義與性質(zhì).

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

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

2)d(p2,q)

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

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

(1)

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

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

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

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

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

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

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

2 道路網(wǎng)K-支配空間Skyline查詢

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

2.1 約減數(shù)據(jù)集

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

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

定理1.在由數(shù)據(jù)點構(gòu)造的道路網(wǎng)Voronoi圖中，若查詢凸包CH(Q)內(nèi)有一數(shù)據(jù)點p，則數(shù)據(jù)點p支配CH(Q)與該點所成圓相切區(qū)域外的數(shù)據(jù)點，則該區(qū)域外的數(shù)據(jù)點均被約減，區(qū)域內(nèi)的數(shù)據(jù)點可加入候選集中.

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

證畢.

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

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

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

證畢.

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

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

證畢.

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

約減策略1.數(shù)據(jù)點在查詢區(qū)域內(nèi)或者查詢點所在的道路網(wǎng)Voronoi單元與查詢區(qū)域相交，則將查詢點加入到候選集中.

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

約減策略2.數(shù)據(jù)點所在的道路網(wǎng)如果與查詢區(qū)域相交，則將該數(shù)據(jù)點加入到候選集中.

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

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

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

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

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

輸入：查詢區(qū)域Q、道路網(wǎng)路段集合R、數(shù)據(jù)集P;

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

① 以P中的數(shù)據(jù)點和道路網(wǎng)路段為生成點創(chuàng)建道路網(wǎng)Voronoi圖;

②a[pi]←?;

③ fori=0 tondo

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

⑤ 將結(jié)果按升序結(jié)果存入a[pi]中；

⑥ end for

⑦resultSP←?;

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

⑨ ifp在CH(Q)內(nèi)then

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

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

2.2 精煉候選集

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

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

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

(2)

(3)

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

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

我們進一步給出道路網(wǎng)數(shù)據(jù)點K-支配的I-PNS算法如算法2所示.

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

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

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

①Sk←?;

② for every pointp∈resultSPdo

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

④p初始化標(biāo)記為p.isDominat=false;

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

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

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

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

⑨ end for

⑩ fori=1 totdo*t是數(shù)組A和數(shù)組B中數(shù)據(jù)點的個數(shù)*

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

2.3 查詢算法

本節(jié)根據(jù)道路網(wǎng)K-支配空間Skyline查詢的不同情況分別調(diào)用道路網(wǎng)空間Skyline情況下的R-PNS算法和K-支配空間Skyline查詢情況下的I-PNS算法進行查詢.

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

證明. 當(dāng)數(shù)據(jù)點p∈Sk時，以查詢點qi為圓心、以qi與數(shù)據(jù)點p之間的網(wǎng)絡(luò)距離d(qi,p)為半徑作圓，若在多個圓域的相交區(qū)域內(nèi)存在數(shù)據(jù)點pk，則對于查詢點qi，一定存在d(qi,pk)

證畢.

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

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

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

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

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

輸入：查詢集Q、支配維數(shù)k、數(shù)據(jù)集P、道路網(wǎng)路段集R;

輸出：道路網(wǎng)K-支配情況下的空間Skyline查詢的結(jié)果集Sp.

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

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

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

④ ifp在Sk中then

⑤ forj=1 tomdo

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

⑦ ifpinsideSk并且p∩C≠? then

⑧Sp←Sp-p;

⑨ else ifp不在其他點的支配圓域內(nèi)then

⑩Sp←Sp+p;

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

3 實驗比較與分析

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

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

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

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

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

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

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

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

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

Fig. 7 Effect of road network line segmentnumber on query performance圖7 道路網(wǎng)線段數(shù)量對查詢性能影響

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

4 結(jié)束語

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