楊澤雪，王阿川，李 陸，李 松

（1.東北林業(yè)大學(xué) 信息與計算機(jī)工程學(xué)院，哈爾濱 150040；2.黑龍江工程學(xué)院 計算機(jī)科學(xué)與技術(shù)系，哈爾濱 150050；3.黑龍江省政務(wù)大數(shù)據(jù)中心，哈爾濱 150028；4.哈爾濱理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080）

0 概述

反 向K 最近鄰（Reverse K-Nearest Neighbor，RKNN）查詢［1］將某查詢點作為K 最近鄰的所有空間數(shù)據(jù)對象，在基于位置的服務(wù)、決策支持、集群和異常值探測、交通網(wǎng)絡(luò)、冒險游戲、分子生物學(xué)等方面具有廣泛應(yīng)用。關(guān)于反向K 最近鄰查詢的研究，學(xué)者提出諸多經(jīng)典算法，主要有靜態(tài)反向最近鄰查詢算法［2-4］、動態(tài)反向最近鄰查詢算法［5-6］、高維反向最近鄰查詢算法［7］、近似反向最近鄰查詢算法［8-9］、并行反向最近鄰查詢算法［10-11］、隱私保護(hù)反向最近鄰查詢算法［12-14］等。但由于以上反向K 最近鄰查詢沒有考慮到數(shù)據(jù)對象的可視性，可能導(dǎo)致已有算法在交互式在線游戲、軍事模擬系統(tǒng)、游客推薦系統(tǒng)等應(yīng)用中不可行，為此需要在空間查詢的研究中考慮可視性。

關(guān)于考慮可視性的空間查詢，NUTANONG 等［15-16］提出可視K 最近鄰（Visual K-Nearest Neighbor，VKNN）查詢，該查詢返回距離查詢點q最近的K 個可視對象，并利用R-樹提出處理VKNN 查詢的POSTPRUNING和PREPRUNING 兩個算法。GAO 等［17］提出查詢點在一條線段上移動的連續(xù)可視最近鄰（Continuous Visible Nearest Neighbor，CVNN）查詢，利用R-樹和分枝限界技術(shù)得到有效的CVNN 查詢處理算法，并提出幾種剪枝規(guī)則提高查詢效率。另一個連續(xù)可視最近鄰查詢算法由WANG 等［18］提出，給出過濾-精煉處理方法，并在過濾階段提出2 個剪枝規(guī)則，通過精煉步驟檢查數(shù)據(jù)對象的確切位置，從而找到最終結(jié)果。XU 等［19］提出組可視最近鄰（Group Visible Nearest Neighbor，GVNN）查詢，提出解決GVNN 查詢的MTO 和TOO 算法，通過定義查詢數(shù)據(jù)集的不可視區(qū)域進(jìn)行數(shù)據(jù)集和障礙集的剪枝，TOO算法只需遍歷一次R-樹即可得到結(jié)果。GAO等［20］提出可視反向K 最近鄰（Visible Reverse K Nearest Neighbor，VRKNN）查詢，該查詢在處理反向K 最近鄰查詢時考慮了障礙物對數(shù)據(jù)對象可視性的影響，提出可視區(qū)域計算算法，有效檢索只對查詢點可視性有影響的障礙，并利用可視區(qū)域計算算法得到VRKNN 查詢處理算法。YANG 等［21］提出連續(xù)可視反向最近鄰（Continuous Visible Reverse Nearest Neighbor，CVRNN）查詢，利用查詢線段的可視性判斷算法和過濾步驟的剪枝規(guī)則，給出處理CVRNN 查詢的過濾-精煉-分裂算法。針對可視性查詢不能處理三維空間對象問題，LIU等［22］提出三維對象基于控制點的連續(xù)可視范圍（Continuous Visible Range Query Based on Control Point，CVRQ-CP）查詢，給出三維對象的可視性判定方法和控制點的定義，并提出CVRQ-CP 查詢處理算法。以上查詢雖然考慮了數(shù)據(jù)對象的可視性，但在增強(qiáng)現(xiàn)實系統(tǒng)、導(dǎo)游系統(tǒng)、視頻監(jiān)控系統(tǒng)等應(yīng)用中需要數(shù)據(jù)對象在某個特定的視域內(nèi)，因此有必要對視域范圍內(nèi)的空間查詢進(jìn)行研究。

