障礙環境中空間Skyline查詢方法*

李 松，竇雅男，張麗平，郝曉紅

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

1 引言

隨著基于位置服務技術的發展與廣泛應用，空間數據庫中的Skyline查詢[1]以及它的變體查詢研究成為熱點問題。近年來,Skyline查詢的研究進一步擴展到海量數據的動態Skyline查詢[2]、不確定數據Skyline查詢[3]、K-支配 Skyline查詢研究[4]、反 Skyline查詢研究[5]、數據流 Skyline 查詢[6]、P2P 對等網絡Skyline查詢[7]、子空間Skyline查詢[8-9]、連續Skyline查詢[10]、概率 Skyline查詢[11]、Top-kSkyline查詢[12]等方面。這些研究所獲得的研究成果解決了Skyline查詢領域及延伸領域內的一系列重要的問題。

空間Skyline查詢[13]（spatial Skyline queries，SSQ）是空間數據庫中重要的查詢之一，SSQ查詢是數據點在d維空間查找不被其他數據點支配的點的集合。例如，在同一個城市的不同地點工作的朋友決定找一個聚餐的餐廳，使得這個餐廳到他們的工作地點距離要合適，這個餐廳就是找出的沒有比其他任何餐廳到他們工作地點的距離更近的最優化的解決策略。對于SSQ查詢，Lin等人[14]提出針對一般空間Skyline查詢的方法，通過選取一個最小的候選集合來減少計算被支配的數據點的個數。Chen等人[15]利用用戶偏好的優先選擇策略，來剪枝不符合條件的數據點。You等人在文獻[16]中為了解決最遠空間Skyline查詢問題，提出了TFSS（thresholdfarthestspatialSkyline）線性算法，利用空間位置來加速Skyline檢索過程，使查詢效率提高。

以上查詢均是在理想的歐式空間下的，但是在空間上移動的物體一般會受到建筑、河流或者道路等地理人為的條件限制。對于障礙環境下空間Skyline查詢（spatial Skyline queries in obstacle space，OSSQ）問題，李松等人[17]提出了基于R+樹的SOS算法，該方法通過建立的R+樹對數據點剪枝，然后精煉得到結果集。但是該方法由于對最小外包矩形處理和支配檢查需要花費大量的空間內存和時間，并且未考慮查詢點的變化對算法的影響，在實際應用中具有較大的局限性。因此本文提出了基于Voronoi圖的靜態OSSQ查詢方法，優點在于使用Voronoi圖快速定位并剪枝非候選點，提高了查詢效率，在支配檢查使用多查詢點時結果更精確。依據查詢點集合發生的變化，提出了查詢點動態變化下的SSQ查詢方法，分別為查詢點動態增加和減少情況下的OSSQ查詢方法。

2 基礎定義

定義1（Voronoi圖[18]）給定一組數據點的集合，P={p1,p2,…,pn}∈R2，其中2＜n＜∞，當i≠j時，pi≠pj。由pi所決定的Voronoi圖單元區域為VH(pi)，由VH(pi)={VH(p1),VH(p2),…,VH(pn)}所定義的圖形被稱為Voronoi圖。共享棱的Voronoi多邊形稱為VH(pi)的鄰接多邊形，其對應的生成點稱為pi的鄰接生成點。

定義2（查詢凸包）在查詢點集中，由多個查詢點連接線段圍成的封閉區域使得剩余的查詢點均在此封閉區域內，這個封閉區域稱為查詢凸包，簡稱CH(Q)。則這些圍成查詢區域的查詢點稱為查詢凸點，簡稱為凸點。

根據文獻[13]的空間支配的定義，結合文獻[18]的點與點之間的障礙距離定義，本文提出障礙空間支配的定義如定義3所示。

定義3（障礙空間支配）在障礙環境下，給定的一組數據集P={p1,p2,…,pn}，查詢集Q={q1,q2,…,qm}和障礙物集O={o1,o2,…,ok}中返回對查詢集Q不被P中其他點支配的點的Skyline集合，即?p′∈P，p′≠p，?qi∈Q，若存在Dobs(p,qi)≤Dobs(p′,qi)，則點p障礙空間支配p′。

3 算法描述

3.1 靜態查詢點環境下的OSSQ查詢

本節提出的靜態查詢點STA_OSSQ查詢方法主要分為兩個主要步驟：約剪數據集和支配檢查。約剪數據集通過3個定理剪枝非候選數據點，然后支配檢查候選集得到最終的空間Skyline集合。

3.1.1 約剪數據集

約剪數據集過程首先對數據點構建Voronoi圖，對查詢點建立一個查詢的凸包，然后利用Voronoi圖的鄰接性質、數據點與查詢點及其查詢區域形成的障礙距離來剪枝掉大量數據點，剩下的未被剪枝的數據點構成候選點集合。

