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

摘要： K近邻查询是空间数据库中的重要查询之一，k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况，提出基于平面线段的k近邻查询，查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集，然后从中找到最终结果。通过随机数据的实验证明，所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。

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