基于Voronoi图的最近邻查询的研究  

Research on Nearest Neighbors Queries for Moving Query Point based on Voronoi Diagrams

作　　者：王淼[1] 

机构地区：[1]哈尔滨理工大学计算机与控制学院,哈尔滨150080

出　　处：《微计算机信息》2008年第33期259-260,263,共3页Control & Automation

摘　　要：移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型。基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树。进而给出了基于VR树索引结构的1NN查询算法。The nearest neighbor inquiry for moving query point is foundational and important in both mobile computing research and real life applications. Nearest neighbor inquiry based on Voronoi diagrams has been studied for quite a long time in Computational Geometry.Which concrete index structure to inquire the spatial search used in the nearest neighbor inquire based on the Voronoi diagram in the past research is rarely mentioned . In this paper a new index structure VR-tree is presented, which combines the advantage of Voronoi diagram in the field of resolving nearest neighbor inquiry with the traditional R-tree.Then proposed a INN inquiry algorithm which is based on VR-tree index structure.

关 键 词：VORONOI图 K最近邻查询 VR树 

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