作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (5): 59-61. doi: 10.3969/j.issn.1000-3428.2010.05.022

• 软件技术与数据库 • 上一篇    下一篇

基于Delaunay图的反向最近邻查询

王 淼1,郝忠孝1,2   

  1. (1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;2. 哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-03-05 发布日期:2010-03-05

Reverse Nearest Neighbor Query Based on Delaunay Diagram

WANG Miao1, HAO Zhong-xiao1,2   

  1. (1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080;
    2. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-03-05 Published:2010-03-05

摘要: 将查询点作为Delaunay图的一个生成点,利用Delaunay图的生成点与其邻接生成点之间的关系,在查询点的邻接生成点集(元素个数小于等于6)中计算数据集中给定点的反向最近邻。把伴随Delaunay图增量生成过程产生的Delaunay树作为查询索引结构,该结构能存储Delaunay图,在数据点插入和删除时维护Delaunay图的拓扑结构。

关键词: 反向最近邻, Delaunay图, Delaunay树

Abstract: This paper takes query point as a generation point of Delaunay diagram and utilizes the relationship between this point and its adjacent generation point to search Reverse Nearest Neighbor(RNN) in adjacent generation point set(less than six elements) of query point. It takes Delaunay tree generated during the process of Delaunay incremental generation as the query index structure, which can store Delaunay diagram and maintain Delaunay diagram topology when a point is added or deleted.

Key words: Reverse Nearest Neighbor(RNN), Delaunay diagram, Delaunay tree

中图分类号: