空间数据库中基于Voronoi图的线段反k最近邻查询

摘要

为了解决已有研究成果无法有效处理空间数据库中基于线段的反k最近邻查询问题,提出基于Voronoi图的线段反k最近邻查询方法（LRk NN方法）.该方法获得的结果集是将查询线段作为k NN的线段集合,在实际应用中可以用来评估一个查询对象的影响力.LRk NN查询方法分为三个过程:初步剪枝、深度剪枝、精炼过程.在剪枝阶段利用Voronoi图的邻接特性可以有效地过滤掉大量的非候选者,快速地缩小查询范围,提高了整个算法的查询效率.在精炼阶段又利用定义排除不满足查询条件的对象,有效地提高了算法的准确性.理论研究和实验结果表明所提算法具有较高效率.