关键词: 线段, Voronoi图, k近邻查询, 空间数据库

Abstract: K-nearest neighbor query is one of the most important queries in spatial database. K-nearest neighbor query has important applications in the content similarity search, pattern recognition and geographic information systems. Existing k-nearest neighbor query is the query based on the point. The line segment k-nearest neighbor queries are put forward. That is finding k line segments whose distances to query point are the nearest. The algorithm of line segment kNN query based on Voronoi diagram is proposed and the relevant theorem and proof are given. The algorithm finds a candidate set with the adjacent properties of the segment Voronoi diagram, then finds the final results. Experiments on synthetic data sets show that the proposed algorithm outperforms brute-force method and the algorithm based on R-tree.

Key words: line segment, Voronoi diagram, k nearest neighbor query, spatial database