在已有文獻(xiàn)中，SUNGMIN 等［23］提出視域最近鄰（View Field Nearest Neighbor，VFNN）查詢，檢索視域范圍內(nèi)距離查詢點最近的數(shù)據(jù)對象，提出連續(xù)視域最近鄰處理方法，并分別給出2 個階段的扇形探索算法和扇形監(jiān)控算法，解決了VFNN 查詢問題。WOOIL 等［24］提出移 動視域 最近鄰（Moving View Field Nearest Neighbor，MVFNN）查詢，該查詢連續(xù)檢索查詢位置和視域變化情況下的最近鄰結(jié)果，定義了地理安全界限和角度安全界限，并基于這2 個定義給出了MVFNN 查詢處理的有效算法。YI等［25］提出反 向視域 最近鄰（Reverse View Field Nearest Neighbor，RVFNN）查詢，及基于扇形R?-樹和原始R?-樹的RVFNN 查詢算法，還構(gòu)建了一個新的數(shù)據(jù)索引結(jié)構(gòu)VFR-樹，并給出基于VFR-樹的RVFNN 查詢處理算法，用實驗驗證基于VFR-樹的RVFNN 查詢算法優(yōu)于前2 種算法。

在上述所有查詢研究中，部分研究僅考慮可視性，或者僅考慮視域范圍，而有些查詢在實際應(yīng)用中可能只對視域范圍內(nèi)可視的數(shù)據(jù)對象感興趣，導(dǎo)致存在適應(yīng)性不高等問題，為此需要同時考慮可視性和視域2 個方面。在相關(guān)文獻(xiàn)中，SU 等［26］提出視域可視K最近鄰（View Field Visible K Nearest Neighbor，V2-KNN）查詢，該查詢檢索視域范圍內(nèi)距離查詢點最近的K 個可視最近鄰，基于網(wǎng)格索引數(shù)據(jù)集和障礙集，結(jié)合剪枝規(guī)則給出了V2-KNN 查詢的處理算法，該查詢同時考慮可視性和視域2 個方面，但只對視域范圍內(nèi)的可視K 最近鄰查詢進(jìn)行處理，忽略了視域范圍內(nèi)的可視反向K 最近鄰查詢處理。

本文在反向K 最近鄰查詢的研究中同時考慮可視性和視域2 個因素，提出一種可視反向視域K 最近鄰（Visible Reverse View Field K Nearest Neighbor，V2-RKNN）查詢算法。定義V2-RKNN 查詢，設(shè)計相應(yīng)的剪枝規(guī)則和視域可視性判斷算法，并分別基于文獻(xiàn)［25］中的R?-樹和VFR-樹給出V2-RKNN 查詢處理算法。

1 相關(guān)定義

定義2［20］（可視性）給定數(shù)據(jù)集P=｛p1，p2，…，pi｝，障礙集O=｛o1，o2，…，oj｝，點p∈P與p′∈P是可視的，需要滿足p與p′之間的連線不會穿過O中任意障礙o，即?o∈O，-----pp'∩o=?。

定義3（視域可視性）給定查詢點q（l，r，θ），數(shù)據(jù)集P=｛p1，p2，…，pi｝，障礙集O=｛o1，o2，…，oj｝，一個數(shù)據(jù)對象p∈P與q是視域可視的，需要滿足p在q的視域范圍內(nèi)、q與p的連線之間不存在障礙o∈O這2 個條件。

定義4［26］（可視距離）給定查詢點q和數(shù)據(jù)對象p，如果p與q是可視的，則p與q之間的可視距離（表示為Vd（q，p））是它們之間的最小歐式距離（即dist（p，q）），否則Vd（q，p）是無窮的。即，

定義5［26］（可視視域K 最近鄰查詢）給定查詢點q（l，r，θ），數(shù)據(jù)集P=｛p1，p2，…，pi｝，障礙集O=｛o1，o2，…，oj｝，可視視域最近鄰查詢檢索P的子集，表示為V2-KNN（q），滿足：

1）|V2-KNN（q）|=k；

2）?p∈V2-KNN（q），p與q是視域可視的；

3）?p∈V2-KNN（q），p'∈PV2-KNN（q），Vd（q，p）≤Vd（q，p'）。

