| 求k邻域的体素栅格算法研究 |
| |
| 引用本文： | 董洪伟. 求k邻域的体素栅格算法研究[J]. 计算机工程与应用, 2007, 43(21): 52-56 |
| |
| 作者姓名： | 董洪伟 |
| |
| 作者单位： | 江南大学,信息工程学院,江苏,无锡,214122 |
| |
| 摘 要： | 给定一个度量空间中的一组数据点集，k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本。目前主要有2种方法，一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格（CG（Cell Grid）方法，另一种方法是基于树索引结构的方法如kd-Tree等。论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法：排序体素栅格（SCG）方法和投影体素栅格（PCG）方法。CG、SCG、PCG算法采用了改进的搜索方法，避免了传统CG算法[2-4]可能得到错误k邻域的问题。对三种算法的时空性能进行了分析比较，给出了相应的实验比较数据。
|
| 关 键 词： | k最近邻域 BSP树 kd树 |
| 文章编号： | 1002-8331（2007）21-0052-05 |
| 修稿时间： | 2006-11-01 |
Study for cell grid methods finding k nearest neighbors |
| |
| DONG Hong-wei. Study for cell grid methods finding k nearest neighbors[J]. Computer Engineering and Applications, 2007, 43(21): 52-56 |
| |
| Authors: | DONG Hong-wei |
| |
| Affiliation: | School of Information Engineering，Southern Yangtze University，Wuxi，Jiangsu 214122，China |
| |
| Abstract: | Given a database or elements of a metric space,the k-nearest-neighbor problem consist in finding,for each element,its k nearest neighbors.Two approaches,one called CG(Cell Grid) method in this paper which based spatial cubic partitioning where the axis-aligned bounding box of the data points is partitioned by a cubical grid,and another based on tree structure such as kd tree are known for the problem.This paper concentrates on CG algorithm from which two improved algorithms called Sorted-Grid-Cell(SCG) and Projected-Grid-Cell(PCG) are presented.An improved k nearnest search process for CG,SCG and PCG is presented which avoids the wrong results occurred in the traditional CG algorithm used in paper [2-4].Comparisons for all the three algorithms are discussed and some empirical results are given. |
| |
| Keywords: | k nearest neighbors BSP tree kd tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