定理1若點p在查詢凸包Q內，則點p支配各查詢點與該點所成圓域區域外的點，則區域外的點被剪枝。

證明在圖1中，黑色點代表數據點，白色點代表查詢點。已知查詢點集Q={q1,q2,q3}，查詢凸包CH(Q)內有一點p1，分別以各查詢點為圓心，以點p1與各查詢點間的距離為半徑做圓如圖1所示，點p′是點p1與各查詢點形成的圓域外的一點，顯然可以得到Deuc(q1,p1)?Deuc(q1,p′),同理 可 得Deuc(q2,p1)?Deuc(q2,p′),Dobs(q3,p1)?Deuc(q3,p′),根據障礙空間點支配的定義可得，點p1在障礙空間上支配圓域外的點p′。因此當查詢區域內存在數據點時，區域外的數據點均被剪枝。

定理2若點pi所在的Voronoi單元VC(pi)與凸包CH(Q)相交，則點pi支配該區域外的點，則此區域外的點被剪枝。

Fig.1 Example of adjacency theorem1 and theorem2圖1 基于定理1和定理2的示例

證明圖1中，點p所在的Voronoi單元與查詢區域CH(Q)相交，點p″為查詢區域外的任意數據點，作線段pp″的垂直平分線，則線段pp″的垂直平分線與CH(Q)不相交，且該垂直平分線將p與CH(Q)分到同一側，由垂直平分線性質可知，CH(Q)上的點與數據點p的距離更近，即對于任意查詢點qj∈CH(Q)，一定存在D(p,qj)?D(p″,qj)。因此，p點支配點p″，故p″被剪枝。

定理3若候選集中的點p的Voronoi鄰居VH(pi)都被剪枝了，則該點p也被剪枝。

證明假設在候選集中取一點為p，并且p的Voronoi鄰居都被剪枝。由Voronoi圖的性質可知，q到p一定經過p的Voronoi鄰接鄰居，假設經過p的Voronoi鄰接鄰居為pi，且pi被剪枝，則必存在Dobs(q,pi)?Dobs(q,p)，則pi支配p，而pi被剪枝，故p也被剪枝，定理得證。

本節提出的剪枝算法的主要思想為：通過定理1～定理3這三個剪枝策略快速剪枝大量非候選點和對查詢無影響的障礙物，獲得候選集Sc。這一過程，首先生成數據點的Voronoi圖，然后計算查詢凸包的區域范圍，再根據定理1～定理3的剪枝策略，滿足條件的數據點被剪枝，剩下未被剪枝的點構成候選集Sc。據以上定理給出如下剪枝算法，如算法1所示。

算法1STA_OSSQ_Filter（Q,P,O）

輸入：數據點集P，查詢集Q，障礙集O。

3.1.2 支配檢查

本節首先根據點與點的可視關系及支配關系給出定理4，然后根據定理4對候選集中的點進行支配

輸出：剪枝后的候選集Sc。判斷，若滿足條件則被剪枝，剩下未被剪枝的點就構成Skyline集Sk。

定理4當點p∈Sc時，且p與查詢點qi之間是可視的，則以qi為圓心，以Deuc(qi,p)為半徑做圓，若在此圓中存在數據點qk，則在qk空間上支配p，則將p剪枝。當p與查詢點qi是不可視時，以qi為圓心，以Dobs(qi,p)為半徑畫圓。同樣，若此圓中存在數據點，則數據點p被剪枝。

證明當點p∈Sc時分兩種情況說明：（1）當點p與查詢點qi可視時，以查詢點qi為圓心，以Deuc(q,pi)為半徑作圓，若在該圓域的相交區域存在數據點pk，則一定存在Deuc(qi,pk)?Deuc(qi,p)，即在障礙空間上pk支配p，p不是空間Skyline點，則將p點刪除。（2）當點p與查詢點qi不可視，則以查詢點qi為圓心，以點p、qi間的障礙距離（即Dobs(qi,p)）為半徑畫圓，若該圓域相交區域中有數據點pk，則一定存在Deuc(qi,pk)?Dobs(qi,p)，則點p被剪枝，pk加入Sk集合中。

基于以上討論，進一步給出支配檢查過程的精煉算法，如算法2所示。

算法2STA_OSSQ_Prune(Sc,Q,O′)。

輸入：候選集Sc，查詢集Q，更新后的障礙集O′。

輸出：空間中不被支配Skyline集合的Sk。

3.2 障礙物環境下動態查詢點的OSSQ查詢

由于現實中查詢點是會改變的，故本節進一步給出障礙環境下動態查詢點的OSSQ查詢方法。

3.2.1 查詢點動態增加情況下的OSSQ查詢

