技术详细介绍
本发明公开了一种VoronoiDiagram与虚拟网格结合的高效空间最近邻查询方法，包括以下步骤：(1)使用VoronoiDiagram划分二维空间中的数据点，形成N个VoronoiCell；(2)使用虚拟网格将二维空间划分为若干个网格单元，确定网格单元的边长并进行编号；(3)设计计算虚拟网格单元和VoronoiCell之间的对应关系的方法，并存储在一个哈希表中；(4)计算查询点位置所在的网格单元，并确定对应的网格单元的编号；(5)在哈希表中查找查询点位置所在的网格单元所对应的VoronoiCell，并从中计算选择距离查询点位置最近的数据点返回给用户。本发明适用于大规模均匀分布的二维数据集，能够将空间最近邻查询的时间复杂度从O(logN)降低到O(1)，极大地提高了空间最近邻查询的效率。