定義6（可視反向視域k最近鄰查詢）給定查詢點q（l，r，θ），數(shù)據(jù)集P=｛p1，p2，…，pi｝，障礙集O=｛o1，o2，…，oj｝，可視反向視域K 最近鄰查詢檢索點集V2-RKNN（q）?P，滿足?p∈V2-RKNN（q），q∈V2-KNN（p），即V2-RKNN（q）=｛p∈P|q∈V2-KNN（p）｝。

圖2 給出了反向視域K 最近鄰查詢和可視反向視域K 最近鄰查詢的實例。

圖1 查詢點q 及其視域Fig.1 Query point q and its view field

圖2 RVFKNN 查詢和V2-RKNN 查詢的實例Fig.2 Example of RVFKNN query and V2-RKNN query

如圖2 所示，數(shù)據(jù)對象p=（l，r，θ），給定一個數(shù)據(jù)對象集合P=｛p1，p2，p3，p4，p5｝和查詢點q，反向視域K最近鄰查詢RVFKNN（q）（k=1）結(jié)果為p3，因為在視域范圍內(nèi)包含查詢點q的數(shù)據(jù)對象為p3和p5，其中p3距離查詢點q最近。雖然p2距離查詢點q較近，但因其視域內(nèi)不包含查詢點q，所以不能成為結(jié)果。

如圖2 所示，加入障礙O=｛o1，o2，o3｝后，可視反向視域K 最近鄰查詢V2-RKNN（q）（k=1）結(jié)果為p5，這是因為p3與查詢點q被障礙o1遮擋，p3與查詢點q是不可視的，所以不能成為查詢結(jié)果。而p5的視域內(nèi)包含查詢點q，p5與查詢點q是可視的，所以p5成為結(jié)果。

2 障礙過濾剪枝

給定障礙集O=｛o1，o2，…，oj｝，由于不是所有障礙都會影響查詢結(jié)果，因此需要對障礙進(jìn)行剪枝。障礙過濾剪枝的具體步驟如下：

1）利用查詢點q進(jìn)行障礙剪枝，將不可能影響查詢結(jié)果的障礙過濾掉，形成初步的障礙過濾集Sofr；

2）對于Sofr中的障礙，只有落入數(shù)據(jù)對象的視域內(nèi)障礙才有可能影響查詢結(jié)果，因此利用數(shù)據(jù)對象的視域進(jìn)行進(jìn)一步剪枝；

3）對于查詢點和某數(shù)據(jù)對象，只有與查詢點和數(shù)據(jù)對象的連接線相交的障礙才對可視性有影響，為此進(jìn)行再次剪枝，得到最終障礙。

2.1 障礙過濾算法

首先利用查詢點q找到對查詢結(jié)果有影響的障礙，剪掉沒有影響的障礙。如圖3 所示，設(shè)障礙集O=｛o1，o2，o3，o4，o5，o6，o7，o8｝，其中o1～o6對查詢點q的可視性有影響，組成的陰影區(qū)域是查詢點q的不可視區(qū)域，落入陰影區(qū)域的障礙o7、o8對查詢點q的可視性沒有影響，因此可以剪掉?？瞻讌^(qū)域構(gòu)成了查詢點q的可視區(qū)域。

圖3 基于查詢點q 的障礙過濾Fig.3 Obstacle filtering based on query point q

障礙過濾算法如算法1 所示，算法1 使用最小堆HO存放未訪問的節(jié)點，最佳優(yōu)先遍歷TO，得到障礙過濾結(jié)果。

算法1Obstacles-filter（q，TO，Sofr）

2.2 視域可視性判斷算法

利用數(shù)據(jù)對象可視性進(jìn)行剪枝，由算法1 得到障礙集Sofr，由于只有落入某數(shù)據(jù)對象視域內(nèi)的障礙才可能影響查詢結(jié)果，因此需要進(jìn)一步剪枝。

圖4 o 落入p 視域內(nèi)的4 種情況Fig.4 Four cases of o is inside p’s view field

剪枝規(guī)則2只有與q和p的連線相交的障礙o會影響q和p的可視性。

根據(jù)剪枝規(guī)則1和2，對障礙過濾結(jié)果Sofr中的障礙進(jìn)行剪枝，得到視域可視性判斷算法，如算法2 所示。

