障碍环境中可视反向视域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。下一步将研究连续可视反向视域最近邻查询，即考虑数据点移动情况下的可视反向视域最近邻查询。