论文部分内容阅读
移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型。基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中基于voronoi图的最近邻查询究竞是基于何种具体的索引结构去实现对查询空间的搜索的，却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合，提出了一种新的索引结构：VR树。进而给出了基于VR树索引结构的1NN查询算法。