连续近邻查询方法的研究

Research for the methods of continuous nearest neighbor queries

连续近邻查询(CNN)是时空数据库中一种重要的查询类型。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文利用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。

Continuous nearest neighbors （ CNN ） inquiry is important in spatial-temporal database.Voronoi diagrams is employed to resolve CNN inquiry, which is explicit and simple in thought. But the cost of constructing higher-order Voronoi Diagrams is too high, particularly to a high-order Voronoi Diagrams .This paper is based on the conception of division and bound to decide the upper bound of scope of Voronoi generaters,this paper proposed a method which dynamically constructs partial Voronoi diagrams to reSolVe CNN inquiry.This method take points of k nesaest neighbors of every point on given line segment as generaters to construct a k-order Voronoi diagram to resolve kCNN inquiry.So sharply lowered the cost of the continuous k nearest neighbors inquiry.