基于Voronoicell的RNNk近似查询与计算（英文）

被引：1

作者：

郝忠孝 ^{[1
,2
]}

李博涵 ^{[1
]}

机构：

[1] 哈尔滨理工大学计算机科学与技术学院

[2] 哈尔滨工业大学计算机科学与技术学院

来源：

Transactions of Nanjing University of Aeronautics & Astronautics | 2009年 / 26卷 / 02期

关键词：

计算几何; 近似查询; 过滤; 反向k最近邻; Voronoi cell;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

在空间数据索引与查询研究领域中,反向k最近邻(RNNk)问题作为反向最近邻问题的泛化扩展近来受到更多关注。所谓RNNk查询就是找到所有以给定查询点为k个最近邻之一的对象点。为了有效地进行RNNk查询,利用分级的Voronoi cell和空间区域划分方法对查询结果进行有效过滤,避免了过多次最近邻查找计算。在初步得到的RNNk结果中,有针对性地分别利用平行于分割线的扫描线和局部扩展的查询区域Q进一步限定了RNN候选点。近似最小平均距离(AMAD)计算则可由近似的RNNk查询结果得到且不受k取值限制。实验结果表明了在3种不同数据分布情况下,本文算法与近似方法的效率和有效性。因此,通过充分利用对数据的过滤与查询空间修剪的近似方法,得到了具有较高查全率和准确率的近似查询和计算。

引用

页码：154 / 161

页数：8