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

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

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

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

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

2 基礎(chǔ)定義

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

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

根據(jù)文獻(xiàn)[13]的空間支配的定義，結(jié)合文獻(xiàn)[18]的點(diǎn)與點(diǎn)之間的障礙距離定義，本文提出障礙空間支配的定義如定義3所示。

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

3 算法描述

3.1 靜態(tài)查詢點(diǎn)環(huán)境下的OSSQ查詢

本節(jié)提出的靜態(tài)查詢點(diǎn)STA_OSSQ查詢方法主要分為兩個(gè)主要步驟：約剪數(shù)據(jù)集和支配檢查。約剪數(shù)據(jù)集通過3個(gè)定理剪枝非候選數(shù)據(jù)點(diǎn)，然后支配檢查候選集得到最終的空間Skyline集合。

3.1.1 約剪數(shù)據(jù)集

約剪數(shù)據(jù)集過程首先對數(shù)據(jù)點(diǎn)構(gòu)建Voronoi圖，對查詢點(diǎn)建立一個(gè)查詢的凸包，然后利用Voronoi圖的鄰接性質(zhì)、數(shù)據(jù)點(diǎn)與查詢點(diǎn)及其查詢區(qū)域形成的障礙距離來剪枝掉大量數(shù)據(jù)點(diǎn)，剩下的未被剪枝的數(shù)據(jù)點(diǎn)構(gòu)成候選點(diǎn)集合。

定理1若點(diǎn)p在查詢凸包Q內(nèi)，則點(diǎn)p支配各查詢點(diǎn)與該點(diǎn)所成圓域區(qū)域外的點(diǎn)，則區(qū)域外的點(diǎn)被剪枝。

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

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

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

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

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

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

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

算法1STA_OSSQ_Filter（Q,P,O）

輸入：數(shù)據(jù)點(diǎn)集P，查詢集Q，障礙集O。

3.1.2 支配檢查

本節(jié)首先根據(jù)點(diǎn)與點(diǎn)的可視關(guān)系及支配關(guān)系給出定理4，然后根據(jù)定理4對候選集中的點(diǎn)進(jìn)行支配

輸出：剪枝后的候選集Sc。判斷，若滿足條件則被剪枝，剩下未被剪枝的點(diǎn)就構(gòu)成Skyline集Sk。

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

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

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

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

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

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

3.2 障礙物環(huán)境下動(dòng)態(tài)查詢點(diǎn)的OSSQ查詢

由于現(xiàn)實(shí)中查詢點(diǎn)是會(huì)改變的，故本節(jié)進(jìn)一步給出障礙環(huán)境下動(dòng)態(tài)查詢點(diǎn)的OSSQ查詢方法。

3.2.1 查詢點(diǎn)動(dòng)態(tài)增加情況下的OSSQ查詢

根據(jù)增加的查詢點(diǎn)所在的位置不同，主要分為兩種情況：（1）新增查詢點(diǎn)對STA_OSSQ查詢結(jié)果沒有影響；（2）新增查詢點(diǎn)改變了查詢區(qū)域，則使查詢區(qū)域增大可能存在數(shù)據(jù)點(diǎn)由被支配剪枝變?yōu)闊o支配關(guān)系，對STA_OSQ查詢有影響，故需要重新計(jì)算關(guān)于增加查詢點(diǎn)的Skyline集合。

如圖2所示，原查詢點(diǎn)為{q1,q2,q3}，q4為新增查詢點(diǎn)。在增加q4之前，查詢點(diǎn)集的Skyline點(diǎn)集合為{p1,p6,p7}，增加q4后，Skyline集合變?yōu)?{p1,p4,p6,p7}。因?yàn)樵黾觪4后，新增加的查詢區(qū)域與p4所在的Voronoi單元相交，且不被其他點(diǎn)支配，所以點(diǎn)p4是Skyline點(diǎn)。

Fig.2 Example of dynamically changing of query point圖2 查詢點(diǎn)動(dòng)態(tài)變化示例

假設(shè)新增加的查詢點(diǎn)為q′，基于以上的討論給出判定規(guī)則1和判定規(guī)則2。

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

判定規(guī)則2靜態(tài)障礙物環(huán)境下的OSSQ查詢結(jié)果集是查詢點(diǎn)動(dòng)態(tài)增加的OSSQ查詢的子集，因此對新增候選點(diǎn)進(jìn)行支配檢查。

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

基于以上的討論，進(jìn)一步給出查詢點(diǎn)動(dòng)態(tài)增加情況下的OSSQ查詢算法，如算法3所示。

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

輸入：查詢點(diǎn)集Q，數(shù)據(jù)點(diǎn)集P，障礙物集O，新增加的查詢點(diǎn)q'。

輸出：查詢點(diǎn)動(dòng)態(tài)增加情況下的查詢結(jié)果集SkNew。

3.2.2 查詢點(diǎn)動(dòng)態(tài)減少情況下的OSSQ查詢