算法2View-Field-Visibility（p，q，Sofr）

3 V2-RKNN 查詢處理算法

為處理V2-RKNN 查詢，需要計算給定查詢點和數(shù)據(jù)對象之間的最小可視距離，進(jìn)行查詢點和數(shù)據(jù)對象之間的可視性判斷，并檢測給定查詢點是否在某數(shù)據(jù)對象的視域范圍內(nèi)。為此，本節(jié)基于R*-樹和VFR-樹，分別給出基于R*-樹和VFR-樹的V2-RKNN查詢處理算法。

3.1 基于R＊-樹的V2-RKNN 查詢處理算法

基于R*-樹的V2-RKNN 查詢算法的思想如下：給定數(shù)據(jù)集P、障礙集O和查詢點q，數(shù)據(jù)集P采用R*-樹索引TP，該方法通過對TP的最佳優(yōu)先遍歷找到距離查詢點最近的數(shù)據(jù)對象，在遍歷樹的過程中需要進(jìn)行可視性判斷并且確定查詢點是否在數(shù)據(jù)對象的視域范圍內(nèi)，滿足條件的則成為結(jié)果。

基于R*-樹的V2-RKNN 查詢處理算法如算法3 所示，算法使用最小堆HP存放未訪問的節(jié)點，節(jié)點按照與查詢點q的最小可視距離升序存放，如果訪問的節(jié)點是中間節(jié)點，則需要判斷其子節(jié)點與查詢點q是否可視，可視則存入堆中；如果訪問的節(jié)點是葉節(jié)點，則需要判斷其中數(shù)據(jù)對象與查詢點q是否可視，可視則存入堆中；如果訪問的是數(shù)據(jù)對象，則需要判斷該數(shù)據(jù)對象的視域范圍內(nèi)是否包含查詢點q，然后判斷數(shù)據(jù)對象與查詢點q的視域可視性，形成候選，最后將候選集中的前k個結(jié)果作為最終結(jié)果。

算法3R*-V2-RKNN（q，TP，O，k）

3.2 基于VFR-樹的V2-RKNN 查詢處理算法

VFR-樹［25］的索引結(jié)構(gòu)類似于R-樹，節(jié)點類型分為葉節(jié)點和非葉節(jié)點，葉節(jié)點包括指向數(shù)據(jù)對象的指針、數(shù)據(jù)對象視域的扇形MBR 和數(shù)據(jù)對象；非葉節(jié)點包括指向子節(jié)點的指針、覆蓋所有子節(jié)點的扇形MBR 和覆蓋所有子節(jié)點的數(shù)據(jù)矩形MBR。圖5所示為VFR-V2-RKNN 算法的實例。

圖5 VFR-V2-RKNN 算法實例Fig.5 Example of VFR-V2-RKNN algorithm

基于VFR-樹的V2-RKNN 查詢處理算法如算法4 所示。

算法4VFR-V2-RKNN（q，TP，O，k）

用圖5 的例子說明算法執(zhí)行過程。在本例中，k=2，P=｛p1，p2，…，p12｝，障礙集O=｛o1，o2，…，o8｝，數(shù)據(jù)對象及障礙如圖5（a）所示，對應(yīng)的VFR-樹如圖5（b）所示。算法采用最小堆HP按照節(jié)點與查詢點q之間的最小距離升序存放未訪問的節(jié)點，Sr按照最小距離升序存放結(jié)果，Sc按照最小距離升序存放候選。

