空间数据库中的线段k近邻查询研究  

Research on line segment kNN query in spatial database

作　　者：周屹[1] 杨泽雪[1,2] 

机构地区：[1]黑龙江工程学院计算机科学与技术系,哈尔滨150050 [2]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机工程与应用》2015年第18期131-134,共4页Computer Engineering and Applications

基　　金：黑龙江省教育厅科学技术研究项目(No.12521442)

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

关 键 词：线段 VORONOI图 K近邻查询 空间数据库 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]