根據增加的查詢點所在的位置不同，主要分為兩種情況：（1）新增查詢點對STA_OSSQ查詢結果沒有影響；（2）新增查詢點改變了查詢區域，則使查詢區域增大可能存在數據點由被支配剪枝變為無支配關系，對STA_OSQ查詢有影響，故需要重新計算關于增加查詢點的Skyline集合。

如圖2所示，原查詢點為{q1,q2,q3}，q4為新增查詢點。在增加q4之前，查詢點集的Skyline點集合為{p1,p6,p7}，增加q4后，Skyline集合變為 {p1,p4,p6,p7}。因為增加q4后，新增加的查詢區域與p4所在的Voronoi單元相交，且不被其他點支配，所以點p4是Skyline點。

Fig.2 Example of dynamically changing of query point圖2 查詢點動態變化示例

假設新增加的查詢點為q′，基于以上的討論給出判定規則1和判定規則2。

判定規則1若點q′在CH(Q)內或在CH(Q)的邊界上（非凸點）時，則對STA_OSSQ查詢沒有影響；若q'?CH(Q)時，則需要重新計算Skyline集合。

判定規則2靜態障礙物環境下的OSSQ查詢結果集是查詢點動態增加的OSSQ查詢的子集，因此對新增候選點進行支配檢查。

根據判定規則1和判定規則2，本節提出的障礙環境下查詢點動態增加的情況下的OSSQ查詢算法的主要思想是：首先判斷新增查詢點的位置，根據判定規則1進行判斷，新增查詢點在CH(Q)內，則直接調用算法1和算法2返回的Skyline點集；若新增查詢點在CH(Q)的外部，接下來對新的查詢凸包以調用算法1，得到候選集S，根據判定規則2，對S調用算法2進行支配檢查，被支配的點刪除，最后剩下的候選點就是查詢點動態增加情況下的查詢結果。

基于以上的討論，進一步給出查詢點動態增加情況下的OSSQ查詢算法，如算法3所示。