初始時，算法訪問VFR-樹的根節(jié)點，對其子節(jié)點E1、E2進(jìn)行判斷，因為E1、E2沒有完全落入q的不可視區(qū)域，所以判斷E1、E2的扇形MBR 是否包含查詢點q。由于E1、E2的扇形MBR 均包含查詢點q，因此將其插入HP中。E1的數(shù)據(jù)MBR 與q的距離小于E2的數(shù)據(jù)MBR 與q的距離，順序為HP=｛E1，E2｝。接下來訪問節(jié)點E1，其子節(jié)點為E3、E4，因為E3完全落入q的不可視區(qū)域，所以E3不可能成為結(jié)果，故被剪枝。而由于E4沒有完全落入q的不可視區(qū)域，且E4的扇形MBR 包含查詢點q，因此將E4插入HP中，此時HP=｛E4，E2｝。繼續(xù)訪問E4，因為E4是葉節(jié)點，其子節(jié)點p1、p2、p3的數(shù)據(jù)矩形沒有完全落入q的不可視區(qū)域，且p1、p2的數(shù)據(jù)矩形均包含查詢點q，所以將p1、p2插入HP中，此時HP=｛p2，E2，p1｝。繼續(xù)訪問p2，因為p2是數(shù)據(jù)點，p2的視域內(nèi)包含q，且p2與q是視域可視的，所以p2成為候選集Sc中的第1個結(jié)果。此時候選集Sc中數(shù)據(jù)個數(shù)小于k。繼續(xù)訪問E2，其子節(jié)點為E5、E6，因為E5、E6沒有完全落入q的不可視區(qū)域，且E5的扇形MBR 包含查詢點q，所以將E5插入HP中，此時HP=｛E5，p1｝。繼續(xù)訪問E5，因為E5是葉節(jié)點，其子節(jié)點p4、p5、p6的數(shù)據(jù)矩形沒有完全落入q的不可視區(qū)域，且p4的數(shù)據(jù)矩形包含查詢點q，所以將p4插入HP中，此時HP=｛p1，p4｝。繼續(xù)訪問，因為p1是數(shù)據(jù)點，p1的視域內(nèi)包含q，但p1與q是視域不可視的，所以p1不能成為候選集Sc的結(jié)果，p1被剪掉。繼續(xù)訪問p4，p4成為Sc的第2 個結(jié)果，此時候選集Sc中數(shù)據(jù)個數(shù)等于k，｛p2，p4｝成為最終結(jié)果，算法結(jié)束。

算法執(zhí)行過程中堆的內(nèi)容如表1 所示。

表1 算法執(zhí)行過程中堆的內(nèi)容Table 1 Contents of heap during algorithm execution

定理1VFR-V2-RKNN 算法能夠返回正確的結(jié)果，算法的時間復(fù)雜度為O（cloga|TP|+bloga|TO|），其中：loga|TP|為VFR-樹的大??；loga|TO|為障礙R-樹的大??；c為視域范圍內(nèi)定位查詢點的時間；b為候選集的大小。

證明定理1 的正確性：算法通過遍歷VFR-樹獲取距離查詢點最近的并且在其視域范圍內(nèi)包含查詢點的k個可視最近鄰，在樹的遍歷過程中根據(jù)節(jié)點的不同類型進(jìn)行處理，候選集中的數(shù)據(jù)對象經(jīng)過視域可視性算法的判定，若均滿足與查詢點之間是視域可視的，而視域可視性算法是針對過濾障礙集中的障礙根據(jù)剪枝規(guī)則1 和2 進(jìn)一步處理的，剪枝規(guī)則1和2 的正確性可以根據(jù)視域可視性的定義得到，由此證明候選集中的結(jié)果都是正確的。

時間復(fù)雜度分析：算法的時間包括遍歷VFR-樹的時間和遍歷障礙R-樹TO的時間，而算法只需遍歷一次VFR-樹，遍歷一次VFR-樹的時間為loga|TP|。遍歷TO的次數(shù)為b，因為每個候選需要進(jìn)行一次TO的遍歷，所以遍歷TO的時間為bloga|TO|。在VFR-樹的遍歷過程中需要查詢扇形MBR 是否包含查詢點，這個時間為c，因此算法總的時間復(fù)雜度為O（cloga|TP|+bloga|TO|）。

4 實驗結(jié)果及分析

實驗環(huán)境為Intel CORE i5-10400 CPU，2.9 GHz，8 GB 內(nèi)存，1 TB 硬盤，Windows 10 操作系統(tǒng)，用C++語言實現(xiàn)。

