Reverse nearest neighbor queries using Voronoi diagrams
Hao Zhong-xiao · Harbin Gongcheng Daxue Xuebao/Journal of Harbin Engineering University · 2008
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.