根據(jù)被刪除的查詢點(diǎn)所在位置，分為兩種情況討論：（1）被刪除查詢點(diǎn)對靜態(tài)查詢點(diǎn)STA_OSSQ查詢結(jié)果沒有影響；（2）是有影響。假設(shè)被刪除的查詢點(diǎn)為q'，當(dāng)q'在CH(Q)內(nèi)時(shí)，對查詢區(qū)域未產(chǎn)生影響，因此對靜態(tài)查詢點(diǎn)STA_OSSQ查詢結(jié)果集沒有影響；當(dāng)q'是CH(Q)的凸點(diǎn)時(shí)，刪除后CH(Q)會(huì)減小，則查詢點(diǎn)的支配區(qū)域會(huì)減小，原Skyline點(diǎn)可能變?yōu)榉荢kyline點(diǎn)，需要對Skyline集合進(jìn)行更新?；谝陨系挠懻摻o出判定規(guī)則3。

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

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

基于上述討論，進(jìn)一步給出查詢點(diǎn)動(dòng)態(tài)減少情況下的OSSQ算法，如算法4所示。

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

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

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

4 實(shí)驗(yàn)比較與分析

本章通過實(shí)驗(yàn)對所提算法進(jìn)行性能評(píng)估，實(shí)驗(yàn)中的對比算法為文獻(xiàn)[17]的SOS算法和文獻(xiàn)[13]中在VS2算法基礎(chǔ)上增加障礙物并反復(fù)調(diào)用該算法檢查數(shù)據(jù)點(diǎn)所形成的對比算法，即OVS2算法，其主要思想為將障礙物視作由數(shù)據(jù)點(diǎn)組成，執(zhí)行VS2算法得出查詢結(jié)果，對結(jié)果集進(jìn)行檢查，去除障礙物后再重新調(diào)用算法直至得到不含障礙物的結(jié)果集。

實(shí)驗(yàn)平臺(tái)配置如下：4 GB內(nèi)存，2.0 GHz CPU，500 GB硬盤，Windows 10操作系統(tǒng)上用Microsoft Visual Studio2013實(shí)現(xiàn)。本文使用的數(shù)據(jù)集來自美國加利福尼亞州空間信息網(wǎng)絡(luò)中的數(shù)據(jù)集中抽取的10 000個(gè)節(jié)點(diǎn)對象和5 000個(gè)線段對象（線段作為障礙物）。查詢集是由數(shù)據(jù)集中隨機(jī)抽取的m個(gè)對象點(diǎn)的集合。實(shí)驗(yàn)測試的指標(biāo)是CPU時(shí)間和I/O執(zhí)行次數(shù)，并取執(zhí)行30次查詢的平均值作為結(jié)果。實(shí)驗(yàn)首先對STA_OSSQ算法進(jìn)行測試，分別測試數(shù)據(jù)點(diǎn)數(shù)量和障礙物數(shù)量對CPU執(zhí)行時(shí)間和I/O代價(jià)的影響。然后針對動(dòng)態(tài)查詢點(diǎn)環(huán)境下的3種算法分別進(jìn)行測試。

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

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

圖4給出了障礙物個(gè)數(shù)對執(zhí)行時(shí)間的影響。實(shí)驗(yàn)中數(shù)據(jù)點(diǎn)個(gè)數(shù)為10 000，查詢點(diǎn)為10。由圖可見，OVS2算法執(zhí)行時(shí)間最長，SOS算法和STA_OSSQ算法次之。這是因?yàn)檫@兩種算法需要對障礙物進(jìn)行調(diào)用檢查支配性，這一過程中時(shí)間花費(fèi)較多，而STA_OSSQ算法受到障礙物的影響較小，當(dāng)障礙物增加時(shí)，該算法的優(yōu)勢更明顯。

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

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

Fig.5 Effect of dataset scale on I/O costs圖5 數(shù)據(jù)集大小對I/O代價(jià)的影響

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

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

最后對動(dòng)態(tài)查詢點(diǎn)情況下的OSSQ查詢算法的性能進(jìn)行測試。對OVS2和SOS算法采取重新調(diào)用的方式應(yīng)用于動(dòng)態(tài)查詢點(diǎn)變化情況下，形成對比算法。表1反映了DYN_QADD_OSSQ算法與兩種對比算法在查詢點(diǎn)動(dòng)態(tài)增加的情況下的性能對比。實(shí)驗(yàn)設(shè)定數(shù)據(jù)集規(guī)模為10 000個(gè)，障礙物集為5 000個(gè)，CPU執(zhí)行時(shí)間為執(zhí)行30次算法的平均時(shí)間。當(dāng)查詢點(diǎn)數(shù)量從20變?yōu)?5時(shí)，兩種對比算法的執(zhí)行時(shí)間都大于DYN_QADD_OSSQ算法，故該算法優(yōu)于其他兩種算法。

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

表2顯示的是查詢點(diǎn)動(dòng)態(tài)減少情況下的OSSQ查詢算法的性能。對OVS2和SOS算法采取重新調(diào)用的方式應(yīng)用于動(dòng)態(tài)查詢點(diǎn)情況下，形成對比算法。如表2所示，當(dāng)查詢點(diǎn)數(shù)量減少5個(gè)后，此兩種對比算法的查詢時(shí)間遠(yuǎn)多于DYN_QDEL_OSSQ算法，這是由于這兩種對比算法只是單純地重復(fù)執(zhí)行一次；而DYN_QDEL_OSSQ算法會(huì)判斷減少的查詢點(diǎn)所在的位置，再分別采取不同的方法，這樣就避免了很多冗余計(jì)算。

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

5 結(jié)束語

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