實驗數(shù)據(jù)包括模擬數(shù)據(jù)集和真實數(shù)據(jù)集，模擬數(shù)據(jù)集是由隨機(jī)數(shù)生成器產(chǎn)生的數(shù)據(jù)，數(shù)據(jù)分布為Uniform分布和Zipfian分布數(shù)據(jù)集，數(shù)據(jù)集大小為5×103～1×105，障礙集采用http：//chorochronos.Datastories.Org中Greece真實數(shù)據(jù)集，選取River 數(shù)據(jù)集中的5×103～2.5×104條河流的MBR 數(shù)據(jù)作為障礙集。以下實驗中，用UR（Uniform River）表示數(shù)據(jù)集采用Uniform 分布的模擬數(shù)據(jù)集而障礙集采用真實的River 數(shù)據(jù)集；ZR（Zipfian River）表示數(shù)據(jù)集采用Zipfian 分布的模擬數(shù)據(jù)集而障礙集采用真實的River 數(shù)據(jù)集。所有數(shù)據(jù)都被映射在200×200 的數(shù)據(jù)空間中。查詢點從數(shù)據(jù)集中隨機(jī)選取，實驗參數(shù)詳情如表2 所示。

表2 實驗參數(shù)Table 2 Experimental parameters

實驗測試算法執(zhí)行過程中的查詢執(zhí)行時間，每個實驗執(zhí)行100 次，最終結(jié)果取平均值。實驗在不同分布數(shù)據(jù)集上分別比較R*-V2-RKNN 算法和VFR-V2-RKNN 算法的性能。

1）測試數(shù)據(jù)集大小對查詢指標(biāo)的影響。選取數(shù)據(jù)集大小|P|為5×103～1×105，障礙集大小|O|為1×103，k的大小固定為10，圖6 和圖7 分別給出了在UR 和ZR 數(shù)據(jù)集|P|的變化對查詢時間的影響。如圖6 和圖7 所示，隨著|P|的增大，算法R*-V2-RKNN 和VFR-V2-RKNN 的查詢時間呈線性增長，這是因為隨著數(shù)據(jù)量的增大，數(shù)據(jù)集中數(shù)據(jù)的密度增大，導(dǎo)致需要更多次的可視性檢測和視域可視性判斷，視域范圍內(nèi)包含查詢點的數(shù)據(jù)對象增多，而因為VFR-V2-RKNN 在樹的遍歷中的剪枝大大減少了候選集規(guī)模，所以算法VFR-V2-RKNN的查詢性能明顯優(yōu)于算法R*-V2-RKNN。

圖6 UR 數(shù)據(jù)集下|P|的大小對查詢時間的影響Fig.6 Effect of size of|P|on query time under UR date set

圖7 ZR 數(shù)據(jù)集下|P|的大小對查詢時間的影響Fig.7 Effect of size of|P|on query time under ZR date set

2）測試障礙集大小對查詢指標(biāo)的影響。選取數(shù)據(jù)集大小|P|為1×103，障礙集大小|O|為5×103～2.5×104，障礙集中數(shù)據(jù)從River 數(shù)據(jù)集中隨機(jī)選取，k的大小固定為10，圖8 和圖9 分別給出了在UR 和ZR 數(shù)據(jù)集下|O|的變化對查詢時間的影響。如圖8 和圖9 所示，隨著|O|的增大，算法R*-V2-RKNN 和VFR-V2-RKNN 的查詢時間呈線性增長，這是因為隨著障礙數(shù)量的增大，視域范圍內(nèi)障礙的密度不斷增大，這就需要在可視性檢測中處理更多的障礙，且視域可視性判斷的次數(shù)也會增加，而算法VFR-V2-RKNN 的查詢性能明顯優(yōu)于R*-V2-RKNN 算法，這是因為VFR-V2-RKNN 算法的剪枝規(guī)則減少了處理的數(shù)據(jù)量，在障礙增多的情況下視域可視性檢測的時間會增長，但增長幅度明顯小于R*-V2-RKNN 算法。

圖8 UR 數(shù)據(jù)集下|O|的大小對查詢時間的影響Fig.8 Effect of size of|O|on query time under UR date set

圖9 ZR 數(shù)據(jù)集下|O|的大小對查詢時間的影響Fig.9 Effect of size of|O|on query time under ZR date set

