障礙環境中可視反向視域K 最近鄰查詢

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

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

0 概述

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

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

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

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

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

1 相關定義

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

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

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

定義5［26］（可視視域K 最近鄰查詢）給定查詢點q（l，r，θ），數據集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，θ），數據集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 所示，數據對象p=（l，r，θ），給定一個數據對象集合P=｛p1，p2，p3，p4，p5｝和查詢點q，反向視域K最近鄰查詢RVFKNN（q）（k=1）結果為p3，因為在視域范圍內包含查詢點q的數據對象為p3和p5，其中p3距離查詢點q最近。雖然p2距離查詢點q較近，但因其視域內不包含查詢點q，所以不能成為結果。

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

2 障礙過濾剪枝

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

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

2）對于Sofr中的障礙，只有落入數據對象的視域內障礙才有可能影響查詢結果，因此利用數據對象的視域進行進一步剪枝；

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

2.1 障礙過濾算法

首先利用查詢點q找到對查詢結果有影響的障礙，剪掉沒有影響的障礙。如圖3 所示，設障礙集O=｛o1，o2，o3，o4，o5，o6，o7，o8｝，其中o1～o6對查詢點q的可視性有影響，組成的陰影區域是查詢點q的不可視區域，落入陰影區域的障礙o7、o8對查詢點q的可視性沒有影響，因此可以剪掉。空白區域構成了查詢點q的可視區域。

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

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

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

2.2 視域可視性判斷算法

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

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

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

根據剪枝規則1和2，對障礙過濾結果Sofr中的障礙進行剪枝，得到視域可視性判斷算法，如算法2 所示。

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

3 V2-RKNN 查詢處理算法

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

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

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

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

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

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

VFR-樹［25］的索引結構類似于R-樹，節點類型分為葉節點和非葉節點，葉節點包括指向數據對象的指針、數據對象視域的扇形MBR 和數據對象；非葉節點包括指向子節點的指針、覆蓋所有子節點的扇形MBR 和覆蓋所有子節點的數據矩形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 的例子說明算法執行過程。在本例中，k=2，P=｛p1，p2，…，p12｝，障礙集O=｛o1，o2，…，o8｝，數據對象及障礙如圖5（a）所示，對應的VFR-樹如圖5（b）所示。算法采用最小堆HP按照節點與查詢點q之間的最小距離升序存放未訪問的節點，Sr按照最小距離升序存放結果，Sc按照最小距離升序存放候選。

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

算法執行過程中堆的內容如表1 所示。

表1 算法執行過程中堆的內容Table 1 Contents of heap during algorithm execution

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

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

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

4 實驗結果及分析

實驗環境為Intel CORE i5-10400 CPU，2.9 GHz，8 GB 內存，1 TB 硬盤，Windows 10 操作系統，用C++語言實現。

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

表2 實驗參數Table 2 Experimental parameters

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

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

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

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

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

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

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

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

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

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

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

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

圖12 ZR 數據集下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值的增大，可視性判斷的次數增加。此實驗結果跟UR 數據集類似，但查詢時間增長幅度明顯大于UR 數據集，這是因為隨著k的增大，如果查詢結果的數量小于k，則R*-V2-RKNN 算法需要訪問的節點數量基本等于查詢數據集的節點數，所以查詢時間劇增，而VFR-V2-RKNN 算法使用的VFR-樹能夠對不包含查詢點的節點進行有效剪枝，查詢性能明顯優于R*-V2-RKNN算法。

5 結束語

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