开放科学（资源服务）标志码（OSID）：

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 相关定义

定义1^[23]（查询点及其视域）  查询点q表示三元组（l，r，θ）。其中：l=（x，y）表示q的位置；r表示用户的最大可视距离；θ表示q的视域角。θ =（$ {\theta }_{q}^{⊢} $，$ {\theta }_{q}^{⊣} $）由2个角$ {\theta }_{q}^{⊢} $和$ {\theta }_{q}^{⊣} $组合而成，$ {\theta }_{q}^{⊢} $和$ {\theta }_{q}^{⊣} $分别是θ基于x轴正方向的起始角和结束角。

图 1所示为查询点q及其视域、视域角θ、$ {\theta }_{q}^{⊢} $、$ {\theta }_{q}^{⊣} $的示意图，其中阴影部分为查询点q的视域。

定义2^[20]（可视性）  给定数据集P={p₁，p₂，…，p_i}，障碍集O={o₁，o₂，…，o_j}，点p∈P与p′∈P是可视的，需要满足p与p′之间的连线不会穿过O中任意障碍o，即∀o∈O，$ \overline{p{p}^{\text{'}}}\bigcap $o=$ \mathrm{\varnothing } $。

定义3（视域可视性）  给定查询点q（l，r，θ），数据集P={p₁，p₂，…，p_i}，障碍集O={o₁，o₂，…，o_j}，一个数据对象p∈P与q是视域可视的，需要满足p在q的视域范围内、q与p的连线之间不存在障碍o∈O这2个条件。

定义4^[26]（可视距离）  给定查询点q和数据对象p，如果p与q是可视的，则p与q之间的可视距离（表示为V_d（q，p））是它们之间的最小欧式距离（即dist（p，q）），否则V_d（q，p）是无穷的。即，

$ V_{d}（q\text{，}p）= \left\{\begin{array}{l}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\left(q, p\right), p\mathrm{与}q\mathrm{是}\mathrm{可}\mathrm{视}\mathrm{的}\\ \mathrm{\infty }, \mathrm{其}\mathrm{他}\end{array}\right. $

定义5^[26]（可视视域K最近邻查询）  给定查询点q（l，r，θ），数据集P={p₁，p₂，…，p_i}，障碍集O={o₁，o₂，…，o_j}，可视视域最近邻查询检索P的子集，表示为V2-KNN（q），满足：

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

2）∀p∈V2-KNN（q），p与q是视域可视的；

3）∀p∈V2-KNN（q），$ {p}^{\text{'}} $∈P\V2-KNN（q），V_d（q，p）≤ V_d（q，$ {p}^{\text{'}} $）。

定义6（可视反向视域k最近邻查询）  给定查询点q（l，r，θ），数据集P={p₁，p₂，…，p_i}，障碍集O={o₁，o₂，…，o_j}，可视反向视域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最近邻查询的实例。

如图 2所示，数据对象p=（l，r，θ），给定一个数据对象集合P={p₁，p₂，p₃，p₄，p₅}和查询点q，反向视域K最近邻查询RVFKNN（q）（k=1）结果为p₃，因为在视域范围内包含查询点q的数据对象为p₃和p₅，其中p₃距离查询点q最近。虽然p₂距离查询点q较近，但因其视域内不包含查询点q，所以不能成为结果。

如图 2所示，加入障碍O={o₁，o₂，o₃}后，可视反向视域K最近邻查询V2-RKNN（q）（k=1）结果为p₅，这是因为p₃与查询点q被障碍o₁遮挡，p₃与查询点q是不可视的，所以不能成为查询结果。而p₅的视域内包含查询点q，p₅与查询点q是可视的，所以p₅成为结果。

2 障碍过滤剪枝

给定障碍集O={o₁，o₂，…，o_j}，由于不是所有障碍都会影响查询结果，因此需要对障碍进行剪枝。障碍过滤剪枝的具体步骤如下：

1）利用查询点q进行障碍剪枝，将不可能影响查询结果的障碍过滤掉，形成初步的障碍过滤集S_ofr；

2）对于S_ofr中的障碍，只有落入数据对象的视域内障碍才有可能影响查询结果，因此利用数据对象的视域进行进一步剪枝；

3）对于查询点和某数据对象，只有与查询点和数据对象的连接线相交的障碍才对可视性有影响，为此进行再次剪枝，得到最终障碍。

2.1 障碍过滤算法

首先利用查询点q找到对查询结果有影响的障碍，剪掉没有影响的障碍。如图 3所示，设障碍集O={o₁，o₂，o₃，o₄，o₅，o₆，o₇，o₈}，其中o₁~o₆对查询点q的可视性有影响，组成的阴影区域是查询点q的不可视区域，落入阴影区域的障碍o₇、o₈对查询点q的可视性没有影响，因此可以剪掉。空白区域构成了查询点q的可视区域。

障碍过滤算法如算法1所示，算法1使用最小堆H_O存放未访问的节点，最佳优先遍历T_O，得到障碍过滤结果。

算法1  Obstacles-filter（q，T_O，S_ofr）

输入  查询点q，障碍集O的R-树T_O

输出  S_ofr（障碍过滤结果）

begin

  H_O=$ \mathrm{\varnothing } $；

  S_ofr=$ \mathrm{\varnothing } $；

  Enheap（H_O，T_O的树根）；

  while H_O≠∅ do

    e$ \leftarrow $Deheap（H_O）；

    if e是一个障碍then

        if e与q是可视的then

          S_ofr= S_ofr+{e}；

    else

        for each e_i∈e do

          if e_i与q是可视的then

                Enheap（H_O，e_i）；

  return S_ofr；

end

2.2 视域可视性判断算法

利用数据对象可视性进行剪枝，由算法1得到障碍集S_ofr，由于只有落入某数据对象视域内的障碍才可能影响查询结果，因此需要进一步剪枝。

剪枝规则1^[26]  如图 4所示，给定障碍o和数据对象p，θ_p，o.min及θ_p，o.max分别表示障碍o关于数据对象p的最小角和最大角，如果障碍o落入数据对象p的视域内，则障碍o一定满足p与o的最小距离小于或等于r，且$ {\theta }_{p}^{⊢} $、$ {\theta }_{p}^{⊣} $、θ_p，o.min、θ_p，o.max满足以下4种情况之一：

1）$ {\theta }_{p}^{⊢} $≤θ_p，o.min≤$ {\theta }_{p}^{⊣} $且θ_p，o.max > $ {\theta }_{p}^{⊣} $（如图 4（a）所示）；

2）$ {\theta }_{p}^{⊢} $≤θ_p，o.max≤$ {\theta }_{p}^{⊣} $且θ_p，o.min≤$ {\theta }_{p}^{⊢} $（如图 4（b）所示）；

3）$ {\theta }_{p}^{⊢} $≤θ_p，o.min≤$ {\theta }_{p}^{⊣} $且$ {\theta }_{p}^{⊢} $≤θ_p，o.max≤$ {\theta }_{p}^{⊣} $（如图 4（c）所示）；

4）θ_p，o.max > $ {\theta }_{p}^{⊣} $且θ_p，o.min≤$ {\theta }_{p}^{⊢} $（如图 4（d）所示）。

剪枝规则2  只有与q和p的连线相交的障碍o会影响q和p的可视性。

根据剪枝规则1和2，对障碍过滤结果S_ofr中的障碍进行剪枝，得到视域可视性判断算法，如算法2所示。

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

输入  障碍过滤结果S_ofr，查询点q，数据对象p

输出  p关于q的视域可视性V_pq

begin

  for each障碍o in S_ofr do

    if o不在p的视域范围内then

      S_ofr = S_ofr -{o}；//剪枝规则1

    else

      if o与q和p的连线不相交then

        S_ofr = S_ofr -{o}；//剪枝规则2

  V_pq=True；

  If S_ofr≠$ \mathrm{\varnothing } $ then

    V_pq=False；

  return V_pq；

end

3 V2-RKNN查询处理算法

为处理V2-RKNN查询，需要计算给定查询点和数据对象之间的最小可视距离，进行查询点和数据对象之间的可视性判断，并检测给定查询点是否在某数据对象的视域范围内。为此，本节基于R^*-树和VFR-树，分别给出基于R^*-树和VFR-树的V2-RKNN查询处理算法。

3.1 基于R^*-树的V2-RKNN查询处理算法

基于R^*-树的V2-RKNN查询算法的思想如下：给定数据集P、障碍集O和查询点q，数据集P采用R^*-树索引T_P，该方法通过对T_P的最佳优先遍历找到距离查询点最近的数据对象，在遍历树的过程中需要进行可视性判断并且确定查询点是否在数据对象的视域范围内，满足条件的则成为结果。

基于R^*-树的V2-RKNN查询处理算法如算法3所示，算法使用最小堆H_P存放未访问的节点，节点按照与查询点q的最小可视距离升序存放，如果访问的节点是中间节点，则需要判断其子节点与查询点q是否可视，可视则存入堆中；如果访问的节点是叶节点，则需要判断其中数据对象与查询点q是否可视，可视则存入堆中；如果访问的是数据对象，则需要判断该数据对象的视域范围内是否包含查询点q，然后判断数据对象与查询点q的视域可视性，形成候选，最后将候选集中的前k个结果作为最终结果。

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

输入  查询点q（l，r，θ），数据集P={p₁，p₂，…，p_i}的R^*-树T_P，障碍集O={o₁，o₂，…，o_j}，RKNN的k值

输出  V2-RKNN结果集合S_r

begin

  H_P=∅；

  S_r=∅，S_c=∅；

  Enheap（H_P，T_P的树根）；

  Obstacles-filter（q，T_O，S_ofr）；

  while H_P≠∅ do

    e$ \leftarrow $Deheap（H_P）；

    if e是数据对象then

      if e的视域范围内包含查询点q then

        if View-Field-Visibility（e，q，S_ofr）=True

        then

          S_c=S_c+{e}；

          if |S_c|≥k then

            kNN_dist=V_d（q，S_c中的第k个结果）；

            if H_P≠∅ or kNN_dist≤H_P中第一个对象的键值

            then

                S_r=S_r+{S_c中的前k个元素}；

            return S_r；

  else if e是叶节点then

    for each数据对象e_i∈e do

    if e_i没有完全落入q的不可视区域

    then

          Enheap（H_P，e_i）；//包含数据对象与q的最小可视距离

else

  for each子节点e_i∈e do

    if e_i没有完全落入q的不可视区域then

      Enheap（H_P，e_i）；//包含e_i与q的最小可视距离

end

3.2 基于VFR-树的V2-RKNN查询处理算法

VFR-树^[25]的索引结构类似于R-树，节点类型分为叶节点和非叶节点，叶节点包括指向数据对象的指针、数据对象视域的扇形MBR和数据对象；非叶节点包括指向子节点的指针、覆盖所有子节点的扇形MBR和覆盖所有子节点的数据矩形MBR。图 5所示为VFR-V2-RKNN算法的实例。

基于VFR-树的V2-RKNN查询处理算法如算法4所示。

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

输入  查询点q（l，r，θ），数据集P={p₁，p₂，…，p_i} 的VFR-树T_P，障碍集O={o₁，o₂，…，o_j}，RKNN的k值

输出  V2-RKNN结果集合S_r

begin

  H_P=∅；

  S_r =∅，S_c=∅；

  Enheap（H_P，T_P的树根）；

  Obstacles-filter（q，T_O，S_ofr）；

  while H_P≠∅ do

    e$ \leftarrow $Deheap（H_P）；

    if e是数据对象then

      if e的视域范围内包含查询点q then

        if View-Field-Visibility（e，q，S_ofr）=True

        then

            S_c=S_c+{e}；

            iif | S_c |≥k then

              kNN_dist=V_d（q，S_c中的第k个结果）；

              if H_P≠∅ or kNN_dist≤H_P中第一个对象的键值the

              S_r=S_r+{ S_c中的前k个元素}；

              return S_r；

  else if e是叶节点then

    for each子节点e_i∈e do

      if e_i没有完全落入q的不可视区域

      then

        if e_i的数据MBR包含查询点q then

          Enheap（H_P，e_i）；//包含数据对象与q的最小

//可视距离

else

  for each非叶子节点e_i∈e do

    if e_i没有完全落入q的不可视区域then

      if e_i.扇形MBR包含q

      then

        Enheap（H_P，e_i）；//包含数据对象与q的最小

//可视距离

end

用图 5的例子说明算法执行过程。在本例中，k=2，P={p₁，p₂，…，p₁₂}，障碍集O={o₁，o₂，…，o₈}，数据对象及障碍如图 5（a）所示，对应的VFR-树如图 5（b）所示。算法采用最小堆H_P按照节点与查询点q之间的最小距离升序存放未访问的节点，S_r按照最小距离升序存放结果，S_c按照最小距离升序存放候选。

初始时，算法访问VFR-树的根节点，对其子节点E₁、E₂进行判断，因为E₁、E₂没有完全落入q的不可视区域，所以判断E₁、E₂的扇形MBR是否包含查询点q。由于E₁、E₂的扇形MBR均包含查询点q，因此将其插入H_P中。E₁的数据MBR与q的距离小于E₂的数据MBR与q的距离，顺序为H_P={E₁，E₂}。接下来访问节点E₁，其子节点为E₃、E₄，因为E₃完全落入q的不可视区域，所以E₃不可能成为结果，故被剪枝。而由于E₄没有完全落入q的不可视区域，且E₄的扇形MBR包含查询点q，因此将E₄插入H_P中，此时H_P={E₄，E₂}。继续访问E₄，因为E₄是叶节点，其子节点p₁、p₂、p₃的数据矩形没有完全落入q的不可视区域，且p₁、p₂的数据矩形均包含查询点q，所以将p₁、p₂插入H_P中，此时H_P={ p₂，E₂，p₁}。继续访问p₂，因为p₂是数据点，p₂的视域内包含q，且p₂与q是视域可视的，所以p₂成为候选集S_c中的第1个结果。此时候选集S_c中数据个数小于k。继续访问E₂，其子节点为E₅、E₆，因为E₅、E₆没有完全落入q的不可视区域，且E₅的扇形MBR包含查询点q，所以将E₅插入H_P中，此时H_P={E₅，p₁}。继续访问E₅，因为E₅是叶节点，其子节点p₄、p₅、p₆的数据矩形没有完全落入q的不可视区域，且p₄的数据矩形包含查询点q，所以将p₄插入H_P中，此时H_P={p₁，p₄}。继续访问，因为p₁是数据点，p₁的视域内包含q，但p₁与q是视域不可视的，所以p₁不能成为候选集S_c的结果，p₁被剪掉。继续访问p₄，p₄成为S_c的第2个结果，此时候选集S_c中数据个数等于k，{p₂，p₄}成为最终结果，算法结束。

算法执行过程中堆的内容如表 1所示。

定理1  VFR-V2-RKNN算法能够返回正确的结果，算法的时间复杂度为O（clog_a|T_P|+blog_a|T_O|），其中：log_a|T_P|为VFR-树的大小；log_a|T_O|为障碍R-树的大小；c为视域范围内定位查询点的时间；b为候选集的大小。

证明定理1的正确性：算法通过遍历VFR-树获取距离查询点最近的并且在其视域范围内包含查询点的k个可视最近邻，在树的遍历过程中根据节点的不同类型进行处理，候选集中的数据对象经过视域可视性算法的判定，若均满足与查询点之间是视域可视的，而视域可视性算法是针对过滤障碍集中的障碍根据剪枝规则1和2进一步处理的，剪枝规则1和2的正确性可以根据视域可视性的定义得到，由此证明候选集中的结果都是正确的。

时间复杂度分析：算法的时间包括遍历VFR-树的时间和遍历障碍R-树T_O的时间，而算法只需遍历一次VFR-树，遍历一次VFR-树的时间为log_a|T_P|。遍历T_O的次数为b，因为每个候选需要进行一次T_O的遍历，所以遍历T_O的时间为blog_a|T_O|。在VFR-树的遍历过程中需要查询扇形MBR是否包含查询点，这个时间为c，因此算法总的时间复杂度为O（clog_a|T_P|+blog_a|T_O|）。

4 实验结果及分析

实验环境为Intel CORE i5-10400 CPU，2.9 GHz，8 GB内存，1 TB硬盘，Windows 10操作系统，用C++语言实现。

实验数据包括模拟数据集和真实数据集，模拟数据集是由随机数生成器产生的数据，数据分布为Uniform分布和Zipfian分布数据集，数据集大小为5×10³~1×10⁵，障碍集采用http://chorochronos.Datastories.Org中Greece真实数据集，选取River数据集中的5×10³~2.5×10⁴条河流的MBR数据作为障碍集。以下实验中，用UR（Uniform River）表示数据集采用Uniform分布的模拟数据集而障碍集采用真实的River数据集；ZR（Zipfian River）表示数据集采用Zipfian分布的模拟数据集而障碍集采用真实的River数据集。所有数据都被映射在200×200的数据空间中。查询点从数据集中随机选取，实验参数详情如表 2所示。

实验测试算法执行过程中的查询执行时间，每个实验执行100次，最终结果取平均值。实验在不同分布数据集上分别比较R^*-V2-RKNN算法和VFR-V2-RKNN算法的性能。

1）测试数据集大小对查询指标的影响。选取数据集大小|P|为5×10³~1×10⁵，障碍集大小|O|为1×10³，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。

2）测试障碍集大小对查询指标的影响。选取数据集大小|P|为1×10³，障碍集大小|O|为5×10³~2.5×10⁴，障碍集中数据从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算法。

3）测试k值的变化对查询指标的影响。基于UR数据集进行实验，选取数据集大小|P|为1×10³，障碍集大小|O|为1×10³，图 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算法。

基于ZR数据集进行实验，选取数据集大小|P|为1×10³，障碍集大小|O|为1×10³，查询点q从密集区域数据对象中选取，图 11给出了k值的大小对查询时间的影响。如图 11所示，随着k值的增大，算法R^*-V2-RKNN和VFR-V2-RKNN的查询时间逐渐增大，这是因为随着k值的增大，可视性判断的次数增加。但是算法在ZR数据集上的查询性能明显低于UR数据集，原因是数据集密集，访问数据量明显增大，包含在对象视域范围内的数据对象将明显增加，由于算法VFR-V2-RKNN基于剪枝规则，因此查询查询性能明显优于R^*-V2-RKNN。

基于ZR数据集进行实验，选取数据集大小|P|为1×10³，障碍集大小|O|为1×10³，查询点q从稀疏区域数据对象中选取，图 12给出了k值的大小对查询时间的影响。

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