3）測試k值的變化對查詢指標(biāo)的影響。基于UR數(shù)據(jù)集進(jìn)行實驗，選取數(shù)據(jù)集大小|P|為1×103，障礙集大小|O|為1×103，圖10 給出了k值的變化對查詢時間的影響。如圖10 所示，隨著k值的增大，算法R*-V2-RKNN 和VFR-V2-RKNN 的查詢時間逐漸增大。這是因為隨著k值的增大，可視性判斷的次數(shù)增加。算法R*-V2-RKNN 的查詢時間增長幅度明顯大于算法VFR-V2-RKNN，原因是前者需要檢測數(shù)據(jù)對象查詢視域范圍內(nèi)是否包含查詢點。對于R*-V2-RKNN 來說，因為R*-樹中不包含扇形MBR，不能對中間節(jié)點進(jìn)行剪枝，所以隨著k值的增大，查詢時間急劇增長，而VFR-V2-RKNN 算法使用的VFR-樹能夠?qū)Σ话樵凕c的節(jié)點進(jìn)行有效剪枝，查詢性能明顯優(yōu)于R*-V2-RKNN 算法。

圖10 UR 數(shù)據(jù)集下k 值變化對查詢時間的影響Fig.10 Effect of k value on query time under UR date set

基于ZR 數(shù)據(jù)集進(jìn)行實驗，選取數(shù)據(jù)集大小|P|為1×103，障礙集大小|O|為1×103，查詢點q從密集區(qū)域數(shù)據(jù)對象中選取，圖11 給出了k值的大小對查詢時間的影響。如圖11 所示，隨著k值的增大，算法R*-V2-RKNN 和VFR-V2-RKNN 的查詢時間逐漸增大，這是因為隨著k值的增大，可視性判斷的次數(shù)增加。但是算法在ZR 數(shù)據(jù)集上的查詢性能明顯低于UR 數(shù)據(jù)集，原因是數(shù)據(jù)集密集，訪問數(shù)據(jù)量明顯增大，包含在對象視域范圍內(nèi)的數(shù)據(jù)對象將明顯增加，由于算法VFR-V2-RKNN 基于剪枝規(guī)則，因此查詢查詢性能明顯優(yōu)于R*-V2-RKNN。

圖11 ZR 數(shù)據(jù)集上k 值變化對查詢時間的影響（密集查詢點）Fig.11 Effect of k value on query time under ZR date set（dense query point）

基于ZR 數(shù)據(jù)集進(jìn)行實驗，選取數(shù)據(jù)集大小|P|為1×103，障礙集大小|O|為1×103，查詢點q從稀疏區(qū)域數(shù)據(jù)對象中選取，圖12 給出了k值的大小對查詢時間的影響。

圖12 ZR 數(shù)據(jù)集下k 值變化對查詢時間的影響（稀疏查詢點）Fig.12 Effect of k value on query time under ZR date set（sparse query point）

如圖12 所示，隨著k值的增大，算法R*-V2-RKNN和VFR-V2-RKNN 的查詢時間逐漸增大，這是因為隨著k值的增大，可視性判斷的次數(shù)增加。此實驗結(jié)果跟UR 數(shù)據(jù)集類似，但查詢時間增長幅度明顯大于UR 數(shù)據(jù)集，這是因為隨著k的增大，如果查詢結(jié)果的數(shù)量小于k，則R*-V2-RKNN 算法需要訪問的節(jié)點數(shù)量基本等于查詢數(shù)據(jù)集的節(jié)點數(shù)，所以查詢時間劇增，而VFR-V2-RKNN 算法使用的VFR-樹能夠?qū)Σ话樵凕c的節(jié)點進(jìn)行有效剪枝，查詢性能明顯優(yōu)于R*-V2-RKNN算法。

5 結(jié)束語

本文提出一種可視反向視域K 最近鄰查詢算法，將可視性和視域范圍同時引入到RKNN 查詢中，能夠增強(qiáng)現(xiàn)實系統(tǒng)、導(dǎo)游系統(tǒng)和視頻監(jiān)控系統(tǒng)中的反向最近鄰查詢。結(jié)合障礙過濾算法和2 個障礙剪枝規(guī)則給出視域可視性判斷算法，并分別基于R*-樹和VFR-樹得到R*-V2-RKNN 和VFR-V2-RKNN 算法。在真實數(shù)據(jù)集和模擬數(shù)據(jù)集下的實驗結(jié)果表明，VFR-V2-RKNN的性能明顯優(yōu)于R*-V2-RKNN。下一步將研究連續(xù)可視反向視域最近鄰查詢，即考慮數(shù)據(jù)點移動情況下的可視反向視域最近鄰查詢。