基于Voronoi图的反向最近邻查询方法研究

被引：29

作者：

李松

郝忠孝

机构：

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

来源：

哈尔滨工程大学学报 | 2008年 / 03期

基金：

黑龙江省自然科学基金;

关键词：

反向最近邻; 空间分割区域; Voronoi图; R树;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

为了解决数据集中数据点的反向最近邻问题,利用Voronoi图及空间分割区域的性质计算查询点的反向最近邻,通过Voronoi图的特性可免去每次都计算数据集中给定查询点的最近邻的步骤,每次查询可过滤出少数的几个数据点并对其进行反向最近邻的判断.给出了在数据点被加入或删除时,对查询点的反向最近邻变化情况的判断方法与算法.为了便于数据库查询,设计了相应的空间存储数据结构.比较分析表明,该方法较适用于平面及复杂曲面上的数据点的反向最近邻的查询.

引用

页码：261 / 265

页数：5

共 6 条

[1]

Reverse nearest neighborssearch in Ad-hoc subspaces. MAN L Y,MAMOULIS N. IEEE Transactions onKnowledge and Data Engineering . 2007

[2]

Handbook on computationalgeometry. SACL J R,URRUTIA J. . 2000

[3]

Influence sets basedon reverse nearest neighbor queries. FLIP K,MUTHUKRISHNAN S. InternationalConference on Management of Data.Proceedings of the2000 ACM SIGMOD international conference on Manage-ment of Data . 2000

[4]

An index structure for efficient re-verse nearest neighbor queries. YANG C,LIN K I. Proceedings of theIEEE International Conference on Data Engineering . 2001

[5]

Reverse nea-rest neighbor queries for dynamic databases. STANOI I,AGRAWAL D,ABBADI A E. Pro-ceedings of the ACM SIGMOD Workshop on ResearchIssues in Data Mining and Knowledge Discovery . 2000

[6]

Reverse nearest neighbors in large graphs. MAN L Y,PAPADIAS D,MAMOULIS N,TAO Y. IEEETransactions on Knowledge and Data Engineering . 2006

← 1 →