算法3DYN_QADD_OSSQ算法(Q,P,O,q')

輸入：查詢點集Q，數據點集P，障礙物集O，新增加的查詢點q'。

輸出：查詢點動態增加情況下的查詢結果集SkNew。

3.2.2 查詢點動態減少情況下的OSSQ查詢

根據被刪除的查詢點所在位置，分為兩種情況討論：（1）被刪除查詢點對靜態查詢點STA_OSSQ查詢結果沒有影響；（2）是有影響。假設被刪除的查詢點為q'，當q'在CH(Q)內時，對查詢區域未產生影響，因此對靜態查詢點STA_OSSQ查詢結果集沒有影響；當q'是CH(Q)的凸點時，刪除后CH(Q)會減小，則查詢點的支配區域會減小，原Skyline點可能變為非Skyline點，需要對Skyline集合進行更新。基于以上的討論給出判定規則3。

判定規則3設被刪除的查詢點為q'，Q為原查詢點集，若q'在CH(Q)內，則刪除q'對STA_OSSQ算法的結果沒有影響；若q'是CH(Q)的凸點，則需要更新查詢集后再進行查詢。

基于判定規則3，本節提出的查詢點動態減少情況下的算法的主要思想是：首先判斷被刪除查詢點的位置，根據判定規則3，將被刪除點是否是CH(Q)的凸點分為兩種情況，若刪除點不是CH(Q)的凸點，則被刪除查詢點對算法1和算法2的查詢結果沒有影響；若刪除點是CH(Q)的凸點，將查詢點集更新后調用算法1和算法2得到查詢點動態減少情況下的查詢結果。

基于上述討論，進一步給出查詢點動態減少情況下的OSSQ算法，如算法4所示。

算法4DYN_QDEL_OSSQ(Q,P,O,q')

輸入：查詢點集Q，數據點集P，障礙物集O，刪除查詢點q'(q'∈Q)。

輸出：Q'的新的Skyline集合SkNew。

4 實驗比較與分析

本章通過實驗對所提算法進行性能評估，實驗中的對比算法為文獻[17]的SOS算法和文獻[13]中在VS2算法基礎上增加障礙物并反復調用該算法檢查數據點所形成的對比算法，即OVS2算法，其主要思想為將障礙物視作由數據點組成，執行VS2算法得出查詢結果，對結果集進行檢查，去除障礙物后再重新調用算法直至得到不含障礙物的結果集。

實驗平臺配置如下：4 GB內存，2.0 GHz CPU，500 GB硬盤，Windows 10操作系統上用Microsoft Visual Studio2013實現。本文使用的數據集來自美國加利福尼亞州空間信息網絡中的數據集中抽取的10 000個節點對象和5 000個線段對象（線段作為障礙物）。查詢集是由數據集中隨機抽取的m個對象點的集合。實驗測試的指標是CPU時間和I/O執行次數，并取執行30次查詢的平均值作為結果。實驗首先對STA_OSSQ算法進行測試，分別測試數據點數量和障礙物數量對CPU執行時間和I/O代價的影響。然后針對動態查詢點環境下的3種算法分別進行測試。

如圖3首先分析數據集大小對CPU執行時間的影響。實驗設定障礙物的數量是1 000，查詢點數量為10。圖中3種算法的CPU執行時間都是隨著數據集的增大而呈上升趨勢。由于OVS2算法需要刪除障礙物重新調用算法，消耗大量的查詢時間。本文提出的STA_OSSQ算法利用Voronoi圖的鄰接特性在剪枝階段和精煉階段有效地過濾掉大量的非候選者，快速地縮小查詢范圍，比SOS算法因數據點的增多在處理MBR消耗的時間更短。故該算法在數據集增大時所花費的執行時間較小。

Fig.3 Effect of dataset scale on CPU time圖3 數據集大小對查詢的CPU時間的影響

圖4給出了障礙物個數對執行時間的影響。實驗中數據點個數為10 000，查詢點為10。由圖可見，OVS2算法執行時間最長，SOS算法和STA_OSSQ算法次之。這是因為這兩種算法需要對障礙物進行調用檢查支配性，這一過程中時間花費較多，而STA_OSSQ算法受到障礙物的影響較小，當障礙物增加時，該算法的優勢更明顯。

Fig.4 Effect of number of obstacles on CPU time圖4 障礙物集大小對CPU執行時間的影響

圖5給出數據集大小對I/O代價的影響。實驗設定障礙物1 000個，查詢點數量為10個。從圖中可以看出3種算法都成上升趨勢。OVS2算法和SOS算法分別對障礙物和MBR距離節點判斷，隨著數據點的增加，算法的I/O代價增加。而STA_OSSQ在約剪數據集利用Voronoi圖的特性有效剪枝大量非候選點，降低了查詢算法的I/O代價，故隨著數據集的增大，該算法的I/O代價增幅緩慢。

Fig.5 Effect of dataset scale on I/O costs圖5 數據集大小對I/O代價的影響

圖6顯示的是障礙物集大小對算法的I/O代價的影響。實驗設定數據點個數為10 000，查詢點為10。圖中3種算法中OVS2算法變化更快，而STA_OSSQ算法的上升趨勢最緩慢。因為OVS2算法隨著障礙物數量增加，對障礙物檢查刪除的I/O時間也增加，而SOS算法在障礙物增加時，處理數據點的MBR的I/O訪問增加。而STA_OSSQ算法在約剪數據集過程中對沒有影響的障礙物進行了處理，故該算法隨著障礙物數量增加I/O代價增加較緩。

Fig.6 Effect of number of obstacles on I/O costs圖6 障礙物集數量對I/O代價的影響

最后對動態查詢點情況下的OSSQ查詢算法的性能進行測試。對OVS2和SOS算法采取重新調用的方式應用于動態查詢點變化情況下，形成對比算法。表1反映了DYN_QADD_OSSQ算法與兩種對比算法在查詢點動態增加的情況下的性能對比。實驗設定數據集規模為10 000個，障礙物集為5 000個，CPU執行時間為執行30次算法的平均時間。當查詢點數量從20變為25時，兩種對比算法的執行時間都大于DYN_QADD_OSSQ算法，故該算法優于其他兩種算法。

Table 1 Performance comparison among DYN_QADD_OSSQ，OVS2and SOS表1 DYN_QADD_OSSQ、OVS2和SOS算法性能比較

表2顯示的是查詢點動態減少情況下的OSSQ查詢算法的性能。對OVS2和SOS算法采取重新調用的方式應用于動態查詢點情況下，形成對比算法。如表2所示，當查詢點數量減少5個后，此兩種對比算法的查詢時間遠多于DYN_QDEL_OSSQ算法，這是由于這兩種對比算法只是單純地重復執行一次；而DYN_QDEL_OSSQ算法會判斷減少的查詢點所在的位置，再分別采取不同的方法，這樣就避免了很多冗余計算。

Table 2 Performance comparison among DYN_QDEL_OSSQ,OVS2and SOS表2 DYN_QDEL_OSSQ，OVS2和SOS算法性能比較

5 結束語

本文研究障礙環境下空間Skyline查詢。形式化定義了障礙空間支配，提出一種基于Voronoi圖的高效剪枝方法，根據Voronoi圖和障礙空間支配的特性，大幅度減少了處理數據點和障礙物的數量，通過支配檢查得到精準的結果集。根據查詢點的狀態，提出了靜態查詢點和查詢點動態情況下的OSSQ算法。通過理論研究和實驗表明，所提出的算法具有更好的性能。未來的研究重點主要集中在路網環境中存在障礙物的空間Skyline查詢方面。