障碍环境中可视反向视域K最近邻查询

在障碍环境下的空间应用中，用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题，将视域可视性引入到反向K最近邻查询中，提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q，可视反向视域K最近邻查询检索P中数据点，并将q作为可视视域K最近邻。应用查询点进行障碍过滤，得到障碍过滤算法，利用数据对象的视域进行剪枝，使用查询点与数据对象的关系剪枝，形成有效的障碍剪枝规则，并根据剪枝规则得到视域可视性判断算法。在此基础上，分别基于R^*-树和VFR-树提出可视反向视域K最近邻查询算法R^*-V2-RKNN和VFR-V2-RKNN，并分别通过对R^*-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明，VFR-V2-RKNN算法的查询性能明显优于R^*-V2-RKNN算法。

Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment

In spatial applications used in obstacle environments, users are usually only interested in visible data objects within the field of view.To solve the problem of a reverse nearest-neighbor query within the field of view in an obstacle environment, view field visibility is introduced into the Reverse K-Nearest Neighbor(RKNN) query, and a Visible Reverse View Field K-Nearest Neighbor (V2-RKNN) query algorithm is proposed.The query considers both the visibility and view field, which makes up for the deficiency in which the existing query only considers one aspect.Given a spatial data set P, an obstacle set O, and a query point q, the V2-RKNN query retrieves the data points in P that have q as their visible view field K-nearest neighbor.First, a query point is used for obstacle filtering to obtain the obstacle filtering algorithm.The view field of the data object is then used for pruning, and the relationship between the query point and data object is applied to the pruning to form effective obstacle pruning rules, based upon which a view field visibility judgment algorithm is achieved.On this basis, two visible reverse view field K nearest neighbor algorithms, R^*-V2-RKNN and VFR-V2-RKNN, based on an R^*-tree and VFR-tree, respectively, are developed.The two algorithms obtain their query results through one traversal of an R^*-tree and VFR-tree, respectively, and the query efficiency of the VFR-V2-RKNN algorithm is verified experimentally on real and synthetic data sets.