基于Voronoi图的反向最近邻查询方法研究

Reverse nearest neighbor queries using Voronoi diagrams

为了解决数据集中数据点的反向最近邻问题,利用Voronoi图及空间分割区域的性质计算查询点的反向最近邻,通过Voronoi图的特性可免去每次都计算数据集中给定查询点的最近邻的步骤,每次查询可过滤出少数的几个数据点并对其进行反向最近邻的判断.给出了在数据点被加入或删除时,对查询点的反向最近邻变化情况的判断方法与算法.为了便于数据库查询,设计了相应的空间存储数据结构.比较分析表明,该方法较适用于平面及复杂曲面上的数据点的反向最近邻的查询.

To effectively solve reverse nearest neighbor queries in a dataset, the properties of the Voronoi diagram and space-dividing regions were used to evaluate the reverse nearest neighbors of the given query points. By using Voronoi diagrams, the reverse nearest neighbors of a given point could be queried without computing the nearest neighbors every time. In each query, only a few data points were filtered out to perform a judgment about the reverse nearest neighbor. An algorithm and judgment method are given for instances of changes to the reverse nearest neighbor of the given query points caused by the addition or deletion of data points from the dataset. To more easily search for these points in a database, corresponding database storage structures were designed. Comparative analysis shows that this method is suitable for reverse nearest neighbor queries of data points on planar surfaces and complex curved surfaces.