| 基于Voronoi图的反向最近邻查询 |
| |
| 引用本文： | 刘润涛,张佳佳.基于Voronoi图的反向最近邻查询[J].计算机工程,2009,35(19):81-82,8. |
| |
| 作者姓名： | 刘润涛 张佳佳 |
| |
| 作者单位： | 1. 哈尔滨理工大学信息与科学计算技术研究所,哈尔滨,150080
2. 哈尔滨理工大学应用科学学院,哈尔滨,150080 |
| |
| 基金项目： | 国家自然科学基金资助项目，黑龙江省教育厅基金资助项目 |
| |
| 摘 要： | 为了解决反向最近邻查询问题，利用Voronoi图及数据集中点的凸包进行反向最近邻查询，通过判断查询点与凸包的位置关系，可去除大量的数据点，并且给出在数据点被加入或删除后，对查询点的反向最近邻变化情况的判断方法与算法。为了便于查询，设计相应的空间存储数据结构。比较分析表明，该方法在处理多个查询点的反向最近邻时有一定的优势。
|
| 关 键 词： | 反向最近邻 Voronoi图 凸包 |
| 修稿时间： | |
Reverse Nearest Neighbor Search Based on Voronoi Diagram |
| |
| LIU Run-tao,ZHANG Jia-jia.Reverse Nearest Neighbor Search Based on Voronoi Diagram[J].Computer Engineering,2009,35(19):81-82,8. |
| |
| Authors: | LIU Run-tao ZHANG Jia-jia |
| |
| Affiliation: | (1. Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080; 2. College of Applied Science, Harbin University of Science and Technology, Harbin 150080) |
| |
| Abstract: | In order to solve Reverse Nearest Neighbor(RNN) search in a dataset, Voronoi diagram and the hulls of dataset are used for RNN search. By determinating the location relation between query point and convex hulls, many points can be cut. And an algorithm and judgment method for the change of the RNN of query point are given when data points are added or deleted. To be convenient to search, corresponding spatial storage structures are designed. Comparative analysis shows that this method has evident advantages when many query points are dealt with. |
| |
| Keywords: | Reverse Nearest Neighbor(RNN) Voronoi diagram convex hull |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
